Regression with Cost-based Rejection
Authors: Xin Cheng
Yuzhou Cao
Haobo Wang
Hongxin Wei
Bo An
Lei Feng
Venue: NeurIPS 2023 poster (2023)
Keywords: regression
rejection costs
surrogate loss
TL;DR: We investigate a novel regression problem called regression with cost-based rejection, where the model can reject to make predictions on some examples given certain rejection costs.

Abstract: Learning with rejection is an important framework that can refrain from making predictions to avoid critical mispredictions by balancing between prediction and rejection. Previous studies on cost-based rejection only focused on the classification setting, which cannot handle the continuous and infinite target space in the regression setting. In this paper, we investigate a novel regression problem called regression with cost-based rejection, where the model can reject to make predictions on some examples given certain rejection costs. To solve this problem, we first formulate the expected risk for this problem and then derive the Bayes optimal solution, which shows that the optimal model should reject to make predictions on the examples whose variance is larger than the rejection cost when the mean squared error is used as the evaluation metric. Furthermore, we propose to train the model by a surrogate loss function that considers rejection as binary classification and we provide conditions for the model consistency, which implies that the Bayes optimal solution can be recovered by our proposed surrogate loss. Extensive experiments demonstrate the effectiveness of our proposed method.

Regression with Cost-based Rejection
Xin Cheng'
Yuzhou Cao² Haobo Wang' Hongxin Wei
Bo An
Lei Feng"*
CCollege of Computer Science, Chongqing University, China
2School of Computer Science and Engineering, Nanyang Technological University, Singapore School of Software Technology, Zhejiang University, China
*Department of Statistics and Data Science, Southern University of Science and Technology, China xi 2nccheng9215@gmae il com, yuzhou0026e ntu. edu.. sg, wanghaobo@ z ju. edu. cn weihx@sustech, edu. en, boanêntu.. edu. sg, fengggaq gma com
Abstract
Learning with rejection is an important framework that can refrain from making predictions to avoid critical mispredictions by balancing between prediction and rejection. Previous studies cost-based rejection only focused on the classifica- tion setting, which cannot handle the continuous and infinite target space the regression setting. In this paper, investigate novel regression problem called regression with cost-based rejection, where the model can reject to make pre- dictions some examples given certain rejection costs. To solve this problem, we first formulate the expected risk for this problem and then derive the Bayes optimal solution, which shows that the optimal model should reject make pre- dictions on the examples whose variance larger than the rejection cost when the mean squared error used the evaluation metric. Furthermore, we propose to train the model by a surrogate loss function that considers rejection as binary classification and we provide conditions for the model consistency, which implies that the Bayes optimal solution can be recovered by our proposed surrogate loss. Extensive experiments demonstrate the effectiveness of our proposed method.
1 Introduction
In machine learning, the learned model from training data is expected to make predictions un- known test data as accurately as possible. However, would be unreasonable for the learned model to make predictions on all the test instances, as there may exist some difficult instances that the learned model cannot give an accurate prediction. Incorrect predictions can cause severe conse- quences and even can be life-threatening, especially in risk-sensitive applications [5, 19, 36, 11], such as healthcare management, autonomous driving, and product inspection. Therefore, the learn- ing with rejection (LwR) framework [10, 11, 36, 27, 31, 17, 8, 6, 38] was extensively investigated, which aims to provide a reject option to not make a prediction in order to prevent critical false pre- dictions. In this case, the LwR model can be learned by balancing the rejection and the prediction.
So far, most of the existing studies on LwR have focused on the classification setting, i.e., classifi- cation with rejection [10, 3, 44, 45, 14, 19, 37, 17, 8, 6J. A well-known framework for classification with rejection that has been studied extensively is called the cost-based framework, i.e., classifica- tion with cost- cost-based rejection [11, 12, 18, 39, 16, 36, 8, 6]. In the classification with cost-based rejection setting, there is pre-determined rejection cost for each instance, which must be smaller than the classification error 1. A typical approach for classification with cost-based rejection is the confidence based approach [22, 3, 45, 39, 40, 8J. The main idea to use the real-valued output of the classifier as the confidence score and decide whether to reject the prediction based on the
"Coresponding author: Lei Feng.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

confidence score and the given rejection cost Another effective approach is classifer-rejector
approach [11, 12, 36], which simultaneuusly trains classifier and rejector, and this approach achieves state-of-the-an ahrt performance in binary classification [36].
Despite many previous studies LwR, they only focused on the classification setting, which can- not handle the continuous and infinite target space in the regression setting. In many real-world scenarios, regression tasks with continuous real-valued targets can be commonly encountered. How- ever, even state-of-the-art regression models may make incorrect predictions, and blindly trust- ing the model results may lead to critical consequences, especially in risk-sensitive applications [7, 4, 28, 23, 48]. Therefore, it is necessary to consider adding a rejection option for the regression problem to not make predictions in order to avoid critical mispredictions. To this end, many studies have been conducted on regression with rejection. A widely studied framework in regression with rejection is called selective regression [26, 44, 20, 46, 27,41] 41] that trains a regression model with a reject option given a fixed reject rate of predictions. However, this selective regression setting fails to consider the cost-based rejection scenario where a certain cost could be incurred if the model chooses to refrain from making prediction for a certain instance.
In this paper, we provide the first attempt to investigate novel regression setting called regression with cost-based rejection (RcR), where the model could reject to make predictions on some instances certain costs to avoid critical mispredictions. To solve the RcR problem, we first formulate the expected risk and then derive the Bayes optimal solution, which shows that the optimal model should reject make predictions on the examples whose variance larger than the rejection cost when the popular mean squared error is used as the regression loss. However, it is difficult to directly optimize the expected risk to derive the optimal solution, since the variance of the instances cannot be easily accessed. Therefore, we propose surrogate loss function to train the model that considers the rejection behavior as a binary classification and we provide theoretical analyses to show that the Bayes optimal solution can be recovered by minimizing our surrogate loss under mild conditions. Our main contributions can be summarized as follows:
We propose a surrogate loss function considering rejection as binary classification and we demon- strate the regressor-coossistenn, and the rejector-calibration when the binary classification loss function is cetssfiiaatton-calirrttet and is always greater than 0.
We also provide relaxed condition that allows the daasifiiattoon-caliiiane binary classification loss to be non negntvvaeie.. In the relaxed condition, the for correctly accepted instances.
can still be satisfied
We derive a regret transfer bound and an estimation error bound for our proposed method, and extensive experiments demonstrate the effectiveness of our method.
2
Preliminaries
In this section, we introduce preliminary knowledge of ordinary regression, classification with re- jection, and selective regression.
2.1 Ordinary Regression
For the ordinary regression problem, let the feature space be X' e Rd and the label space be y R. Let us denote by (x, y) an example including an instance æ and a real-valued label y. Each example (x, 3) X' y is assumed probability density p(æ,y). y). For the regression task, we aim to learn a regression model h X' + R that minimizes the following expected risk:
be independently sampled from an unknown data distribution with
R(L)= Bx( [T(h(m) v)),
where (Ep(a.g) denotes the expectation over the data distribution p(æ,8) y) and L R x R + 14 is a conventional loss function (such as mean squared error and mean absolute error) for regression, which measures how well model estimates a given real-valued label.
2.2 Classification with Rejection
widely studied framework in classification with rejection is the cost-based framework 360,36,8 6] that aims to train a classifier f : X - - that can reject to make a prediction, where @ denotes the

---

reject option. The evaluation metric of this task is the zero cero-one-c loss fuie defined as follows:
fole(f(z), { (), z), otherwise,
c(x), f
where c(z) is the rejection cost associated with æ. Then, the expected risk with loie can be repre- sented as follows:
Roie(f) = Bpta (Foe))))))(((()
The optimal solution for classification with rejection f Roie given by Chow's rule [10] can be expressed as follows:
Definition 1. (Chow's s Rule [10]) A classifier f: x + t the optimal solution of expected risk (3) if and only if the following conditions are almost satisfied:
R max (2) 10-55114 c(x)
f(x)
(4)
aargmax ( (x)) otherwise,
where (==) p(=[ar). Chow's rule shows that classification with rejection be solved when (xx) is known. However, the estimation of the probability difficult especially when using deep neural networks [24].
2.3 Selective Regression
In selective regression, for given instance æ, the selective model can choose to make a prediction for it reject to make prediction without costs. Formally, the selective model is pair (h, where h : X - R is a regression prediction model and r X - R selection model, which serves the rejection rule as follows,
(h,r)( (1(x))
r(x) >
(5)
otherwise.
Let us denote by e the expected rejection rate and denote by <dr) = pn [[((x)) > 0] the coverage of selective regression. The purpose of selective regression is derive pair (h, r) such that the risk R(h,r) r) [ptt.s) [I(h(z), (xx > O]] is minimized with coverage L(h(z), y) is a conventional regression loss function. However, the selective regression setting fails to consider the cost-based rejection scenario but fixes the rejection rate e. In many real-world scenarios, rejection with costs is more common, and the cost c(x) is casier to provide compared with the rejection rate
<(r) < where
3 Regression with Cost-based Rejection
Let X E IRd be the d-dimensional feature space and y E RR be the label space. Suppose the training set is denoted by D = {x;,
and each training example (æ;, vi) E x ) is assumed to be sampled from an unknown data distribution with probability density p(æ; y). In RcR setting, for given instance x, the learner has the option @ to reject making a prediction or to make a regression prediction. If the learner rejects an instance, the cost is non-negative loss c(x). The goal of ReR is to induce a pair (h,r) where r: X' r> R is rejector to determine whether reject instance not. The evaluation metric of this task is the following loss function L(h, r, C.
X' + R is a regressor to predict the accepted instance and
((h,r,c,z,v) L ((h(z)) v), r(x) > 0, c(x), otherwise,
(6)
where I(h(2)))) y) is conventional regression loss function (e.g., mean squared error).
In what follows, we will present Bayes optimal solution to the ReR problem and provide a surro- gate loss function to train the regressoorrejector.
3

---

3.1 Bayes Optimal Solution
In this paper, we only discuss the case where the loss function ((h(2)). y) is the mean squared error (MSE), which is the most widely used regression loss function. The expected risk of ((h, r, c, x) over the data distribution can be represented as follows:
Racn (h, r) = Ept r,,,r. c, c,
Let us denote by (h', = argmin RRO (h, r) the optimal pair of the expected risk RROR -s p(y](()))))) (yyy and [) = Jy p(y (x))))( [p dly denote the expectation and variance of y over the distribution p(y (r) For a given cost function c(z), we have
and we Bp(ul=)yy] -
the following theorem:
Theorem 2. For a given instance non-negative cost c(x) and the Bayes optimal pair (h*, r*)
of the risk RReR the following equality holds:
h" (a) [p
(8)
(xx) = I (c(x)) D P)ll)))ll)
The proof of Theorem 2 is provided in Appendix A. is worth noting that our derived Bayes optimal solution in Theorem 2 can be considered as generalized version of Proposition 2.1 in Zaoui et al. [46], with an instance-dependent cost function. Theorem 2 shows the expected optimal pair (h",r*) of risk RRCR where the rejector r* should reject making a prediction the variance of the distribution of labels y associated with is so large that it exceeds given rejection cost c(x)). This is intuitive and easy to understand. Unfortunately the probability density function p(y x) is usually unknown, meaning that obtaining the variance Dptsl=) [y] and expectation Ep (=) [y] is difficult or even impossible. Many previous studies adopted specific assumptions to avoid directly estimating the variance and the expectation (e.g., homoscedasticity [26, 43, 42] and heteroscedasticity [29, 30, 9, 32]), while all of them have certain constraints. Therefore, the key challenge of RcR is how to learn the optimal solution
rr" without the expectation and the variance.
3.2 Surrogate Loss Function of Training Regressor-Rejecte
we know how the optimal pair (h", r"*) makes rejection and prediction for an un- known instance, but since the expectation and the variance are difficult to obtain, we cannot directly derive the optimal regressor and rejector. Let reconsider the ReR loss function [(h, T, C, x, y) by the following equation: C(,,T,C,z,y) (h(x)= u[(((( > 0J + c(=))[r(x)) s 0].
From Theorem 2,
(9)
where I[:] denotes the indicator function. We cannot directly derive regressor h and a rejector by the above loss since the loss function contains non-convex and discontinuous parts I[((x) > 0] and I[((x) < 0]. In order to efficiently optimize the target loss, using surrogate loss is preferred. It is worth noting that the behavior of the rejector is similar to binary classification due to the only two options, rejection and acceptance. We may consider it directly binary classification (1), where +1 means acceptance and -1 means rejection. Then we have the following surrogate loss function:
(h, r, az, x;, v) = (l((=) - ())())) -1) + c())))(r(())++1)
(10)
where E(-) is an arbitrary binary classification loss function such as hinge loss. Then the expected risk with our surrogate loss to can be represented follows:
R (h, r) (v r, v)]-
(11)
The intuition behind this is that when the squared error is less than the given cost, we expect its weight (r((x),-1) l to be larger, i.c., (r((x), +1) to be smaller. However, not every binary classifi- cation loss is theoretically grounded.
4 Theoretical Analysis
In this section, we first introduce the definitions of regressor-consistency and rejector-calibration. Then, we show the condition that our method can result in the Bayes optimal solution. Furthermore, we provide relaxed condition that the regressor-consistency is only satisfied for correctly accepted instances. Finally, We derive a regret transfer bound and an estimation error bound for our method.

---

4.1 Regrsssor-Consisteecy and Rejector-Calibration
The rejector-calibration we are talking about here related to the notion of classification calibration [1, 47, 15]. The notion of classification calibration of surrogate losses is defined as the minimum requirement to ensure that risk-min lisk-minimizing classifier becomes the Bayes optimal classifier, which is a pointwise version of consistency. The definition of rejector-calin cepetor-calibbatiion is given below.
Definition 3. segjector-calibratiin the same decisions as the Bayes optimal rejector r* in Theorem 2, i.e., sign(r(æ)) = sign(r"(z)) for all
We say a rejector r X R is calibrated if r always makes
X such that (x) +
The definition of rejector calibration indicates that we do not need to obtain the exact optimal rejec- tor due the diffieulty of obtaining the variance, therefore, we just need to ensure that rejector makes the same decisions as the optimal rejector in Theorem 2.
reejetor-calibration
On the other hand, we define the regressor-consistency as follows. Definition 4. Reegressor-consistens We say a regressor h X - consistent if is equivalent to the Bayes optimal regressor h* in Theorem 2, i.e., h = h*
Then demonstrate that method is regressor-consisten by the following theorem:
Theorem 5, Suppose the binary loss i always larger than For a given non-negative cost func- tion c(x), for any fixed rejector r, the optimal regressor h = argmin R (h, r) is equivalent to the Bayes optimal regressor h²
The proof of Theorem is provided in Appendix B.I. Theorem 5 shows that the regressor h learned from our method can be equivalent to the Bayes optimal regressor h:"
It is worth noting that there is special case [(r(x), 1) = O. where the regressor actually ig- nores the instance æ. Here we show a relaxed condition for regressor-consistencyy by the following theorem:
Theorem Suppose the binary loss function clussficationn and is always non- negative. Given a non-negative cost function c(r),, for any fixed rejector and for the optimal regressor h argmin B r), the regressor-comsistency can be only satisfied for cor- rectly accepted instances (i.e., Vx E X, (x)) > 0).
The proof of Theorem provided Appendix B.2. Theorem gives a relaxed condition of consistency, where the regressor-comsiitengy is still satisfied for correctly accepted instances.
Then, we demonstrate that our method is egjector-calibratee by the following theorem:
Theorem 7. Suppose the binary loss is classifictton-calibrue
and is always larger than O.
For given non-negative cost function c(x), the optimal rejector r = argmin, R (h r) is calibrated (i.e., sign(r;; (z))
(x))))(())))))) where r" is the Bayes optimal rejector.
The proof of Theorem is provided Appendix B.3. Theorem 7 shows that our method is rejector- calibrated if the used binary loss É is clasification-caliiratd..
4.2 Regret Transfer Bound and Estimation Error Bound
In the previous section, have given the Bayes consistency analysis of method, i.e., if the minimizer of our proposed risk can be the optimal one in Theorem 2. However, such a result does not guarantee the performance of models that are close to but not the minimizer of the risk R which occurs commonly since we usually minimize the empirical risk practice. We provide theoretical guarantee for such cases by showing the following regret transfer bound:
Theorem 8. Suppose that Va E X, Vy V, (piy)))((((x)) y) S M and c(x) S C hold almost surely:
RRER RiEn S E(RR (h, R)x
This regret transfer bound holds for widely used binary losses, e.g., when is the sigmoid loss or the hinge loss, E(n) = [n]. When is the logistic loss or the square loss, E(u) min 2u, 2/M M + C)u
5

---

The proof of Theorem 8 is provided in Appendix C.I. This theorem guarantees that even if the obtained (h, r) is not exactly the minimizer of R we can also expect them to achieve good performance as long as they have low risk R RRR Then we can further get the following estimation envor bound:
Theorem 9. Suppose the binary loss is upper bounded by M1 > 0 and p p-Lipschitz continuous, |/1, c(æ),, and ly] are bounded by M2 > 0. Given the empirical risk minimizers h and f, the following bound holds with probability at least - 6:
21og(2/8)
ROR (h, f) R I 2 ( + C.V
T2
where Ci = (4M3 - M2) L1 = / Mi) ( 16M n is the i.i.d. sample size, and Rn the Rademacher complexity [2].
The proof of Theorem 9 is provided in Appendix C.2. Given the fact that the Rademacher complexity usually decays at the rate of O(1/ we can finally conclude that the performance of our model can approximate its optimal performance with the increasing size of the training set. In the following sections, we will demonstrate the effectiveness of our approach through experiments.
5 Experiments
In this section, we show the experimental results when our method is equipped with various binary classification losses and is compared with selective regression methods. In addition to the evalu- ation metrics commonly used for LwR, we propose additional evaluation metrics. Details of the experiment and the complete experiment can be found in Appendix D.
5.1 Implementation Details
When using deep neural networks as the model and using the gradient descent optimization, we consider a possible scenario where the regressor predicts any instance æ with such large er- ror that {(h(x),,)) >> c(x). In this case the rejector expects to reject all instances to make the empirical risk minimal. However, when the rejector r converges quickly to reject all train in- stances, i.c., ((r(x).-1)
0 for all train instances, the surrogate loss vé will be constant equal to (ct)((((z)++1)) At that point the gradient of the regressor h suffers from gradient vanishing. The main reason for this situation is that the regressor h has not learned the distribution of the label, but the rejector r has converged, which means that the regressor is not ready. Fortunately, we can avoid such situation by training the rejector after the regressor ready, and name such a method Slow-Start. Specifically, Slow-Star prioritizes training the regressor h without training the rejec- tor r, and then co-trains the regressor h and rejector when the regressor h is capable of making predictions.
5.2 Datasets and Backbone Models
We conduct experiments on seven datasets, including one computer vision dataset (AgeDB [35], one healthcare dataset (BreastPathQ [33]), and five datasets from the UCI Machine Learning Repos- itory [13] (Abalone, Airfoil, Auto-mpg. Housing and Concrete). For each dataset, we randomly split the original dataset into training, validation, and test sets by the proportions of 60%, 20%, and 20%, respectively. worth noting that our approach has no restrictions on the regressor and rejector so / and can be two separate parts or share parameters.
AgeDB regression dataset on age prediction [21] collected by [35]. It contains 16.4K face images with a minimum age of 0 and a maximum age of 101. Age prediction is not an easy task, especially when only a single photo is available. Lighting, clothing, makeup, and facial expressions all tend to affect the intuitive age, and even friends can hardly say they can identify the age in photo. Rejecting predictions for photos with complex environments can avoid large errors. We employ ResNet-50 [25] as our backbone network for AgeDB, and the regressor h and rejector share parameters. We use the Adam optimizer to train our method for 100 epochs where the Slow- Start is set to 40 epochs, the initial learning rate of 10-3 and fix the batch size to 256.

---

Table 1: Test performance (mean and std) of surrogate loss equipped MAE BreastPathQ. We repeat the process times. metrics Rej, AR, RA are scaled 0-100 and Sup, ReRLoss, and RL are all magnified by factor of 1000.
Cost
Sup
ReRLoss
AL
RL
Rej
AR
RA
31.51
72.53
52.61
6.53
5
(0.17)
(1.07)
(2.29)
(4.44)
(5.10)
(2.66)
8.22
5,50
37.14
60.08
43.14
11.01
(0.70)
(1.98)
(4.43)
(4.34)
(4.49)
(4.22)
16.77
11.11
6,84
40.39
53.49
38.39
15.46
(1.22)
(0.55)
(1.43)
(1.67)
(3.39)
(2.86)
(3.97)
13.84
9.53
43.41
40.65
29.98
29.02
20
(0.62)
(1.69)
(5.34)
(7.28)
(6.58)
(9.81)
46.62
24.47
17.46
25
(1.32)
(2.48)
(9.43)
(4.26)
(4.96)
(8.00)
Table 2: Test performance (mean and std) of our surrogate loss equipped MAE on AgeDB, We repeat the sampling-ae and and-aaaddntaa trainiianing process 5 times. The metries Rej. AR and RA scaled to 0-100.
Cost
Sup
RcRLoss
AL
RL
Rcj
AR
RA
59,80
54.25
156.81
95.40
93.13
2.51
(0.31)
(4.41)
(23.21)
(2.88)
(4,30)
(1.56)
69.00
61.56
151.04
86.22
81.41
8.12
70
(0.39)
(4.10)
(12.05)
(2.94)
(3.07)
(2.49)
77.10
67.32
150.52
76.00
70.63
16.11
(1.72)
(2:21)
(12.36)
(15.71)
(16.36)
(13.20)
100.34
85.36
73.07
162.44
73.38
67.33
17.20
(3.73)
(2.23)
(3.21)
(12.45)
(11,50)
(12.07)
(9.08)
92,94
82.89
170.04
58.35
$2.15
30.56
100
(7.47)
(20.53)
(12.51)
(11.59)
(12.48)
95.08
79.62
166.07
52.15
46.13
34.38
(5.62)
(5.44)
(13.75)
(14.96)
(14.76)
(13.40)
82,44
37.11
32.54
51.31
120
(7.45)
(2.40)
(12.58)
(22.64)
(21.42)
(23.96)
BreastPathQ [33] is healthcare dataset collected at the Sunnybrook Health Sciences Centre, Toronto. The dataset contains 2579 patch images, each patch has been assigned tumor cellu- larity score score of 0 to 1 by expert pathologist. Currently, this task is performed manually and relies upon expert interpretation of complex tissue structures. Moreover, cancer cellularity scoring is extremely risky and the use of automated methods could lead to irreversible disasters. Regression with rejection can improve this problem very well by predicting only the accepted samples and leav- ing the rejected samples back to the experts for evaluation. We use the same network as AgeDB and train 300 epochs using Adam optimizer where the Slow-Start is set 50 epochs, the initial learning rate of 10 and fix the batch size to 128.
We conducted experiments on five UCI benchmark datasets including Abalone, Airfoil, Auto-mpg, Housing and Concrete. All of these datasets can be downloaded from the UCI Machine Learning [13]. Since our proposed method do not depend on specific model, and we train two types of base models including the linear model and the multilayer perceptron (MLP) to support the flexibility of our method on choosing model, where the MLP model is five-layer (d-20-30-10-1) neural network with ReLU activation function. For the rejector and regressor h. we consider them as two separate parts with the same structure. For both the linear model and the MI.P model, we use the Adam optimization method with the batch size set to 1024 and the number of training epochs set to 1000 where the Slow-Star is set to 200 epochs. The learning rate for all UCI benchmark datasets selected from {10-1 10 10 10-3).
5.3 Evaluation Metrics
For evaluation metrics, we use the ReR loss (RcRLoss) Eq. (6) and the rejection rate (Rej). In order to further investigate how the model work, propose additional metrics. Accepted losses
7

---

Table 3: Test performance (mean and std) of surrogate loss equipped MAE five UCI datasets trained with the MLP model. We repeat the coupliig--nd--raniii process 10 times. The metrics Rej, AR, and RA are scaled to 0-100.
Sup
Rej
2.41
199
8.13
42.04
32.82
33,33
(0.12)
(0.21)
(1.08)
(3.18)
(3:44)
(3.22)
Abelonc
4
4.44
(0.13)
2,88
(0.21)
2.30
(1.70)
11.37
33,70
(2.81)
25,56
(3.71)
39.27
5
(0.46)
3.22
2.66
10.30
23,43
16.83
48.98
(0.23)
(0.35)
(1.25)
(2.94)
(2.41)
(5,90)
3,53
2.93
12.13
19.32
53,20
(0.25)
(0.35)
(1.69)
(3:47)
(3.33)
(5.67)
7.20
37.80
(0.35)
(0.86)
(2,95)
(3.73)
(5.73)
(3.29)
8.11
5.39
51.51
40.33
23.37
25,88
(0.36)
(0.86)
(10.51)
(7.95)
(7.20)
(9.04)
9.15
6,84
72,80
24.92
11.92
38,17
Airfoil
16
12.96
(0.43)
(20.79)
20
(2.60)
11.32
8.83
58.28
21.53
13:70
48.66
(0.75)
(1.47)
(8.87)
(7.71)
(5.34)
(18.08)
(1,54)
(1.35)
(16.07)
(5.11)
(3.60)
(12.32)
11.68
96.55
2.52
86.35
(3.07)
(3.20)
(16.60)
(3.81)
(1.78)
(20.06)
3.64
2.99
13.98
56.92
46.80
28.74
(0.29)
(0.83)
(4.16)
(13.00)
(15.49)
(10.51)
6
(0.93)
4,83
(1.70)
3.83
(5.95)
18.04
(14.10)
37.31
(12.74)
29.01
(19.54)
42.42
Auto-mpg
8
(2.16)
8.34
(1,93)
6.75
(2.41)
6.14
(12.48)
25.59
(19.88)
22.95
(18.27)
19:26
(23.95)
64.99
7.14
23.29
10
(1.64)
(2:24)
(9.54)
(6.58)
(5.12)
(15.98)
8.13
7.42
35.49
12,56
10:38
71.52
(2.41)
(2.83)
(23.74)
(6.83)
(6.14)
(14.52)
8.80
6.25
40.28
84,46
77.60
9,72
(0.34)
(3.22)
(17.30)
(5.91)
Housing
12
12:57
(0.75)
9.52
(1.48)
7.40
(25.98)
58.94
44.65
33.30
(8.64)
31.25
16
(3.43)
(1.84)
10.12
(1.58)
8.35
(44.53)
88. 34.14
(8.90)
22.38
(6.81)
14.21
(14.41)
$1.84
20
(3.32)
10.50
(3.50)
9.59
(109.35)
184.24
(6.82)
(5.32)
(13.11)
73.40
82,17
(1.32)
(4.91)
(14.58)
(6.92)
(9.37)
(4.47)
24.20
19.29
112.13
44,08
27.43
26.80
(1.85)
(3.85)
(30.32)
(8.81)
(8.55)
(7.90)
Concrete
40
34.44
28.63
23.12
136.51
31.50
18.32
39.49
(3:05)
(2.56)
(4.59)
(46.59)
(8.98)
(12.07)
50
(2.76)
32.48
(4.31)
27.90
(41.73)
168.19
(7.54)
19.76
(4.51)
10:54
(13.74)
53.82
197.26
(3.50)
(4.89)
(49.03)
(6.62)
(3.21)
(14.99)
(AL) and rejected losses (RL) denote losses on accepted instances and rejected instances, and they are defined as Σr (k))))
and Σ. (h(()))))))(
We also present the false rejection rate (AR) and false acceptance rate (RA) similar to false negative and false positive, which denote the rate of instances that should be accepted that are rejected and the ratio of instances that I[(h(x;) - (lt and should be rejected that are accepted, and they are defined as > -:; ΣT_ (.
>" [[((m))>0]
>nn T[((2,))0)
Ee I((h(a,))))) (eteer,))))))) "0)))))(((.))))(((aa)..... S (1)
It is worth noting that the optimal pair (h", r*) is unknown, so AR and RA for the current regressor and rejector. We also provide the results under supervised regression method (Sup) that directly trains the model with MSE from fully training set.
5.4 Formulation of Surrogates and Setting of Rejection Costs
In our experiments, we consider a variety of binary classification loss functions, such as mean ab- solute error (MAE), mean square loss, logistic loss, sigmoid and hinge loss. The rejection cost

---

Breast
Abalone
Abalone
RCR loss
16.
hage
Leghit
Ginne
12.
Sgyo
Page
Lopbit
3.6
3.4
3.2
Squan
Leghte
3.0
2.8
Legine
Squar
10. Muz
Muc
3.0
AL
E 2.0
2.6
20 Rejection cost
10 15
25
2
5
10 15
20
25
2.4
4
Rejection costic
Rejection cost c
Rejection cost
(a) ReRLoss on Breast
(b) AL on Breast
(c) ReRLoss on Abalone
(d) AL on Abalone
Figure 1: Figures (a) and (b) report the ReRLoss and AL with different rejection cost when different binary classification losses are equipped to the Breast dataset, respectively. Figures (c) and (d) report the RcRl Loss and AI with different rejection costs when different binary classification losses equipped to the Abalone dataset, respectively.
<(x) is considered as a constant, which is the most commonly considered scenario in learning with rejection [6, 8, 36, 11]. For each dataset, we set various rejection costs including extreme cases and unstressed cases depending on the supervised loss. The complete experiments are provided in Appendix D.
5.5 Experimental Performance
Table I, Table 2 and Table 3 show the experimental results when surrogate loss function equipped with MAE on the AgeDB, BreastPathQ,, and UCI datasets, respectively. From these three tables, we have the following observations: (1) Our proposed method significantly outperforms the supervised regression method in almost all cases, which validates the effectiveness of our method by rejecting difficult test instances.
(2) In most cases, the average loss of our method in accepted test instances is always smaller than the average loss of the supervised regression model in all test instances. This further indicates the ability of our method to identify hard-to-predin instances and reject them. (3) As the rejection cost e increases, we can clearly see the following trends in all datasets: RcRLoss decreases; Rejection rate decrease; Accepted loss increases. This is because as the prediction error we can accept increases, i.e., the rejection cost increases, the rejector will accept more instances, leading decrease in the rejection rate. However, the regressor capacity remains the same and more instances (containing difficult instances) also face more challenges, so ReRLoss and AL in- crease but remain smaller than Sup. (4) In setting the rejection cost c, we consider many extreme cases, e.g., the rejection cost is much smaller and much larger than the average loss in the supervised regression. In such extreme cases, our approach is still effective to identify and reject difficult test instances. In addition, we show in Figure when different binary classification losses are equipped on the Breast and Abalone datasets. As the rejection cost increases, both AL loss and RcRLoss also increase.
plot of ReRLos Loss with the increasing rejection cost
5.6 Comparison with Selective Regression Methods
Since our paper provides the first attempt to investigate regression with cost-based rejection, there does exist baseline that can be directly compared. However, the Bayes optimal solution of regression with cost-based rejection is the same as the Bayes optimal solution of selective regression, we compare with selective regression methods. We have conducted additional experiments compare with SelectiveNet [20] and Knn-Plug [46]. For SelectiveNet, this work proposes a neural network architecture and an optimization goal control the rejection threshold of the rejector to ensure specific rejection rate. To ensure fair comparison, we use the same base model for all datasets. For Knn-Plug, this method proposes semi-supervised learning process for learning data-driven predictor with a reject option based on the plug-in principle. Specifically, this method learns a regression function h and conditional variance function from the labeled dataset, while the unlabeled dataset is used to calibrate the conditional variance function o to ensure the desired rejection rate. For each dataset, we randomly split the original dataset into labeled training set, an unlabeled training set, and a test set by the proportions of 60% (the same size of labeled training set as ours), 20%, and 20%, respectively. To ensure fairness, we replace the original base model Knn with MIP and named MI.P-Puug

---

Table 4: Comparison with SelectiveNet and MLP-Plug. The cost the rejection cost in regression with based rejection and Rj is expected rejection rate in selective regression.
RcR_MAR
MLP Plug
SelectiveNet AT.
Datasets
Cost
AL.
Rj
Rj
Rej
3
2.41
(0.21)
1.99
(3.18)
42,04
42.04
2.13
(2.70)
40,93
42.00
(0.19)
2.10
(1.84)
42,80
2,88
2,30
33,70
2.36
32,30
2,40
34,26
Abalome
4
(0.13)
(0.21)
(2.47)
33.70
33.00
(0.22)
(1.52)
5
(0.23)
3,22
(0.35)
2.66
(2.94)
23.43
23.43
(0.23)
2.72
(3.69)
22.00
23.00
(0.42)
2.84
(1.71)
25.10
6
(0.25)
3.53
(0.35)
2.93
(3,47)
19.32
19.32
(0.31)
2.94
(2.71)
17.64
19.00
(0.39)
2.92
(2.00)
21,20
3.64
2.99
56.92
56.92
4.83
56.08
56.00
3.58
57.44
(0,29)
(0.83)
(13.00)
(2.28)
(6.53)
(1.91)
(5.06)
Auto-mpg
6
(0.93)
4.83
(1.70)
3.83
(14.10)
37.31
37.31
(2.14)
5.64
(9.47)
36.46
37.00
(2.48)
6.29
(6.34)
35.13
8
(1.93)
(2:41)
(19.88)
22.95
(2.03)
(9.82)
23.00
(2.08)
(5.91)
13
7.42
12.56
10.63
7.79
11.15
(2.41)
(2.83)
(6.83)
(1.93)
(3.54)
(2,29)
(3.49)
8.80
6,25
84.46
84,90
7.70
86.88
(0.34)
(3.22)
(11.67)
84.46
(4.70)
(8.22)
84.00
(2,22)
(4.56)
12
9.52
7,40
44.65
9.76
44,80
8.20
46.83
Housing
(0.75)
(1.48)
(8.69)
(2.82)
(8.62)
(2.11)
(5.86)
16
(1.84)
10.12
(1.58)
8.35
(8.90)
22.38
(3.70)
10.52
(6.50)
22.55
22.00
(1.64)
8.73
(4.52)
26.44
10.50
9.59
8.51
11.16
10,20
8.79
11.39
20
(3.32)
(3.50)
8.51
(4.14)
9,00
(1.67)
(2.44)
18.03
13.17
69.42
18.96
71.17
14.44
71.60
20
(4.91)
69.00
69.00
(4,42)
(3.16)
30
24.20
19.29
44.08
44.00
25.13
48,20
44.00
21.48
49.27
(1.85)
(3.85)
(8.81)
(8.23)
(3.77)
(2.54)
Concrete
40
28.63
23.12
31.50
32,00
26.69
33.74
31.00
25.02
36.99
(2.56)
(4.59)
(8.98)
(4.83)
(7.59)
(1.67)
(2.46)
50
(2.76)
32.48
(4.31)
27.90
(7.54)
19.76
20.00
(4.56)
29.26
(5.37)
21.36
20.00
(3,23)
28.66
(2.91)
28.54
30.33
20.00
60
13,00
12.00
(3.50)
(4.89)
(6.62)
(4.65)
(4,81)
(3.90)
(3.59)
Table 4 shows the results of comparison experiments. Specifically, to be able to establish a con- nection between our studied RcR and selective regression, we set the expected rejection rate (Rj) of the selective regression method based the results of 3cR_MAE (our surrogate loss equipped MAE). It is important to note that there is no way to perfectly match the rejection rate, as the set Rj is "expected". In addition,
show plots of the variation in AL loss for all methods with different rejection rates Appendix D.7. As can be seen Table 4, our proposed method outperforms (smaller AL loss with the same rejection rate) almost all compared methods, which validates the effectiveness of our method.
6 Conclusion
In this paper, investigated a novel regression problem called regression with cost-based rejection, which aims to learn a model that can reject predictions to avoid critical mispredictions at a certain rejection cost. In order to solve this problem, we first formulated the expected risk for regression with cost-based rejection and derived the Bayes optimal solution for the expected risk, which shows that should reject instances where the variance variance is difficult to obtain, we proposed a surrogate loss function that considers rejection as binary classification. Further, we provided conditions for the consistency of our method, implying that the optimal solution can be recovered by our method. Finally, we derived the regret transfer bound and the estimation error bound for our method and conducted extensive experiments on various datasets to demonstrate the effectiveness of our proposed method. We expect that our first study of simple yet theoretically grounded method for regression with cost-based rejection can inspire more interesting studies on this new problem.
greater than the rejection
Since the
10

---

Acknowledgements
Lei Feng supported by Chongqing Overseas Chinese Entrepreneurship and Innovation Support Program, CAAl-Huawei MindSpore Open Fund, and Openl Community (https:/openi..cl. en). Bo An is supported by the National Research Foundation, Singapore under its Industry Alignment Fund Pre- Prsiiioigin (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.
References
[1] P. L. Bartlett, M. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):188-55, 2006.
[2] L. Bartlett and Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of the American Statistical Association, 3:463 482, 2002.
[3] P. I.. Bartlett and M. H. Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 98). 2008
[4] E. Beede, E. Baylor, F. Hersch, A. Turchenko, Wilcox, P. Ruamviboonsuk, and L. M. Var- doulakis. A human-centered evaluation of deep learning system deployed in clinics for the detection diabetic retinopathy. In CHI, pages 1-12, 2020.
[5] R. K. Bellamy, K. Dey. M. Hind, S. C. Hoffman, S. Houde, K. Kannan, P. Lohia, J. Martino, S. Mehta, A. Mojsilovic, et al. Ai fairness 360: An extensible toolkit for detecting, understand- ing, and mitigating unwanted algorithmic bias. arXiv preprint arXiv: 1r10:0:810001944 2018.
[6] Y. Cao, T. Cai, L. Feng. L. Gu, J. Gu, B. An, G. Niu, and M. Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In NeurIPS, pages 521-534, 2022.
[7] I. Chalkidis, I. Androutsopoulos, and N. Aletras. Neural legal judgment prediction in english. In ACL, 2019.
[8] N. Charoenphakdee, Z. Cui, Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. In ICML, pages 1507-1517, 2021.
[9] K. Chaudhuri, P. Jain, and N. Natarajan. Active heteroscedastic regression. In ICML, pages 694-702, 2017.
[10] C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970.
[11] C. Cortes, G. DeSalvo, and M. Mohri. Boosting with abstention. In NeurIPS, 2016.
[12] C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. In ALT, pages 67-82, 2016.
[13] D. Dua and C. Graff. UCI machine learning repository, 2017.
[14] R. El-Yaniv al. On the foundations of noise-free selective classification. of Machine Learning Research, 11(5), 2010.
[15] J. Finocchiaro, R. Frongillo, and B. Waggoner. An embedding framework for consistent poly- hedral surrogates. In NeurIPS, 2019.
[16] V. Franc and Prusa. On discriminative learning of prediction uncertainty. In ICML, pages 1963-1971,201
[17] A. Gangrade, A. Kag, and V. Saligrama. Selective classification via one-sided prediction. In AISTAYS, pages 2179-2187, 2021.
[18] W. Gao and 7.HH. Zhou. On the consistency of auc pairwise optimization. arXiv preprint arXiv:1288.064 2012.

---

[19] Y. Geifman and R. El- Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.
[20] Y. Geifman and R. Ylniv,.v. Selectivenet: deep neural network with an integrated reject option. In ICML, pages 2151-2159, 2019.
[21] X. Geng, C. Yin, and Z.-H. Zhou. Facial age estimation by learning from label distributions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(10):2401-2413 2013.
[22] Y. Grandvalet, A. Rakotomamonjy, J. Keshet, and S. Canu. Support vector machines with reject option. In NeurIPS, 2008.
[23] Grigorescu, B. Trasnea, Cocias, and G. Macesanu. survey of deep learning techniques for autonomous driving. Journal of Field Robotics, 37(3):362-386, 2020.
[24] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In ICML, pages 1321-1330, 2017.
[25] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[26] C. M. Jarque and Bera. Efficient tests for normality, homoscedasticity and serial inde- pendence of regression residuals. Economics Letters, 6(3):255-255 2599, 1980.
[27] W. Jiang. Y. Zhao, and Z. Wang. Risk-controlled selective prediction for regression deep neural network models. In IJCNN, pages 1-8, 2020.
[28] M. A. Kadampur and S. 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: 10088,, 2020.
[29] K. Kersting, C. Plagemann, P. Pfaff, and W. Burgard. Most likely heteroscedastic gaussian process regression. ICML, pages 393-400, 2007.
[30] M. Lázaro-Gredilla and M. K. Titsias. Variational heteroscedastic gaussian process regression. In ICML, pages 841-848, 2011.
[31] J. K. Lee, Y. Bu, D. Rajan, P. Sattigeri, R. Panda, S. Das, and G. W. Wornell. Fair selective classification via sufficiency. In ICML, 2021.
[32] H. Liu, Y.-S. Ong, and J. Cai. Large-scale heteroscedastic regression via gaussian process. IEEE Transactions on Neural Networks and Learning Systems, 32(2):708-721, 2020.
[33] A. L. Martel, Nofech-Mozes, S. Salama, Akbar, and M. Peikari. Assessment of residual breast cancer cellularity after neoadjuvant chemotherapy using digital pathology [data], 2019.
[34] A. Maurer. A vector-contraction inequality for rademacher complexities. In ALT, pages 17, 2016.
[35] S. Moschoglou, A. Papaioannou, C. Sagonas, J. Deng, I. Kotsia, and S. Zafeiriou. Agedb: The first manually collected, in-the-wild age database. In CVPRW, pages 1997-2005, 2017.
[36] C. Ni, Charoenphakdee, J. Honda, and M. Sugiyama. On the calibration of multiclass classification with rejection. In NeurlPS, 2019.
[37] T. Pietraszek. Optimizing abstaining classifiers using analysis. In ICML, pages 665-672. 2005.
[38] A. Pugnana. Topics in selective classification. In AAAI, pages 16129-16130, 2023.
[39] H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classifi- cation with reject option. arXiv preprint arXiv: 04137, 2015.
[40] H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classifi- cation with an abstain option. Electronic Journal of Statistics, 12(1):530-5544 2018.
12

---

[41] A. Shah, Y. Bu, J. K. Lee, S. Das. R. Panda, P. Sattigeri, and G. W. Wornell. Selective regres- sion under fairness criteria. In ICML, pages 19598- 19615, 2022.
[42] B. W. Silverman. Some aspects of the spline smoothing approach to non-parametric regression curve fitting. Journal of the Royal Statistical Society: Series B (Methodological), 47(1):1-21, 1985.
[43] H. White. A heteroskedastiiityycossister covariance matrix estimator and a direct test for heteroskedasticity. Econometrica: Journal of the Econometric Sociery, pages 817-838, 1980.
[44] Y. Wiener and El-Yaniv. Pointwise tracking the optimal regression function. In NeurIPS, 2012.
[45] M. Yuan and M. Wegkamp. Classification methods with reject option based on convex risk minimization, Journal of Machine Learning Research, 11(1), 2010.
[46] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, pages 20073-20083 2020.
[47] T. Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct)::125-1))) 1251, 2004.
[48] Y. Zoabi, S. Deri-Rozov, and N. Shomron. Machine learning-base prediction of covid-19 diagnosis based on symptoms. npj Digital Medicine, 4(1):1-5, 2021.
13

---

A Proof of Theorem 2
For an instance æ, have the following expected risk for æ:
(n = Bp(y(a) (,,,,
= / (1,,,))((
If we refuse to make prediction for æ, i.e., r(æ) < 0, the above expected risk transforms into the following equation:
(Rcc)).)())<00111) ((,,,))
p(y)))c(x)dd
= c()).
When we make a prediction for æ, i.e. r(æ)) > O, the above expected risk transforms into following equation:
(R)) / (1,,,,
(h(x))(((z)) dy
(h)x)) 2yh(xx) ydy
p(ul=)h(x)) / p(ul p(uvlx)22 22y12)) I plulz)y?dy
1²(x)) 2h(x)) [v] + E 18
h²(x)) 2h(w Eptn/ [v] + E 1 + ppl
(h(x)) Ep(a) (w]) [p)
(p))) [y] minimum. It is easy to know that RReR/a (()))) R when c(x) - [Pp() m) [v] > 0 and (Re))a,(()>> (ReR when c(x)- Dp(ola) (v] < 0 which means that RReR is minimum when the following equation holds.
When h(x)) Epi [v] makes ( TD
r" r"(x) II(c(x) Dp(xl=) (v]).
The proof is completed.
14

---

B Proofs of Consistent and Calibration
B.1 Proof of Theorem 5
First, we prove that the optimal regressor ht is also optimal regressor for R RoR
follows.
( rr)
Bpla.w) r. (,,,,,,,))
Eptans) [h' (x)
S p(z, |t
p()))(h"(x>² / 2yh (2) h -
p(x))(1)(==² 2h (x) E (()))))))))))++
p(x))(11(<=) - 2h (1x(2) (x) w
Pp (n)) (())))))))((())))))((()((((()))) (())))
p(=))((1(())* -Ep()l)) 12) + (ro -1 + (()) +
(12)
where (x)) Bayla) [u] makes the above risk minimal when Vo E X, {(r(x), 2 0, and thus h' an optimal regressor for RR with any rejector r. On the other hand, we prove that ht the only optimal regressor if the condition: Vo E X. ((r(x),))) z) > 0 is achieved.
First we prove that h* is not the only optimal regressor when the condition: Va X, ((r()), =) is achieved by contradiction. Specifically, we assume that there is at least one other regressor that makes risk minimize. Suppose given an instance Dg and rejector r' such that ((r'(zo), 1) 0, hence we have at least one other regressor / such that R (h', (h',r') = Ai (h" (h*,r') and h (xxo +f h" (xx) due to the following equation holds:
D pp(plzo) (y (g) (xo), 1)
(13)
The above equation implies that there exist multiple regressors that minimize the risk when the condition: Va: E X, f(r(x), =) 2 0 is achieved. This is mainly due to the binary classification easily know that h² is the only optimal regressor when the condition: Va E X, ((r(#), > 0 is achieved, since there are no ignored terms in Eq. (12). Li
loss ((r(x), 2) O. However,
B.2
Proof of Theorem 6
Let us go back to the discussion of Eq. (12):
Re (h*, = / [((()(00)) Eppela) [v]) + Poole) -1) + + (1)p(()
f Pp(ll)) ()(((())))))))))))))))))())))) 1)p(2) c())
Similarly to the proof of Theorem 5, the optimal regressor h still minimizes the risk for any re- jector. However, it is easy to know that for rejector To when there exists instance Wy such that
((r((x)), -1) 0, there exists at least one other regressor h such that R& (h', r') R ReR (h' r') and 1 ((())) * h (ma) due to ((h(x)² Ep(s/ar) [2])² (p(vla) [v)))(((()) -1) = 0 always holds. Therefore, the optimal regressor ht* not the only optimal solution. Fortunately, we can still show that it is regressor-consisten for some instances in this case.
15

---

For binary classification loss function f, we denote by X3 the space where Vz E X.. [(((x), -1) o 0 for any rejector r. worth noting that when ((r(z), = we can infer r(x) < O, which means that the instance a will be rejected. Then we have the following equation:
RoR (h, = / [((h(z)) - Bp(l))) Poll=) (ill) + ((2))(((())++))p(
x
Jxg (h(x)) pl [v)) ()p()))
x3
/ D
()) +
xg When for all X2 we have the above risk minimised when h((z) = Ex) [y] for all X/- In this case, we obtain similar form as the proof of Theorem 5. Therefore, we have proved that hg is consistent (i.e., hi Itt) for accepted instances when the loss l non-negative. The proof completed.
B.3 Proof of Theorem 7
By fixing the optimal regressor h"," let us discuss the pointwise version of Eq. (12): Ep(sta) (M r; c, az v)] [u) ((((x)) -1) c(x))((((x) +1).
The rejector r(æ:) that minimizes the expected value is given by
min ID (u) - 1) + c<=)((((m))++1)
r(x)
If the binary classification loss (r(()) 2) is classification-calibaaedd then it is easy to see that the optimal rejector r. should have the same sign with Pr((=)(y] c(x) by the definition of classifi- cation calibration. When [Pp(laa)l)) [v] < c(xr), the optimal rejector r (a) must have positive sign, and when Dy( [v)) 2 c(x), the optimal rejector r (a) must have a negative sign. The proof is completed.
C Proofs of the Regret Transfer Bound and the Estimation Error Bound
C.1 Proof of Theorem
Proof. Without loss of generality, we discuss the regret transfer point æts conditional risk and can be generalized to the whole distribution using Jensen's 's inequality of concave functions. We denote by = [ using margin loss f. thus we denote by E(a, -1) = o(a) and l(a. -1) = ó(a).
Em(..)) [((x)) - ?) a = r(x)), and c = c(x). Notice we are
=
Then we can denote our conditional risk as R(D,a) Di((-)())))))))) cá(()), where \ a:) RRER (h, r). According to our previous discussion, R(D, a) achieves its minimum at (D, a²), where a" = argmin, eR DØ( a)) + cạ(a). We can learn that D 2 D. Then we can write our point-wise regret as:
R(D,a) - RRD, a²) = DΦ(-a) + cΦ(a) - Dő(-a") - cΦ(a")
Then we can begin our proof. There are three cases that the point-wise regret of our target loss is non-zero:
When D c but < 0, the point-wise regret of target loss is D.
In this case:
R(D,a) R(D,a') = ( Dō(-a") cá(a")
2 Dá(-a) + cá(a) - Dé(-a") - cá(a")
2 (D+ c)
D+c ol ((-a)++ + o(a)=
D
0l "(-aa))
D D+c )(a')
c
D+c
D+c
C-D
2 (D+c)5-1
D+c)
16

---

When D > but 2 0, the point-wise wise regret of target loss is D
In this case, denote by x" = argmin R(D, a), we can learn that R(D,a") S R(D,
R(D,a) R 2 ((D,,))R(D,d)
-io(-a)) + cő(a) Dé(-a') - cō(ā")
2 DΦp-aa a) + cΦ(l) DØ(--a) - cá(á")
D
2 (D + +c)
o( ((-a)
+ aa))
((aa) c
o(ā"))
D+C
D+c
D+c
D D+c
D D-c
2 (D+c)5
D D++c)
When D < and a 2 0, the point-wise regret of target loss is Đ - D. In this case, we should notice that a² > O. We further split this case into cases:
When D > c, a < 0:
R(D,a))((DDe)
(²) ( oo(() -=(-a))---0 cpfaa)
-Dó(-a)+ + co(a)
+ Dō(-ā") + cō(ā") - Dő(-a") co(a")
2 (Do(-a) + cδ(a) - DØ(-a") - -bb(a") + (Do -D)((=a)==))))
cō(ā') -c(ā"" Dō(
cσ(a"))
D D-c
c- D
2 (D+
+ + - +D++c) c)5-1
D-c
D+c)
When D < c, we can learn a" > 0 denote by a' = argmin, DΦ(a) + DØ( (a), and we can learn a' 2 0:
R(D,a) a) R(D,( De(-a) cō(a) - Dē(-a') cō(a")
2 ~ + oap(a") - Dib (o((-a)) - eppla")
2 ( + c)
b+c) +( (D+c))
D (+c))
c
Notice that for sigmoid loss and hinge loss, (a) |a|. H(a) 2(1 a). For logistic loss, --1 = _ and (a) = a log(a) - (1 - a) log(1 - a). Denote by y the point-wise regret of target loss. Using the linear bound of sigmoid loss and hinge loss we can learn:
((D,a) 27 7.
For logistic loss, the derivation is more complicated. In the first two cases:
- 2 2 )
D+c ( 7
-(D,)*()))))))) ) 2 7. In the third case, we can learn:
and thus
D c
[ -
2 D c D
R(D,a) - -)D,)))(()a'">
+ 2 D
2
D D+cc
> c))+c)
(D) ((--c)²
3 + (c ())
+c)
(Ō D)2
4(D cc)
17

---

and thus 2 2 R(D,a*)) 2 7 In the last case:
- -(D,,))R((,a")) 2D +c)H
C
+ +(++c)
c D+c)
D+c)
D
D D+c
2 -clog
-Dlog
+ +clog (
+ +Dlog
D+c)
D+c
D D-D
(1+ - - -Dlog (1+ C )T)
clog
1
+ Dog
D DC
D-D
2 clog
1+ D+c
D-D D+c
20
D-D
D+C
cD D)
D+c
c+c
Ò D
2
Combining these cases, can learn
7 (a) - R(D,a")), (M + +c)(R(D,a) - R(D,a*))).
C.2 Proof of Theorem
Definition 10. (Rademacher complexity) Let Z..... Zn be n i.i.d. random variables drawn from a probability distribution μ and {f Z + RJ be class measurable functions. Then the expected Rademacher complexity of function class F is given follows:
Rr (F) Ez, Ba sup E o.f
(14)
t=1
where "1, on the Rademacher variables that take the value from {-1, +1} uniformly.
Then begin proving Theorem 9.
Proof. Suppose that the binary loss bounded by Mj and p-Lipschitz continuous, [h], c(z), lyl bounded by M2 and the hypothesis space H. and R is strong enough, then we learn that the total loss is bounded by C (4M3 + M2) and is Lı-Lipschitz continuous w.rl. (h, r), where L = (4M3p p + M3. By applying the McDiarmid's 'ss inequality, it is routine to show that the following inequalities hold with probability at least 1 I respectively:
log 2
sup h.rEHR
(RROR(hs (h, - RR (h,
sup A.EEHR
(R (h, R (h.
+ +01
2n
log 2
sup h.EERR
(Rt (h, Re (h,r))
sup h.ERH
(h, Re (lfcc(()
+
2n
By applying Talagrand's contraction lemma [34], learn that:
E 11 2
sup H.
(fe (fetia(hhr)) Bhan(t.)r)) <
Rr, (R)))
18

---

and this conclusion also holds for another direction. Plugging this conclusion into the former in- equalities and using the union bound, we can learn this inequality holds with probability at least
1 - 8:
log
Rec (h, RRen (h, (h) S (22, + +R) Ci
sup
2n
According to the definition of empirical risk minimization and identifiable condition, we can get the following conclusion:
R (
min R (h,r) ) PRicah,, R (h,, r*) N.E. [RROR =(RROR ReR ()
( (), + (AROR (Ro AROR (h" (r(r)))))))))))))
(RROR("., (0"),,")--)))))rr))" (""") ARRR (h", (h,,,") ,7-))
(Rien(h, (h,
R (h, (h, + (RReR(h" ,,²) Rict R (h" (hr),,))))))))){)))
2 sup h,
R ReR (h, R (h,
Combining Theorem we can conclude the proof.
Table S: Test performance (mean and std) of our surrogate loss equipped hinge loss on BreastPathQ. We repeat the sampling-ane aappling-and-rrininn process 5 times. The metrics Rej, AR, RA scaled to 0-100 and Sup, ReRLoss, AL, and RL all magnified by factor of 1000.
Cost
Sup
Rej
AL
RL
Rej
RA
4.74
3,51
53.05
80.86
60.37
4.19
(0.38)
(1.96)
(20.33)
(4.17)
(6.70)
(2.36)
8.32
4.58
58,90
68.99
46.63
5,91
10
(0.21)
(1.74)
(13.15)
(4.71)
(6.45)
(2.54)
11.89
49.42
62.45
15
16.77
(0.31)
(1.82)
(8.12)
(4.76)
(5.12)
(3.84)
(1.22)
15.07
9.53
49.58
52.33
38.04
17.88
(0.33)
(1.15)
(8.10)
(3,94)
(3.47)
(5.36)
16.54
10.36
58.39
41.23
29.71
25.34
(0.78)
(2.39)
(19.85)
(8.36)
(7.36)
(12.36)
Table 6: Test performance (mean and std) our surrogate loss equipped hinge on AgeDB, repeat sampling-and-training process 5 times. The metries Rej, AR, RA are scaled to (-100.
Cost
Sup
Rej
AL.
RL.
Rej
AR
RA
59.99
44.80
177.36
97.30
95.84
1.43
(0.10)
(13.97)
(40.19)
(2.16)
(3.19)
(1.17)
70.24
71.81
185.68
92.41
88.90
4.32
70
(0.50)
(4.61)
(26.75)
(1.20)
(1.75)
(0.74)
79.67
76.43
185.14
87.23
82.63
7.83
(1.40)
(12.86)
(18.51)
(2.08)
(2.63)
(1.88)
100.34
88.71
76.78
166.84
83.43
79.46
11.19
90
(3.73)
(1.08)
(8.93)
(5.90)
(11.01)
(12.07)
(9.13)
96.95
77.02
182.70
84.78
80.39
9.14
(0.67)
(7.46)
(13,20)
(6.77)
(7.29)
(5.49)
104.29
85.84
192.05
73.52
67.73
17.41
110
(0.31)
(6.98)
(26.75)
(10.39)
(10.33)
(9.56)
111.54
92.59
186.50
67.31
61.11
21.74
(2.23)
(4.79)
(13.73)
(11.60)
(11.56)
(10.43)
19

---

Table 7: Test performance (mean and std) of surrogale loss equipped logistic loss five UCI datasets trained with the Linear model. repeat the caapling-and-triinee process times. metrics Rej. AR, and RA are scaled to 0-100.
Darasets
Cost
Supervised
Rej
AL
RL
Rej
AR
44.76
(0.08)
(0.21)
(1.06)
(2.66)
(3.45)
(1.93)
2.99
2.39
27.94
Abalone
4.92
(0.11)
(0.19)
(1.44)
(2.78)
(3.02)
(2.83)
(0.51)
3,38
2,80
11.78
25,90
18.43
46.24
(0.18)
(0.25)
(1.86)
(2.27)
(2.08)
(3.20)
3.69
3.19
13.81
17,80
11.89
55.08
(0.26)
(0.31)
(2.00)
(1.98)
(1,45)
(4.19)
8.83
7.55
26.44
85.58
78.07
7.24
(0.35)
(2.64)
(1.99)
(6.10)
(8.53)
(3.99)
11.31
8.76
27.39
79.93
71.90
9.74
12
(0.49)
(2.18)
(2.06)
(3.65)
(5.57)
(1.97)
14.46
10.90
30.60
69.47
60.88
17.14
Airfoil
16
23.32
(0.51)
(1,46)
(2.13)
(6.49)
(7.17)
(5.66)
(1.54)
17.10
13.01
33.51
$8.54
50.38
26.19
20
(0.83)
(1.79)
(4.17)
(5.07)
(5.67)
(6.54)
19.62
15.95
35.26
39.30
34.28
47.29
25
(1.26)
(2.52)
(3.40)
(5.76)
(5.41)
(8.82)
20.94
17.60
42.36
25,38
21.35
61.14
30
(1.84)
(3.18)
(7.32)
(8.07)
(6.97)
(12.70)
3,92
2.78
13.05
79.87
73.18
15.28
(0.26)
(1.68)
(4.12)
(11.10)
(14.13)
(7.25)
5,73
5.25
17.98
58.97
52.23
32.06
(0.70)
(1.63)
(9.69)
(10.05)
Auto-mpg
11.66
6.73
5,72
21.58
42,56
36.08
43.16
(0.52)
(0.92)
(7.67)
(7.84)
(8.66)
(11.24)
7.37
5.94
26.05
31.28
25.72
51.96
(0.95)
(1.61)
(11.45)
(12.77)
(10.98)
(21.76)
8.75
7.72
28.93
19.62
17.31
69.71
(1.64)
(1.94)
(12.64)
(4.69)
(4.60)
(13.77)
8.65
6.95
33.87
67.92
58.56
19.28
(0.75)
(3.16)
(12.62)
(14.04)
(7.94)
10.27
8.19
40.93
58.32
48.25
23.32
Housing
(1.08)
(2.90)
(16.74)
(10.20)
(13.11)
(5.75)
(5.34)
12.34
9.20
50.31
45.35
36.24
31.42
(1.14)
(2.03)
(19.14)
(6.04)
(6.00)
(6.77)
14.19
10.48
55.08
38.42
32.22
42.45
(1.67)
(2.72)
(23.26)
(6.08)
(6.62)
(12.64)
19.80
10.00
204.20
97.57
95.25
1.55
(0.29)
(6.44)
(63.34)
(2.04)
(4.29)
(0.86)
29.51
24.08
227.13
91.17
87.60
6.02
(0.92)
(12.35)
(99.54)
(4.57)
(6.54)
(3.11)
Concrete
111.12
38.09
28.95
282.98
80.34
73.83
12:05
(8.01)
(1.38)
(7.18)
(96.63)
(6.60)
(7.46)
(6.39)
46.94
34.22
242.13
75.34
68.94
15.98
(1.82)
(9.57)
(98.34)
(10.15)
(11.79)
(7.51)
51,96
41,36
370.24
56.26
45.96
25.26
(2.08)
(5.76)
(113.24)
(2.61)
(2.24)
(4.63)
Additional Information of Experiments
D.1 Evaluation Metrics
We describe in detail all the evaluation metrics we used in our experiments.
ReR loss. The ReR loss (RcRLoss) is the main evaluation metric for RcR. For given example (x. y) and the rejection cost c(x), the ReRLoss defined as if r(x) > 0, C(h,r, x. y) = (h(x))
2 otherwise C(h, C, a. 2) c(x=).
Rejection rate. The rejection rate (Rej) defined as >n [0( of our model the test dataset.
Rej indicates the rejection rate
20

---

Table 8: Test performance (mean and std) of surrogate loss equipped logistic loss five UCI datasets trained with the MLP model. We repeat the Sampling-and-traan process 10 times. The metrics Rej. AR, and RA are scaled to 0-100.
Datasets
Cost
Supervised
Rej
AL
RL
Rej
AR
RA
2,41
1,95
8.34
43.14
33.37
33,32
(0.10)
(0.18)
(0.87)
(2.84)
(3.34)
(2.81)
2.87
9.68
41.96
4
Ahalone
4.44
(0.18)
(0.29)
(1.18)
(3.28)
(3.29)
(3.29)
(0.46)
3.20
2.59
10.86
25.25
17.86
45.15
5
(0.20)
(0.29)
(1.34)
(2.15)
(2.02)
(3.61)
3.48
2.82
11.54
20.44
14.74
51.48
(0.25)
(0.35)
(1,53)
(1.72)
(1.42)
(4.63)
6.78
5.05
51.45
43.68
20.35
23.75
9
(0.47)
(0.82)
(4.32)
(5.19)
(5.21)
(3.96)
7,96
5.79
59.74
35.05
12.94
26.90
12
(0.64)
(0.82)
(3.53)
(3.02)
(2.79)
(3.03)
9.04
7.46
68.20
18.57
7,36
48.00
Airfoil
16
12.96
(0.56)
(0.47)
(10.78)
(4.08)
(3.14)
(7.21)
(2.60)
9.64
7.81
74.27
15.05
5.83
47,91
(0.74)
(0.44)
(10.19)
(7.76)
(1.91)
(11.27)
10.47
8.50
80.28
12.03
49.00
25
(1,08)
(0.52)
(27.67)
(4.43)
(1.89)
(17.65)
10.95
8.95
89.30
9.50
2,93
50.67
30
(1.11)
(0.78)
(31.58)
(3.86)
(1.10)
(18.37)
3.85
3.22
11.99
62.44
$4.18
25.19
4
(0,56)
(1,51)
(3.81)
(10.72)
(9.53)
(13.29)
5.33
4.67
15.08
43.01
35.19
41.25
6
(0.82)
(1.36)
(3.83)
(16.01)
(16.09)
(15.35)
Auto-mpg
8.34
6.53
5.86
19.34
29.49
23.19
53.57
(2.16)
(1.18)
(1.53)
(7.60)
(13.45)
(13.60)
(14.78)
7.06
6.42
21.71
17.95
14.15
65.59
10
(1.60)
(1.11)
(8.88)
(3.63)
(11.17)
7,80
7.04
28.55
13.59
11.05
70.15
(1.90)
(2.09)
(14.96)
(5.35)
(5.32)
(14.83)
8.60
8.43
45.60
26.57
66.95
9
(2.49)
(3.15)
(27.02)
(5.78)
(5.63)
(10.39)
9.50
8.63
63.52
25.44
17.38
$2.68
12
Housing
12.57
(1.56)
(2.10)
(26.15)
(6.43)
(5.84)
(12.58)
16
(3.43)
9.30
90.19
62.99
(1.37)
(1.70)
(38.08)
(4.30)
(3.87)
(9.05)
9.67
8.33
103.55
11.18
8.71
70.06
20
(1.40)
(1.77)
(54.73)
(2.97)
(2.70)
(8.59)
18.65
14.32
58.33
68.93
$7.72
16.19
(1.41)
(4.80)
(15.88)
(13.47)
(17.08)
(9.45)
25.64
23.16
80.43
32.85
19.30
48
30
(2.50)
(4.95)
(14.47)
(12.82)
(10.81)
(15.91)
Concrete
34.44
29.79
25.25
107.54
30.24
19.97
44.38
(3.05)
(2.33)
(3.55)
(22.18)
(8.58)
(7.91)
(9.87)
31.63
25.79
120.02
24.22
15.29
47.42
50
(4.29)
(4.22)
(24.12)
(11.22)
(10.47)
(10.35)
34.04
33.26
165.71
2.77
2.14
92.59
60
(4.48)
(4.55)
(62.18)
(5.13)
(2.93)
(12.85)
Accepted loss. The accepted loss (AL) is defined as average loss of our regressor on the accepted test dataset.
Di (M( En [[((2))50
AL denotes the
Σn (S((a))) Ln 11(2))50
Rejected loss. The rejected loss (RL) is defined as average loss of regressor the rejected test dataset.
RL denotes the
False rejection rate. The false rejection rate (AR) is defined as Σn (cd AR denotes the rate of instances that should be accepted that are rejected.
21

---

Table 9: Test performance (mean and std) surrogate loss equipped logistic loss BreastPath We repeat sampling-and-training process times. The metrics Rej. AR, are scaled to 0-100 and Sup,
ReRLoss, AL and RL are all magnified by a factor of 1000.
Cost
Sup
RcRLoss
AL
RL
Rej
AR
RA
4,41
2.92
35.59
71.56
47.48
5.71
(0.35)
(1.51)
(7.36)
(3.20)
(5.95)
(3.02)
7.99
4.72
41.34
61.72
40.69
10.30
(0.47)
(1.01)
(9.74)
(9,54)
(4.90)
(1.02)
16.77
11.52
42.67
50.48
35.50
20.18
15
(1.22)
(0.36)
(1.36)
(5.87)
(5.85)
(4.61)
(7.72)
13.69
8.92
63.51
43,65
31.11
22.61
(0.81)
(1.05)
(49.02)
(5.24)
(5.00)
(5.72)
16.64
12.96
35.27
29.84
23.63
44.77
25
(0.94)
(2.28)
(2.63)
(5.93)
(5.42)
(10.54)
Table 10: Test performance (mean and std) of our surrogate loss equipped square loss on BreastPathQ. We repeat the sampling-and-tranniinn training process times. The metries Rej. AR, RA scaled to 0-100 and Sup, ReRLoss, and RL are all magnified by a factor of 1000.
Cost
Sup
ReRLoss
AL
RL
Rej
AR
RA
4.67
3.60
36.70
69.23
44.09
6.26
(0.41)
(1.17)
(4.46)
(4.94)
(4.16)
(3.25)
8.13
5,30
43.66
59.69
37.47
10.42
10
(0.38)
(0.73)
(6.95)
(2.59)
(2.40)
(2.60)
12.02
8.83
39.83
36.78
17.65
15
16.77
(1.09)
(2.14)
(8.27)
(2.56)
(0.80)
(2.03)
(1.22)
14.58
9.66
43.69
44.72
33.20
24.21
(0.57)
(2,55)
(7.58)
(9.54)
(7.89)
(11.09)
15.75
11.98
45.65
27.57
19.94
43.73
25
(0.76)
(2.59)
(7.18)
(8.62)
(7.86)
(12.04)
False acceptance rate. The false acceptance rate (RA) denotes the rate of instances that should be rejected that are accepted, and is defined as >" [[(h(a,))) (a.
E [(h(..)) 2.22)))))))
D.2 Some Results for Hinge Loss
In this section, show some experimental results of the surrogate loss equipped with hinge loss, which can be formulated as follows:
r,,, v. (h(x) max r(=)) + c(xx) r(x)).
Table and Table show some of the experimental results on the AgeDB adn BreastPathQ when surrogate loss equipped hinge loss, respectively. From this table, always lower than Sup in almost all experiments, which means that our method effective in identifying test instances should be accepted and test instances should be rejected. It is worth noting that most experiments, there is a low RA, which means that there a higher tendency to reject hard-to-predie test instances to avoid serious errors when equipped hinge loss.
that ReRLoss and AL
D.3 Some Results for Logistic Loss
In this section, we show some experimental results of the surrogate loss equipped with logistic loss, which can be formulated follows:
+ hh r. x = (h(x) - y) log + exp(r(x))) + c(x))og(11 + exp(-r(x))).
Table 7, Table 8 and Table 9 show some of the experimental results on the UCI datasets and Breast- PathQ when surrogate loss equipped logistic loss, respectively. Our proposed method significantly outperforms the supervised regression method in almost all cases, which verifies the ability of our
22

---

Table 11: Test performance (mean and std) of surrogate loss equipped square loss five UCI datasets trained with the MLP model. We repeat the sampling-and-traime process 10 times. The metrics Rej. AR, and RA are scaled to 0-100.
Datasets
Cost
Supervised
Rej
AL
RL
Rej
RA
2.39
1.96
7.82
42.54
32.79
32.58
(0.10)
(0.19)
(0.63)
(2:49)
(2.69)
(2.63)
2.84
2.35
8.79
31,82
23,72
40.81
Abalone
4.44
(0.16)
(0.25)
(0.97)
(1.87)
(2:14)
(2.77)
(0:46)
3.18
2,60
9.89
25.37
18.32
45.65
(0.18)
(0.27)
(1.15)
(2.13)
(2.07)
(4.21)
6
(0.29)
3.50
(0.42)
2,89
(1.11)
10.40
(2.17)
20.38
14.37
(5.47)
49,83
9
6.40
4.36
$1.93
43.65
22.05
22,22
(0.25)
(0.36)
(5.13)
(3.26)
(2.93)
(3.71)
12
(0.31)
7.46
(0.38)
5.11
(5.83)
61.13
(2.90)
33.75
(3.10)
15.04
(2.74)
27.05
Airfoil
16
12.96
(0.40)
8.57
(0.30)
(7.82)
70:20
(3.23)
(3.08)
(1.79)
(2.60)
9.27
76.90
(0.42)
(0.43)
(10.02)
(2.34)
(1.54)
(4.65)
9.97
7.23
87.37
15.35
5.19
32.96
(0.60)
(0.51)
(9.07)
(2:44)
(1.38)
(5.61)
10.33
7.82
85.67
11.23
3.92
37.40
(0.86)
(0.79)
(18.03)
(1.95)
(1.25)
(8.27)
3,65
2,83
11.93
62.31
51.76
22.05
(0.26)
(0.90)
(3.22)
(11.46)
(12.43)
(10.30)
6
(0.77)
5.19
(1.47)
4,31
(7.69)
18.00
(21,51)
39.62
(21.46)
33.51
(24.43)
47.55
Auto-mpg
8.34
6.51
5.82
22.62
29.10
22,28
52.29
(2.16)
(1.35)
(1.74)
(8.96)
(14.57)
(13.86)
(16.21)
10
(1.16)
6.80
(1.43)
6.08
(9.41)
23.57
(2.84)
17.82
(1.93)
13.91
(9.09)
65.62
7.28
13
(1.30)
(1.36)
(15.46)
(3.74)
(3.46)
(15,70)
(1.56)
(2.10)
(20.25)
(7.81)
(7.35)
(9.38)
9.03
8.36
76.
17.13
12.16
66.75
Housing
12.57
(1.26)
(1.64)
(47.37)
(5.71)
(5.11)
(11.99)
(3.43)
8.52
7.64
109.61
10.10
7.30
73.14
(1.35)
(1.62)
(60.72)
(3.67)
(2.71)
(13.36)
9.40
8.56
148.19 19
7.03
5.09
73.76
20
(1.94)
(2.16)
(98.03)
(3.30)
(16.54)
20
(2.56)
19.95
(5.05)
18.77
(11.68)
75.19
(13.77)
55.10
(14.20)
43.24
(11.92)
28.28
25.22
22.44
103.99
33.45
22.25
43.75
30
(3.22)
(5.34)
(18.06)
(6.93)
(6.21)
(9.93)
Concrete
40
34.44
31.21
28.84
127.77
21.17
12,47
56.12
(3.05)
(1.50)
(1.84)
(19.65)
(5.11)
(4.12)
(7.44)
29.55
147.99
(2.97)
(3.80)
(36.87)
(4.62)
(3.88)
(9.18)
33.07
28.81
158.65
13.64
7.28
59.55
(3.51)
(3.94)
(33.36)
(3.71)
(2.91)
(8.52)
method to reject difficult test instances demonstrating the effectiveness of our method. In most cases, the average loss of our method in the accepted test instances (AL) is always smaller than the average loss of the supervised regression model (Sup) in all test instances. This further indicates the ability of our method identify hard-to-predict samples and reject them. On both MLP and Linear models, our method is effective in avoiding serious errors, which verifies that our method can be adapted to different models.
D.4 Some Results for Square Loss
In this section, we show some experimental results the surrogate loss equipped with square loss, which can be formulated follows:
(h, r. y) = (h(=) -)))))((())))))))))))) + 1)² (rx)(((x))) - -1)
23

---

Table 12: Test performance (mean and std) of surrogate loss equipped sigmoid BreastPathQ. We repeat the saapllingand-traninng process times. The metrics Rej, AR, RA are scaled to 0-100 and Sup, RcRLoss, AL and RL are all magnified by a factor of 1000.
Cost
Sup
Rej
AL
RL
Rej
AR
RA
2.40
43.86
79.22
56.41
2,81
5
(0.17)
(1.01)
(10.60)
(1.54)
(4.19)
(0.92)
8.44
5.09
51.35
69.34
47.12
6.39
10
(0.46)
(1.64)
(7.30)
(2.56)
(3.83)
(1.83)
11.63
6,30
58.40
60.23
41.23
10.88
15
16.77
(0.38)
(1.83)
(14.79)
(6.75)
(5.42)
(5.57)
(1.22)
14.31
8.91
57.83
49.19
33.84
17.31
20
(0.66)
(1.26)
(9.11)
(4.68)
(5.32)
(3.13)
16.61
9.09
95.10
47.38
29.46
17.78
25
(0.60)
(1.53)
(59.42)
(2.92)
(4.84)
(4.73)
Table 10 and Table 11 show some of the experimental results on the BreastPathQ and UCI datasets with MLP model when surrogate loss equipped square loss, respectively. When the rejection cost is small, both ReRLoss and AL significantly smaller than Sup. When the rejection cost is large, ReRLoss and AL are close to Sup but always smaller, which shows the effectiveness of our method to deal with regression with cost-based rejection.
D.5 Some Results for Sigmoid
In this section, we show some experimental results of the Sigmoid function equipped with sigmoid, which be formulated follows:
(h, (h(z) 2) sigmoid((((z)) c( sigmoid(-r(z)))
Unlike other binary classification losses, sigmoid be viewed weight balancing prediction loss and the rejection cost due to sigmoid(r(#z) + sigmoid(-r(z)) experimental results on BreastPathQ when surrogate loss equipped sigmoid, respectively. ReRLoss and AL are always smaller than Sup, verifying the effectiveness of our method.
1. Table 12 show some of the
In experiments, square loss and sigmoid) and different datasets including two deep datasets (BreastPathQ and AgeDB) and five uci datasets (Abalone, Airfoil, Auto-mpg, Housing and Concrete). and our method outperformed supervised regression most cases, which demonstrates the effective our method.
used multiple binary classification losses (MAE, hinge loss, logistic loss,
D.6 Performance of Increasing Training Data
As showed in Theorem 8 and Theorem the pair rh, learned by surrogate loss could converge to the optimal pair (h" r") when the number of training examples approaches to infinity. Therefore, the performance of the model can be improved as the training samples increase. To empirically validate such theoretical finding, we further conduct experiments on the Abalone and Auto-mpg datasets by changing the fraction of training examples (100% means that we use all training examples in the training set). As shown in Figure 2, the RcRLoss and the AL generally decreases when more training examples are used for model training. This observation is clearly in accordance with our theoretical analyses in Theorem 8 and Theorem 9, because the learned model would be closer to the optimal model as more training examples are provided.
D.7 Curves of AL and Rej
We show the AL loss for all methods with different rejection rates Abalone, Autompg and Con- crete datasets in Figure 3. In the plot of the relationship between loss and rejection rate, a curve at the bottom means better results.
24

---

Breast
Abalone
5.0
4
3.2
4.5
Test l055
Test loss
3.0
2.8
2.6
3.0
2.4
20%
40%
60%
80% 100%
20%
40%
60%
80%
100%
20%
40%
60%
80% 100%
Training set size
Training set size
Training size size
(a) Breast with 5
(b) Breast with 10
(c) Abalone with = 4
Abalone
Housing
Housing
16
18
14
8
3.6
3.4
12
10:
10
3.0
20%
40%
80% Training set
60%
60%
100%
20%
40%
100%
Training set size
Training size
(d) Abalone with c = 6
(e) Housing with 12
(I) Housing with = 16
Figure The lest performance on the Breast, Abalone Housing datasets for the surrogate loss equipped MAE when the number of training examples increases.
abalone
Auto-mpg
Concrate
MiP-Pupp
3.0
MPP-
2.6
2.8
fings
Logald
Simool
AL loss
6
7-
Sdictive
Logiet:
Square
Higg
30
hing
Logit
Seacthve
5
2.4
2.2
20
2.0
15
20 25 30
40 45 Rejection rate (100%)
30 Rejection rate (100%)
10 40 Rejection rate (100%)
(a) Ahalone
(b) Autompg
(c) Concrete
Figure 3: Figures (a), (b) and (c) report the accepted loss (AI.) for all methods with different rejection rates on ahalone, auto-mpg and concrete datasets, respectively.
E Limitations
In Theorem 4 and Theorem 5, we show that there a limitation in our proposed method that requires the binary classification loss {(r(x), 2) to be always greater than 0. This is easily satisfied by the design of the binary classification loss. However, to avoid the modification of the binary classifi- cation loss, we further propose Theorem 6, which only requires the binary classification loss to be non-negative, and this easily satisfied. Extensive experiments on various datasets demonstrate the effectiveness of our proposed method. the other hand, use the pointwise cost functions c(x) in our theoretical analysis, which shows that our method can be used for pointwise cost functions. For simplicity, in experiments, we only consider the rejection cost as constant but method can easily handle the various pointwise cost functions different application scenarios.
25


Reviews:
[{"review_id": "qcSoMWyVZ1", "reviewer": "Reviewer_1UF6", "summary": "The paper explores the framework of regression with rejection, in which the model can opt to refrain from making predictions on certain instances at specific costs, with the intention of avoiding critical mispredictions. The paper determines the Bayes optimal solution and introduces a theoretically grounded surrogate loss within the framework.", "questions": "See Weakness.", "limitations": "N/A.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is pioneering in studying the regression with rejection setting.\n2. The presentation of the paper is clear and concise.", "weaknesses": "1. While the regression with rejection setting represents a fresh concept in the literature, the technical approach seems to closely mirror the standard classification with rejection setting. This resemblance potentially limits the novelty of the paper. Could the authors elaborate on the specific technical challenges encountered within this setting?\n\n2. A definition of regressor-consistency that parallels rejector-calibration (Definition 3) is missing. \n\n3. The use of a supervised regression method may not serve as an appropriate and fair baseline for rejection experiments. It would be more convincing to conduct experiments comparing some straightforward rejection methods against the proposed rejection methods.\n\n4. Additional commentary on the experimental results is required. For instance, the setup considers a range of binary classification loss functions; which among these yields the best results based on the experiments conducted?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review!\n\n**Q1: While the regression with rejection setting represents a fresh concept in the literature, the technical approach seems to closely mirror the standard classification with rejection setting. This resemblance potentially limits the novelty of the paper. Could the authors elaborate on the specific technical challenges encountered within this setting?**\n\nA1: Thank you for posing this nice question. We agree that our studied setting of regression with rejection shares some similarities with the setting of classification with rejection (CwR) due to the rejection option, but they are basically targeting two different tasks, i.e., regression and classification. The label space is continuous and infinite in regression while is discrete and finite in classification, which makes the labeling information harder to capture in regression than in classification. As shown in Theorem 2 in our paper, the main technical challenge of regression with cost-based rejection is **how to accurately estimate the variance of the real-valued label $y$ over the distribution $p(y|x)$**. However, estimating the variance without knowing the distribution $p(y|x)$ is difficult, and empirically estimating $p(y|x)$ is also difficult because $p(y|x)$ is unknown and needs to be approximated by a well-performed model. To address these challenges, we propose to a surrogate loss function considering rejection as a binary classification problem and provide theoretical analyses on regressor-consistency and rejector-calibration. There is an evident difference in the technical approach between our work and most of the existing studies on CwR, i.e., our proposed method avoids estimating $p(y|x)$ by taking rejection as binary classification while most of the existing studies on CwR need to accurately estimate $p(y|x)$ for rejection.\n\n**Q2: A definition of regressor-consistency that parallels rejector-calibration is missing.**\n\nA2: Thank you for pointing out this issue. A informal definition of regressor-consistency was provided in Lines 156-157 of our paper, i.e., we say a method is regressor-consistent, meaning that the regressor $h$ learned by the method converges to the optimal regressor $h^{*}$ as the number of training data increases. We will add a formal definition to our revised manuscript.\n\n**Q3: The use of a supervised regression method may not serve as an appropriate and fair baseline for rejection experiments. It would be more convincing to conduct experiments comparing some straightforward rejection methods against the proposed rejection methods.**\n\nA3: Since this question was repeatedly mentioned by reviewers, we think it is very important. We provide a detailed response to this question in Global Response, so please refer to **Global Response** to check the full response. Briefly, since our paper provides the first attempt to investigate regression with cost-based rejection, there does not exist a baseline that can be directly compared, so we propose a number of evaluation metrics and conduct extensive experiments to verify the validity of our method. However, this does not seem to be convincing enough, so we have adopted the suggestions of reviewers to add comparisons with the methods in selective regression [19, 41] to make our experimental results more convincing. Based on the comparison of accepted loss (AL), our proposed method outperforms (smaller AL with the same rejection rate) all compared methods, which validates the effectiveness of our method.\n\n[19] Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.\n\n[41] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, 2020.\n\n**Q4: Additional commentary on the experimental results is required. For instance, the setup considers a range of binary classification loss functions; which among these yields the best results based on the experiments conducted?**\n\nA4: Indeed, we found that different binary classification loss functions (e.g. mean absolute error, mean square loss, logistic loss, sigmoid, and hinge loss) perform differently on different datasets. For example, hinge loss and sigmoid have similar performances on the BreastPathQ dataset, but sigmoid loss performs better than hinge loss on the AgeDB dataset. Our experimental results show that the performance of MAE is more stable (no excessively high or low rejection rate), compared with other loss functions."}, {"review_id": "9lkm8rKF0p", "reviewer": "Reviewer_4Fnw", "summary": "This paper focuses on the problem of regression with rejection, specifically the approach of specifing a cost function and learn the pair of regressor and rejector at the same time. The paper prensents a concrete path to solving the problem. It first properly defines the problem and shows the Bayes optimal solution to it. Since the Bayes optimal solution requires knowing the expectation and the variance of the underlying distribution, it then proposes a learnable risk defined using surrogate loss function. Then, the paper theoretically investigate and show the usefullness of the proposed approach, from the perspective of classification calibration and error bound. Finally it empirically evaluates the proposed method on several typical datsets using various metrics.\n", "questions": "- For the cost funciton $c(x)$, it is used as a function on $x$ instead of a constant in theoretical demonstrations but considered as a constant in experiments. Does theoretical results has some relationship or limitation on the form of the pointwise cost function? Does some results rely on cost being a non-constant function?\n\n- Are there any detailed discussion on the slow-start mechanism, since is part is not covered by any theory but has crucial practical importance? For example, how the slow-start epochs affect the overall performance? Can we completely stop the learning of $h$ after the slow-start epochs?\n", "limitations": "Techinal limitations on loss function are addressed by authors in appendix.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThis paper tackles the regression with rejection problem which is of significant importance in the field. The paper solves the problem from a novel perspective and can be seen as a novel combination of several well-known techniques. This paper addresses clearly how it is related and different from related publications.\n\nQuality:\nThe paper is technically sound and self-contained. Its claims are properly supported by theoretical demonstrations.\n\nClarity:\nThe paper is clearly written and easy to follow. The structual is well organized.\n\nSignificance:\nThe proposed method has significance to some extent, as it considers a new approach to an important problem. ", "weaknesses": "- Empricail comparison is no sufficiently conducted.\n  - There is no comparison with existing methods. \n  - There is no investigation on varying cost.\n  - There is no investigation on slow-start. This would show the robustness of the proposed method, since slow-start introduces a hyper-parameter to the method.\n  - There is no investigation on varying training data size. Some theoretical results shows how performance would change on different $n$. It would be pursuative to show it empirically to some extent.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your valuable comments!\n\n**Q1: There is no comparison with existing methods.**\n\nA1: Since this question was repeatedly mentioned by reviewers, we think it is very important. We provide a detailed response to this question in Global Response, so please refer to **Global Response** to check the full response. Briefly, since our paper provides the first attempt to investigate regression with cost-based rejection, there does not exist a baseline that can be directly compared, so we propose a number of evaluation metrics and conduct extensive experiments to verify the validity of our method. However, this does not seem to be convincing enough, so we have adopted the suggestions of reviewers to add comparisons with the methods in selective regression [19, 41] to make our experimental results more convincing. Based on the comparison of accepted loss (AL), our proposed method outperforms (smaller AL with the same rejection rate) all compared methods, which validates the effectiveness of our method.\n\n[19] Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.\n\n[41] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, 2020.\n\n**Q2: There is no investigation on varying costs.**\n\nA2: We would like to kindly remind that we have already set various rejection costs $c$ for each dataset and performed repetitive experiments. As the rejection cost $c$ increases, the RcR loss and accepted loss gradually increase while the rejection rate gradually decreases.\n\n**Q3: There is no investigation on slow-start. Are there any detailed discussions on the slow-start mechanism? How do the slow-start epochs affect the overall performance? Can we completely stop the learning of $h$ after the slow-start epochs?**\n\n\nA3: In the implementation details of our experiments, we use a training trick called slow-start, where we first only train the regressor $h$ and then train the regressor $h$ and the rejector $r$ together. The slow-start trick is to alleviate the detraining issue in the early training stage when $h$ is disturbed by $r$, especially when deep neural networks with gradient descent optimization are used. Similar tricks were also used in other rejection learning methods [19]. After our preliminary study, the hyper-parameter of slow-start epochs has no significant effect on the experimental results, and we suggest setting it to 20\\% of the total training epochs. It is worth noting that we cannot stop training $h$ after slow-start because slow-start is only used to accelerate the training of $h$ in the early training stage.\n\n[19] Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.\n\n**Q4: There is no investigation on varying training data size.**\n\nA4: Thank you for the wonderful suggestion. We have added additional experiments by varying the sizes of training data. Specifically, we considered using 20\\%, 40\\%, 60\\%, 80\\%, 100\\% of the training set to train our model. The experimental results are reported following table. As can be seen from following table, there is a significant reduction in RcR loss, AL, and Rej, as more training data is used. This is clearly in accordance with our intuition that the performance will be improved if more training data is provided.\n\n| Datasets | Cost | Slice | RR | AL | RL | Rej |\n| :----:| :----: | :----: | :----: | :----: | :----: | :----: |\n| Abalone | 3.0 | 20\\% | 2.81 $\\pm$ 0.16 | 2.15 $\\pm$ 0.55 | 6.51 $\\pm$ 1.30 | 72.31 $\\pm$ 11.12 |\n| Abalone | 3.0 | 40\\% | 2.60 $\\pm$ 0.14 | 2.18 $\\pm$ 0.29 | 8.28 $\\pm$ 1.35 | 51.58 $\\pm$ 10.11 |\n| Abalone | 3.0 | 60\\% | 2.48 $\\pm$ 0.14 | 2.05 $\\pm$ 0.30 | 8.50 $\\pm$ 1.09 | 46.74 $\\pm$ 2.96 |\n| Abalone | 3.0 | 80\\% | 2.45 $\\pm$ 0.13 | 2.03 $\\pm$ 0.24 | 8.22 $\\pm$ 1.16 | 45.66 $\\pm$ 3.83 |\n| Abalone | 3.0 | 100\\% | 2.41 $\\pm$ 0.12 | 1.99 $\\pm$ 0.21 | 8.13 $\\pm$ 1.08 | 42.04 $\\pm$ 3.18 |\n| Auto-mpg | 4.0 | 20\\% | 4.14 $\\pm$ 0.17 | 4.83 $\\pm$ 1.37 | 12.35 $\\pm$ 2.85 | 82.37 $\\pm$ 10.51 |\n| Auto-mpg | 4.0 | 40\\% | 3.91 $\\pm$ 0.27 | 3.19 $\\pm$ 1.28 | 10.73 $\\pm$ 2.96 | 73.97 $\\pm$ 8.43 |\n| Auto-mpg | 4.0 | 60\\% | 4.15 $\\pm$ 0.78 | 3.68 $\\pm$ 2.15 | 11.97 $\\pm$ 2.68 | 69.10 $\\pm$ 12.92 |\n| Auto-mpg | 4.0 | 80\\% | 3.90 $\\pm$ 0.75 | 3.47 $\\pm$ 1.69 | 13.08 $\\pm$ 3.22 | 60.00 $\\pm$ 20.23 |\n| Auto-mpg | 4.0 | 100\\% | 3.64 $\\pm$ 0.29 | 2.99 $\\pm$ 0.83 | 13.98 $\\pm$ 4.16 | 56.92 $\\pm$ 13.00 |\n\n**Q5: Does theoretical results has some relationship or limitation on the form of the pointwise cost function? Does some results rely on cost being a non-constant function?**\n\nA5: In our theoretical analysis, we use pointwise cost functions $c(x)$, which shows that our method can be used for pointwise cost functions. For simplicity, in our experiments, we only consider the rejection cost as a constant $c$, but our method can easily handle various pointwise cost functions in different application scenarios. "}, {"review_id": "yOe4TLOEvJ", "reviewer": "Reviewer_J2H6", "summary": "The paper addresses problem of regression with the reject option. The authors propose the cost-based formulation of an optimal reject-option regression rule and they derive (Bayes) optimal strategy for the case the distribution is known. The authors further propose a surrogate loss to learn the reject-option regression rule from examples. They prove the the consistency and regret bounds for the proposed learning approach.", "questions": "Please explain reasons for not using any baseline method in the experimental evaluation?\n\n---\nThe authors satisfactorily addressed my questions in the rebuttal based on which I increased my ratings.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is sound and it is very clearly written.\n\nThe proposed method based on surrogate loss is simple and potentially effective. \n\nThe authors derive theoretical guarantees for the proposed estimator, namely, they show the consistency and the regret bound.", "weaknesses": "The first contribution, i.e. formulation of the cost-based reject option regression and the optimal solution, is a known result. E.g. it is given in [41], see equation (1) of the paper. Besides [41], deriving the optimal strategy for a generic reject option predictor (of which the regression with L2-loss is a special case) is straightforward and appears in pattern recognition textbooks, e.g. Schlesinger et al. Ten Lectures on Statistical and Structural Pattern Recognition. Springer 2002.\n\nThe proposed method, based on minimizing the surrogate loss, is not compared against any baseline solution nor any existing methods for learning reject option regression. As a result, when there is no reference, it is difficult to judge about efficiency of the proposed method. The minimal solution would be to use synthetic data with known ground-truth. On real data one could use any regression model which outputs estimate p(y|x), like e.g. Bayesian methods, and plugin Bayes rule.  The author may argue that most existing methods formulate the optimal reject-option regression using the concept of selective risk and coverage [41][20][38]. However, all methods (including the proposed approach) can be compared in terms of the selective risk and the coverage which are reported by the authors anyway in the experiments (section 5) although the authors use different terminology. Namely, the selective risk is denoted as the \"accepted loss\" AL and the coverage equals 1 - rejection rate (RR). Note the cost-based formulation and the selective risk vs. coverage formulation (known as the bounded-improvement or bounded-abstention rejection models) are equivalent in the sense that both lead to the same Bayes-optimal solution, i.e. setting the rejection cost (as in the paper under review) has the same effect as setting threshold on the coverage (or the selective risk), see e.g. Franc et al. Optimal strategies for reject option classifiers. JMLR 2023. \n\nMinor problems:\n\n- Regarding the experiments in sec 5, errors observed on AgeDB dataset are excessively large. The mean error ~100, reported for the standard regression model (sup), makes no sense for age prediction regardless whether the authors report MAE or L2-loss which is not clear from the description.\n\n- The observations derived from the experiments (section 5.5) are questionable or trivial: \"(1) Our proposed method significantly outperforms the supervised reression method\" It is not clear in what sense the propsed method is better as it solves a different problem than the non-reject model. \"(2) In most cases, the average loss of our method in the accepted test instances (AL) is always smaller than the average loss of the supervised regression model\"; note that this holds true for any rejection rule regardless how good the rejector $r(x)$ is. Similarly the obsevation (3) is obvious and it hold for any rejection rule.\n\n- Line 273: \"...RcR loss (RcRLoss) decreases\" -> increases", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your valuable comments!\n\n**Q1: The first contribution regarding the formulation of the cost-based reject option regression and the optimal solution.**\n\nA1: We agree that our derived optimal solution of regression with cost-based rejection is quite similar to the result in [41], but we would like to humbly argue that our derived optimal solution is more general and suitable for regression with cost-based rejection instead of selective regression. In [41], equation (1) is derived by introducing the tuning parameter $\\lambda$ which is responsible for compromising error and rejection rate. Hence $\\lambda$ can only be taken as a constant rejection cost. In contrast, our formulation is more general and can be naturally compatible with instance-dependent rejection cost, and thus is more suitable for regression with cost-based rejection. Therefore, despite being quite similar to the result in [41], we believe that our formulation is also meaningful. We admit that the derivation process of such an optimal solution with L2-loss is straightforward, which is also similar to that of [41]. However, since regression with cost-based rejection is a new problem that has not been studied before, it is quite essential to explicitly show the general optimal solution with instance-dependent cost. Thank you for providing us with such an insightful comment and we will properly revise our manuscript according to the above constructive discussionwith you.\n\n[41] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, 2020.\n\n**Q2: Comparison with selective regression.**\n\nA2: Since this question was repeatedly mentioned by reviewers, we think it is very important. We provide a detailed response to this question in Global Response, so please refer to **Global Response** to check the full response. Briefly, since our paper provides the first attempt to investigate regression with cost-based rejection, there does not exist a baseline that can be directly compared, so we propose a number of evaluation metrics and conduct extensive experiments to verify the validity of our method. However, this does not seem to be convincing enough, so we have adopted the suggestions of reviewers to add comparisons with the methods in selective regression [19, 41] to make our experimental results more convincing. Based on the comparison of accepted loss (AL), our proposed method outperforms (smaller AL with the same rejection rate) all compared methods, which validates the effectiveness of our method.\n\n[19] Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.\n\n[41] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, 2020.\n\n**Q3: The cost-based formulation and the selective risk vs. coverage formulation (known as the bounded-improvement or bounded-abstention rejection models) are equivalent in the sense that both lead to the same Bayes-optimal solution.**\n\nA3: Thank you so much for pointing out this conclusion by Franc et al. (2023) that the cost-based and sensitivity (known as the bounded-improvement or bounded-abstention rejection models) frameworks have the same Bayes-optimal solution. The conclusion can help us to theoretically connect different rejection-based frameworks. However, even if different frameworks have the same optimal solution, they actually do not face the same challenges and application scenarios. Selective regression aims to reject with a fixed rejection rate, while regression with cost-based rejection aims to reject with a fixed rejection cost. To the best of our knowledge, we provide the first study on regression with cost-based rejection. We cannot expect the first study (especially the conference paper) to accomplish all relevant tasks, although it is interesting and meaningful to analyze the connections with different rejection frameworks. Therefore, we think it is more appropriate to leave the study of theoretical links between different rejection frameworks for future work.\n\n**Q4: Excessive errors observed on the AgeDB dataset.**\n\nA4: Thank you for pointing out the lack of clarity in the presentation of our table. Specifically, all of our results are based on L2-loss (i.e., Mean Squared Error). We admit that an average error of about 100 even for the standard regression model (sup) on the AgeDB dataset is excessive. In fact, these results are normal without the use of additional training data, and similar errors also have appeared in a previous paper, see e.g. Yang et al. Delving into deep imbalanced regression. ICML 2021.\n\n**Q5: The observations derived from the experiments (section 5.5) are questionable or trivial.**\n\nA5: Thank you for pointing out this issue. We agree with you that these observations seem somewhat trivial because it may not be appropriate to directly compare our work with supervised regression. Our original intention is to show the effectiveness of our proposed method in regression with cost-based rejection. We will properly revise our manuscript for clarifying this part.\n\n\n**Q6: Please explain the reasons for not using any baseline method in the experimental evaluation?**\n\nA6: To the best of our knowledge, our paper provides the first attempt to investigate regression with cost-based rejection (RcR), hence there are no baseline methods for this task. In order to show the effectiveness of our method, we propose a number of evaluation metrics and conduct extensive experiments. However, these results do not seem convincing enough, so we added the comparison experiments with the selective regression method in Global Response. Please refer to **Global Response** to check the comparison experiments.\n"}, {"review_id": "q5uhacbMli", "reviewer": "Reviewer_mRfi", "summary": "Learning with rejection is an important machine learning problem. Most of the existing papers focus on the classification setting, i.e., classification with rejection and selective classification, and seldom works are targeting at the regression setting. This paper aims to investigate regression with cost-based rejection. Although some papers have studied the selective regression problem, I consider that the problem of regression with cost-based rejection is new. \n\nTo solve this new problem, this paper gives a formulation of the expected risk and derives the Bayes optimal solution. To train an ideal model, this paper also proposes a surrogate loss function that regards rejection as binary classification and provides conditions for the consistency. Experiments are conducted to demonstrate the effectiveness of the proposed.\n", "questions": "Compared with the selective setting, what is the key challenge of the proposed setting regression with cost-based rejection? The authors are encouraged to further explain this point.\n\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The problem of regression with cost-based rejection is interesting and new.\n\n- It is quite important to give the formulation of expected risk for cost-based rejection and the Bayes optimal solution is meaningful and significant, which might serve as a pioneer for follow-up works to check whether the derived model and rejector are consistent when the mean squared error is used as the evaluation metric.\n\n- A reasonable approach to training a good regression model with rejection is proposed and theoretical analyses are provided.\n\n- Experimental results are significant, which supports the importance of considering cost-based rejection in the regression setting.\n", "weaknesses": "In Theorem 4, I notice that the authors did not introduce the concept \"classification calibrated binary classification loss\". For this concept, I also think that some references are required, e.g., [1] and [2].\n\n[1] P. Bartlett et al. Convexity, classification, and risk bounds. JASA 2006.\n[2] A. Tewari and P. Bartlett. On the consistency of multi-class classification methods. JMLR 2007.\n\n- I also notice that the first two cited references are repeated. I would suggest that the authors should further check the details of the references.\n\n- I also find some typos in this paper, e.g., missing a right parenthesis in Eq. (2).\n\n- It will be interesting to give a general Bayes optimal solution for arbitrary regression losses, instead of limiting to the mean squared error.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review!\n\n**Q1: The concept of \"classification calibrated binary classification loss\" is missing.**\n\nA1: Thank you for pointing out this issue, which will be very helpful for us to improve our paper. We have rechecked our manuscript and added the concept to the revised manuscript.\n\n**Q2: It will be interesting to give a general Bayes optimal solution for arbitrary regression losses, instead of limiting to the mean squared error.**\n\nA2: We agree that it is interesting and meaningful to give a general Bayes optimal solution for arbitrary regression losses. Since the mean squared error (MSE) is the most widely used regression loss, we only considered the case of MSE in our paper. Besides, if we use another regression loss, the derivation process would be much different and the corresponding optimal solution may be extremely different from that of MSE. Therefore, whether there exists a general Bayes optimal solution is unknown, which is also a huge challenge to be solved in the future. We believe that the study of the Bayes optimal solution for other regression losses or the general Bayes optimal solution will be an interesting research direction for future work.\n\n**Q3: Compared with the selective setting, what is the key challenge of the proposed setting regression with cost-based rejection?**\n\nA3: As shown in Theorem 2 in our paper, compared with the selective setting, the key challenge of regression with cost-based rejection is how to accurately estimate the variance of the real-valued label $y$ over the distribution $p(y|x)$. However, estimating the variance without knowing the distribution $p(y|x)$ is difficult. Unfortunately, empirically estimating $p(y|x)$ is also difficult because $p(y|x)$ is unknown and needs to be approximated by a well-performed model.\n\n**Q4: Miscellaneous minor issues.**\n\nA4: Thank you for pointing out these issues, which will be very helpful for us to improve our paper. We have rechecked our manuscript and corrected the clarity issues in the revised manuscript. For your mentioned issues, we have removed the repeated references. Besides, we have added the missing parentheses to Eq. (2)."}]

Author rebuttal:
## Global Response

We sincerely appreciate the thoughtful feedback and insightful comments from all reviewers to help improve our work. We are glad that our study was recognized by the reviewers (Reviewer 1UF6, Reviewer 4Fnw, Reviewer J2H6 and Reviewer mRfi). We are delighted that they found our work to be novel (Reviewer 4Fnw), interesting (Reviewer mRfi), clear (Reviewer 1UF6), and simple (Reviewer J2H6), and we are encouraged by these positive comments. 

We have corrected all the typos mentioned by reviewers and made the following key changes to our revised manuscript:

[Section 1] We made appropriate modifications to our first contribution regarding the formulation of the cost-based reject option regression and the optimal solution (Reviewer J2H6).

[Section 4.1] We added the definition of regressor-consistency (Reviewer 1UF6) and the concept of class-calibrated binary classification loss (Reviewer mRfi).

[Section 5] We added a comparison with the method of selective regression to demonstrate the validity of our method to make our work more convincing (Reviewer 1UF6, Reviewer 4Fnw and Reviewer J2H6).

[Section 5.5] We revised Section 5.5 to clearly express the validity of our method (Reviewer J2H6).

[Appendix D] We added experiments on varying training data sizes (Reviewer 4Fnw).

[Appendix E] We added a discussion of pointwise cost functions and constant costs (Reviewer 4Fnw).

----------

Below are our responses to the commonest concern regarding the experimental comparison with previous (selective regression) methods. 

**Q: The experimental comparison with previous (selective regression) methods.**

A: Thank you for raising this concern, which will be definitely helpful for us to improve our paper! To the best of our knowledge, our paper provides the first attempt to investigate regression with cost-based rejection (RcR), hence there are currently no direct baseline methods for this problem. So we propose a number of evaluation metrics and conduct extensive experiments hoping to show the effectiveness of our method.

We admit that there are no directly comparable methods for our setting, but we can adopt the suggestions of reviewers to add comparisons with the methods in selective regression. We have conducted additional experiments to compare with SelectiveNet [19] and Knn-Plug [41], and the results are reported in Table 1 and Table 2, respectively (in the attached one-page PDF). Specifically, to be able to establish a connection between our studied RcR and selective regression, we set the expected rejection rate (RJ) of the selective regression method based on the results of RcR\_MAE (our surrogate loss equipped MAE). It is important to note that there is no way to perfectly match the rejection rate, as the set rejection rate (RJ) is "expected". From Table 1 and Table 2, our proposed method outperforms (smaller AL with the same rejection rate) all compared methods, which validates the effectiveness of our method.


Although RcR and selective regression seem to have a lot of similarities, they actually do not face the same challenges and application scenarios. The selective regression aims to reject with a fixed rejection rate, while RcR aims to reject with a fixed rejection cost. In many real-world scenarios, the rejection rate is inaccessible and we can only have the rejection cost. For example, in safety-critical applications such as autonomous driving, we need to predict the most suitable deflection angle $20^{\circ}$ for the tires based on sensor information. However it is not realistic to have a perfect prediction, so we have a tolerance angle of $10^{\circ}-30^{\circ}$ to complete the turn. In such a case, we can easily set a rejection cost $(10^{\circ})$ instead of a rejection rate. Based on such a view, we believe that RcR is worth studying.


[19] Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.

[41] A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In NeurIPS, 2020.

Meta-review: This paper tackles the regression with rejection problem, which is of significant importance in the field. The paper solves the problem from a novel perspective and can be seen as a novel combination of several well-known techniques. This paper addresses clearly how it is related and different from related publications. The paper is technically sound and self-contained. Its claims are properly supported by theoretical demonstrations. The paper is clearly written and easy to follow. All reviewers agree that this is a good paper. Hence, I support acceptance of this paper.
Decision: Accept (poster)