On the consistent estimation of optimal Receiver Operating Characteristic (ROC) curve
Authors: Renxiong Liu
Yunzhang Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Classification
optimal Receiver Operating Characteristic (ROC) curve
Consistency
Model misspecification

Abstract: Under a standard binary classification setting with possible model misspecification, we study the problem of estimating general Receiver Operating Characteristic (ROC) curve, which is an arbitrary set of false positive rate (FPR) and true positive rate (TPR) pairs. We formally introduce the notion of \textit{optimal ROC curve} over a general model space. It is argued that any ROC curve estimation methods implemented over the given model space should target the optimal ROC curve over that space. Three popular ROC curve estimation methods are then analyzed at the population level (i.e., when there are infinite number of samples) under both correct and incorrect model specification. Based on our analysis, they are all consistent when the surrogate loss function satisfies certain conditions and the given model space includes all measurable classifiers. Interestingly, some of these conditions are similar to those that are required to ensure classification consistency. When the model space is incorrectly specified, however, we show that only one method leads to consistent estimation of the ROC curve over the chosen model space. We present some numerical results to demonstrate the effects of model misspecification on the performance of various methods in terms of their ROC curve estimates.

On the consistent estimation of optimal Receiver Operating Characteristic (ROC) curve
Renxiong Liu
Yunzhang Zhu Department of Statistics Ohio State University Columbus, OH 43210 zhu 2190osu. edu
Department of Statistics Ohio State University
Columbus, OH 43210
liu. 1 wtw.677220uuckeymmail.... .su...ssssse.... edu
Abstract
Under standard binary classification setting with possible model misspecification, we study the problem of estimating general Receiver Operating Characteristic (ROC) curve, which is an arbitrary set of false positive rate (FPR) and true positive (TPR) pairs. We formally introduce the notion of optimal ROC curve over a general model space. It is argued that any ROC curve estimation methods implemented over the given model space should target the optimal ROC curve over that space. Three popular ROC curve estimation methods are then analyzed at the population level (i.e., when there are infinite number of samples) under both correct and incorrect model specification. Based on our analysis, they are all consistent when the surrogate loss function satisfies certain conditions and the given model space includes all measurable classifiers. Interestingly, some of these conditions are similar those that are required to ensure classification consistency. When the model space is incorrectly specified, however, we show that only one method leads to consistent estimation of the ROC curve over the chosen model space. We present some numerical results to demonstrate the effects of model misspecification on the performance of various methods in terms of their ROC curve estimates.
Introduction
One common goal in standard binary classification task is find a classifier with minimum misclas- sification eгror, which is the weighted average of the false negative rate (FNR) and false positive rate (FPR). This implicitly assumes that the two types of errors are equally important. In many real applications, however, these two types of errors may need to be treated unequally by assigning asymmetric losses them. For example, in spam email detection, classifying non-spam as spam may incur higher cost than classifying spam into non-spam. Existing methods to handle this problem can be roughly categorized into three groups. Cost-sensitive learning [Elkan, 2001], which generalizes the empirical risk minimization framework [Vapnik, 1991], assigns unequal class weights to the two types of errors and seeks to find a classifier that minimizes the weighted error. Neyman- Pearson classification [Cannon et al., 2002; Scott and Nowak, 2005; Rigollet and Tong, 2011] is another type of method, which aims to minimize one type error (FNR) subject to a upper bound constraint on the other type of error (FPR). We call these two types of methods weighted method and constrained method, respectively. Another popular approach [Fawcett, 2006], which we call cutoff methods, di- rectly constructs the set of classifiers is obtained through changing the intercept of the given discriminant function. Empirically, the cutoff method is computationally efficient and can work well in some situations.
of classifiers based on discriminant function from
classifier. Specifically,
To study the performance of these methods at the population level, i.c., there are infinite number of samples, we first introduce general notion of optimal ROC curve over arbitrary model space. This
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

new notion of optimal ROC curve parallels the notion of Bayes error for standard binary classification when the model space is the set of all measurable classifiers. Traditionally. ROC curve is typically defined as the set of FPR-TPR pairs produced by the classifiers obtained from the cutoff method, where TPR denotes true positive rate and is defined by TPR- = FNR. An optimal ROC curve [see, e.g., Van Trees, 2004] is defined as the ROC curve generated by m7(r)) = P(Y = X = x),, where Y denotes the binary response and X denotes the feature vector. This curve is optimal in the sense that no other ROC curves can lie above it. Here we generalize the notion of optimal ROC curve given a specific model space, This done by assigning a partial order to all possible FPR-TPR pairs that can be obtained over the given model space, and defining the optimal ROC curve as the pareto frontier of the set of FPR-TPR pairs. This allows us to define the optimal ROC curve under an arbitrary model space, and discuss the general case that model is possibly mis-specified. We show that the newly defined optimal ROC curve coincides with the existing definition when the model space includes all possible measurable classifiers.
In terms of consistency, we find that when the model space contains all measurable classifiers, all three methods target the optimal ROC curve under 0/1 loss or some surrogate loss under a new notion of correct model specification. Interestingly, in order for a model-loss pair to be correctly specified, a sufficient condition required for the surrogate loss is related to the notion of classiiicatonn-caiirattio [Bartlett et al., 2006]. which is a sufficient condition required to achieve consistency in binary classification. In this sense, our results generalize that of Bartlett et al. [2006] for binary classification to optimal ROC curve estimation. When the model-loss pair is mis-specified, however, we show that only the constrained method targets the optimal ROC curve over the chosen model space. In this sense, the other two methods may miss some optimal FPR-TPR pairs on the optimal ROC curve. Importantly, this suggests that the constrained method may be preferable to the two other methods in many practical applications where the model space considered does not include the true model.
To the best of our knowledge, our work is the first that formally investigate theoretical conditions under which the commonly used methods could recover the optimal ROC curve in a statistical decision theoretical framework. Moreover, our proposed definition of optimal ROC curve also generalizes the conventional definition, relaxing some unnecessary distributional assumptions on the data. For ROC curve estimation, existing works are either empirical or mostly focus on how to generate a single FPR-IPR pair on the optimal ROC curve using either the weighted method or the constrained method. For example, Cannon al. [2002] investigated the empirical version of the constrained method, and provided a probabilistic guarantee on simultaneous control of both FPR and FNR. Extensions to structural risk minimization were later considered in Scott and Nowak [2005]. However, they did not address the issues on how to better estimate the whole ROC curve. Scott [2007] proposed two families of performance measures to evaluate classifiers produced by the constrained method. Interestingly, they also showed that the ROC curve is concave under some assumptions on the data generating distributions. part of which are special cases of our theory (see Theorem 2). More recently, Rigollet and Tong [201 1] focused on how to obtain a classifier that can control its FPR at the population level. This done by using a convex surrogate loss and considering a slightly more stringent upper bound than the desired level for the FPR. However, their method may not target the best trade-off between FPR and TPR, which is partly attributed to the use of convex surrogate loss and possible model mis-specification. Lastly, Bach et al. [2006] proposed to estimate the ROC curve by computing a convex envelope of ROC curves generated by the cutoff method when varying the class weights. They demonstrate that this will usually outperform the ROC curve produced by the cutoff method alone, which is partly consistent with our theory that the weighted and cutoff method may be sub-optimal when the model is mis-specified.
Moreover, our definition of the optimal ROC curve is also new and it extends the old definition considered by Van Trees [2004] and Scott [2007] in two different ways. First, the optimal ROC curve in Van Trees [2004] and Scott [2007] requires some continuity assumptions on the data generating distribution. By contrast, our definition is quite general and requires a much weaker assumption on the data generating distribution. In fact, we show that our definition coincides with the existing definition if the continuity assumption is satisfied. Second, our definition allows model missspecification, which reveals some interesting differences among the commonly used methods when model mis- specification may be present. Another important contribution is that we formally prove the continuity and concavity of the optimal ROC curve and present some other important properties of the optimal ROC curve, which extends results informally stated in Van Trees [2004] and Scott [2007].
2

---

The rest of the article is structured as follows. We define the notion of optimal ROC curve over a general model space, and derive the optimal ROC curve over the entire population analytically in Section 2. Section 3 analyzes the population analogue of three ROC estimation methods when model is correctly specified and mis-specified. We present some numerical examples to illustrate the impact the mis-specification on the performance of three methods in Section 4, and we end with some discussions in Section 5. All proofs are included in the supplementary material.
2 Optimal ROC curve over a general model space
In this section, we introduce the notion of optimal ROC curve over a general model space. The notion of optimal ROC curve is parallel Bayes risk in standard binary classification. We therefore argue that the optimal ROC curve should be the theoretical target for ROC curve estimation, just like Bayes error in standard binary classification.
Before proceeding, we first lay out the basic problem setup, some notations, and assumptions to be used throughout the article. Consider feature-response pair (X,Y) with joint distribution IP, where X E IRPP is the feature vector and Y E {-1, } is the corresponding binary response. Throughout, we assume that the marginal distribution X, denoted as Px,, is continuous, and the marginal distribution of Y satisfies p = IY = 1) E (0, 1) and p = IY = -1) E (0, 1). We use h R' + {-1,1} to denote classifier that maps feature vectors to their responses. For many methods, classifier is induced by the sign of a so-called discriminant function. Throughout, we use H to denote set of classifiers, and FF to denote set of discriminant functions.
Many different metrics can be used to assess the performance of a classifier, of which misclassification error rate IP(Y A f((X) is perhaps the most commonly used and well-studied in the literature [Zhang et al., 2004; Bartlett et al., 2006]. Classification methods are often designed to minimize the misclassification error, which is the weighted average of two types of error rate, namely. positive rate FPR(h) = F()(X) = 1 Y = -1) and false negative rate FNR(h) (h) = P(h(X) = -1 Y 1). In this article, we focus the problem of minimizing these two types of error rate simultancously. This is essentially equivalent to the estimation of optimal ROC curve, which plots the true positive rate (TPR) against the false positive rate for set of classifiers, where the true positive rate is defined to be TPR(h) = 1 - (h)(
In standard binary classification, the optimal classifier that minimizes the misclassification error is often referred to as the Bayes classifier. For our problem, we have two criterion to optimize. By borrowing ideas from multi-objective optimization literature [Miettinen, 2012], we define the set of optimal classifiers as those that can not be dominated by any other classifiers, and the optimal ROC curve the set of FPR-TPR pairs that can not be dominated by any other FPR-TPR pairs. Here classifier h dominates classifier h', denoted as h > h', means that TPR(h) 2 TPR(h') FPR(h) < FPR(h') and (FPR(h), TPR(h)) & (FPR(h') ( (PR())). In this sense, classifier h is an optimal classifier if it can not be dominated by any other classifiers. Similarly, for any two FPR-TPR pairs (u, v) and (u', v²), we say that (u, v) dominates (u', v²), denoted as (u. v) v 2 of and (u, v) + (u', o'). Given this partial ordering, we denote by PF(A) == {(,, v) E A (u', & (u, v) for any (u', ,') A} the pareto frontier of a compact set of optimal classifiers constitutes the pareto frontier of the given set of classifiers, while the optimal ROC curve is the pareto frontier of the given set of FPR-TPR pairs.
v²), if u u',
A C IR. Therefore, the
Formally, we define the optimal ROC curve over an arbitrary set of classifiers H, which allows possible model mis- spiiffpeciiia
Definition 1 (Optimal ROC curve over model space H) Given a set of classifiers H. denote by S(H) = {(FPR(h), TPR(h)) h E H} the set of all FPR-TPR pairs generated by classifiers in H. We call the pareto frontier of S(H), denoted as (H)) = PF)S(H)), the optimal receiver operating characteristic (ROC) curve over H. When H. = Ha. where Hy is the class of all measurable classifiers, we simply call (Ha) the optimal ROC curve.
Throughout this article, we assume that S(H) is a closed set so that PF(S(H)) is well-defined. As we can see from Definition 1, classifiers corresponding to any point on the optimal ROC curve cannot be dominated by any other classifier. Note that this is also similar to the notion of admissibility for general decision rules in statistical decision theory. The above definition of optimal ROC curve differs from the existing definition by Scott [2007] in that it allows for model mnis-peccification When the model is correctly specified, the optimal ROC curve parallels the notion of Bayes error
3

---

rate for regular binary classification, while the corresponding classifiers parallels the notion of Bayes classifier. is well-known that Bayes error rate 1/2 E (7()) 1/2] [Devroye al., 2013], where ((a))) = IP = X x) is the regression function. In parallel, we derive the optimal ROC curve over the class of all measurable classifiers Ha. Compared with some existing definitions of optimal ROC curve under correct model specification, our definition is more general, requiring less conditions on the distribution of (X, Y) [see, c.g., Scott, 2007]. Specifically, our definition of optimal ROC curve only requires that X is a continuous random variable, while Scott [2007] requires that both X and (xx) are continuous random variables.
The following theorem derives an analytic form for the optimal ROC curve ((Ha) defined in Definition
Theorem Let nf()) = =1) - the indicator function. We have that the optimal ROC curve can be represented as
inf(p: P(n(X) S s = 1}, and let I(.) denote
((Ha) {(a, a [0,1 P()(X) 0}
(1)
where
P(n(()) = 1)/p+
ifa 0, if E (0,1 -
s(a))=
P(x(X)>((a)) op (M p((I-da))
(2)
((X)) c) a)) < 0}. Moreover s(a) is continuous, strictly increasing, and concave over its domain [0, P(n(X) - 0.
with c(a) = inf E 10.p"): E[1
Some remarks are in order. First, we can see that the optimal ROC curve is continuous, strictly in- creasing, and concave curve defined by the function s(a) over the interval [0. - ((n(()) = 0 Second, existing definition of the optimal ROC curve typically relies the likelihood ratio test [see, e.g., McIntosh and Pepe. 2002; Scott, 2007]. More specifically, it assumes that X has class- conditional density function f+ (2) and f- (x:) conditional on Y and Y -1, and considers class of classifiers indexed by À E [0, co): (1) = (1)((++()//(C)))) - A), X E [0, oo]). Then, under the assumption that
((4(())/-((X) A = -1) P(4(())/- = X Y -0
for any x E [0, oo). Scott [2007] defined the optimal ROC curve as the set of FPR-TPP -PR-TPR pairs generated by the class of classifiers (1)( (x)); À E [0, so]). In other words, the existing definition of the optimal ROC curve can be expressed as
(FFR())), IPR(hx)) X E [0]
(4)
Our definition of optimal ROC curve (c.f. Definition 1), however, does not require the likelihood ratio assumption in (3), and hence in this sense is more general than the existing definition. Indeed, assumption(3) may be violated in some common situations, for example, the two class-conde condissoniiionaal densities f4 (ar) and (=(x) have different supports. Moreover, under the condition (3), we can show that our proposed definition coincides with the existing definition (4). Furthermore, the optimal ROC curve is the FPR-TPR pairs generated by the set of classifiers (Sign(7(XX) e) E (0, 1]}. We summarize these results in Corollary S1 of the supplementary material.
Lastly, remark that our proposed notion of the optimal ROC curve (c.f. Definition 1) also allows model misspecification. This allows us to study the statistical consistency of special classes of classification method such as linear classifiers. We will demonstrate in later sections that model specification has a meaningful impact on the consistency of various popular classification methods for ROC curve estimation.
3 ROC curve estimation methods
In this section, we review three ROC curve estimation methods that are widely used in practice. We then investigate, from a statistical decision theoretical point of view, whether these methods are targeting the optimal ROC curve defined in the previous section. In particular, we shall analyze their population analogue when the model is mis-specified, that is, the optimal classifier not included in the set of classifiers considered in the model.

---

3.1 Neyman-Pearson classification
Neyman-Peane Pearssn classification [Scott and Nowak, 2005; Rigollet and Tong, 2011], or the constrained method, minimizes one type of eтror subject to an upper bound constraint on the other type of error. The population analogue of Neyman- Peaannneersonn classification is equivalent finding classifier that maximizes the true positive rate subject to false positive rate constraint, that is,
maximize (PR(h) subject to FPR S a, kCH
(5)
where H is set of classifiers. In this subsection, will show that under mild conditions the ROC curve generated from the constrained method by varying a E [0, 1] can recover the optimal ROC curve over general model space H.
Before proceeding, we call the ROC curve generated by the constrained method, defined by
(H) = ( ((FPR()),H)) H)), (PR( a E [0,
the population ROC curve of the constrained method, where higH solution to (5). Note that the population ROC curve is essentially the set of FPR-TPR pairs generated by the solutions to the constrained method (5) after varying a [0, 1].
We first consider the case H = Ha. where the model space H. is the set of all measurable classifiers. In this case, can derive the analytic solution to the constrained method (5), which then allows us to derive the population ROC curve TC (Ha) generated by the constrained method.
Theorem Denote ππ(x) P(Y 1 X x) and pd inf(p: : P()(X) S p) =
13. Let H He
be the set of all measurable classifiers. For any solution (x) of (5), denote by R = { h (z) 1}. Then, up P -null set,
(z: n(x) = 1}
fa= 0,
Ra
(6)
(x: U..
ifa E (0,1),
where c(a) = inffe E [0. p0.p']
B(1 1 (x)
c) a) s 0} with c(a) E 10, and
Na S (x: n[xx) c(a)) with
P(X E Na. B(1 B1--((0)(--(((()=ddd)
(0, 1 P()(X)=))
ifa E
1-d(a)
(7)
PP(X E N.)) & B(1 - (x [T](X) > 0))
ifa E
X(((X)=))
Moreover, we have that optimal ROC curve (Ha) satisfies
((Ha)) S (HH)) ~ {(a, 1) : (1-P(((X) = 01// .1]
(8)
This theorem provides a complete characterization of the population ROC curve of the constrained method. Combining (8) with Theorem 1, we can see that the constrained method can recover the optimal ROC curve in the sense that it produces curve that contains the optimal ROC curve. Using this, we can further show that the pareto frontier of the population ROC curve, defined by Te (Haa) (F(c(()))HH)) is identical to the optimal ROC curve. Here use cl (A) to denote the closure of set A. We summarize this result as below.
Corollary We have that
(HH) (PHa) E (Haa).
Corollary: suggests that the constrained method over H. indeed targets the optimal ROC curve (HHa). Essentially, by our proof of Corollary 1, the discrepancy between (HH) and the optimal ROC curve ((Hl,) occurs only if TPR = 1. Moreover, by our proof ((n(X) = 0) = 0 then we have that (HH.) = (Ha). Notably, Scott [2007] also derived the ROC curve generated by the constrained method Tcc and proved that it coincides with the optimal ROC curve they defined under likelihood ratio condition (3). Here, we show that the ROC curve generated by the constrained method coincides with our defined optimal ROC curve (c.f. definition 1) by only requiring ((n(X)) = 0) 0.
Note that for general model space H. it no longer possible to derive the population ROC curve analytically. However, relations like (9) continue to hold. That is, the pareto frontier of the population ROC curve for the constrained method, defined by (2H( = PF(el( (H))), coincides with the optimal ROC curve over H.
5

---

Proposition 1 Suppose that S(H) = {(FPR()), TPR(h)) h E Hy is closed set. We have that (HL)) = (HH) S (c(H).
Proposition 1 shows that any point on the optimal ROC curve over a general model space H can be recovered by solutions to the constrained method (5) for some E [0, 1). Later, shall show that this property is unique to the constrained method for general model space H.
So far all results consider the 0/1 loss. In practice, a surrogate loss is often used to replace the 0/1 loss, and discriminant function often used as the decision variable in the optimization problem. x)) [Shen et al., 2003], which could approximate the 0/1 loss up to arbitrary precision. The rationale here is that a continuous loss that is close to the 0/1 loss would enjoy similar nice theoretical properties of the 0/1 1 loss. As a final note, we do not discuss convex surrogate loss for the constrained method, partly because convex surrogate loss and convex set of discriminant function used, the optimization problem associated with the constrained method is convex, and thus is equivalent to a weighted problem, which we will study subsequently in the next subsection.
Here propose to the so-called psi loss (x)) min( [1, max
3.2 Weighted method
Another popular method to estimate the ROC curve, which we call the weighted method, considers a set of classifiers obtained by assigning different class weights the two types of errors. In practice, instead of directly optimizing the "weighted error rate", some continuous surrogate loss (often convex) is typically used to replace the non-continuous 0/1 loss for ease of computation, which could introduce additional "model bias" or model mis-specification. This phenomenon has been extensively studied for standard binary classification task [see, e.g., Zhang et al., 2004; Bartlett et al., 2006]. Roughly speaking, the surrogate loss function needs to satisfy certain condition to ensure the consistency of the procedure (in terms of Bayes error). In Bartlett al. [2006]. the surrogate loss satisfying this condition is called to be classification classification-calibaaadd calibbaate [Bartlett et al., 2006], and they further showed that procedures that are consistent using the 0/1 loss, are also consistent using any classification -aaliiatto losses.
Here shall present some parallel results for ROC curve estimation. More specifically, we consider the population analogue of the weighted method under surrogate loss V-)) over set of discriminant functions F:
minimize B((1 w)T(Y = + wT= -1)(((())))(())) JEF
(10)
We denote by fi, v(.) a solution (10), which may not necessarily be unique. Given the optimal discriminant function f (.)) we define the associated optimal classifier by h /w = Sign f v where Sign(2) 2I( < 0) 1 denotes the sign function. We aim find conditions for the surrogate loss and the class of discriminant function, under which the population ROC curve of the weighted method using surrogate loss (-) over set of discriminant functions F, defined
( - (FPR(M (w)). TPR(h | w E 10.
(11)
can recover the optimal ROC curve over H (Sign(J) I E FJ. We first present a general condition on the class of discriminant functions F and the surrogate loss function V(-) to ensure consistent estimation of the optimal ROC curve.
Definition 2 (Correct model specification for weighted method) We say that a set of discriminant
for function F is correctly specified under surrogate loss V(-) for the weighted method, if for any
O S w < 1 with [P(n = w) 0, any solution f',,ve) to (10) satisfies (x f (x) > 0) {x n7(x)= w) up to a Fx-lull set.
Under this notion of correct model specification, indeed show that the weighted method using the surrogate loss V-) recovers the optimal ROC curve if the model space F is correctly specified under (-).

---

Theorem 3 F is correctly specified under a surrogate loss V(-) for the weighted method, then we
have that (W. {(a, s(o) is non-differentiialle a, a E ( (()1) {(a))(a)) PP)((X = c(a)) 00, E (0, 1 ((((())00/pp)
(()) TP : E [0. and P(n(X) = w) > 03 u. us.
(12)
where Sy and S1 satisfy
[{(0, (0)))
ifc(0) < < P()(X) = 1) = =0,
S 10,
(13)
otherwise.
and
is [(1 - P()(X) 0)/p- .1},, if 1 c(a) > 0 P(n(X) 0) 0,
10
otherwise.
(14)
Theorem 3 connects the population ROC curve of the weighted method to the optimal ROC curve when H = Ha. In Proposition SI of the supplementary material, we establish that the set of (a, s(a)) with P(n((X
c(a)) > 0 and a > corresponds to linear pieces on > (HH)). Combining this with (12) in Theorem 3, it follows that except for some interior points of these linear pieces the other parts over optimal ROC curve can be recovered by weighted method. Therefore, roughly speaking, the set of points on the optimal ROC curve that can be recovered by the weighted method is the union of non-differentiable part and nonlinear part (up to some isolated points).
Although the above result seems to suggest that the weighted method may not recover all these linear pieces on the optimal ROC curve, it can be trivially modified to recover the entire optimal ROC curve by considering the pareto frontier of the convex hull of the ROC curve generated by weighted method. This is established in Corollary S2 of the supplementary material.
Next, we establish sufficient conditions on (-) under which Fa is correctly specified under V--). where Fa consists of all measurable functions. Interestingly, the requirement on (-) coincides with the notion of classification iuasiffcation-calibraeee [Bartlett et al., 2006].
Definition 3 (Classification-calee calibrated loss [Bartlett et al., 2006)) Let 0 sn S 1 and define
Hv((n) = inf (a) + (1-1n) (1-n) oER
(15)
inf (ī(1) a: a(n-1/2)50
n/ + (1-
(16)
where (-) is a surrogate loss function. (-) is said to be classification-caalibaaedd if Hy (n) < (n) for any 1 # 1/2.
In Bartlett et al. [2006], it is shown that using a classifictiion-caibrza loss V-) ensures consistent estimation of the optimal misclassification error, when JF includes all measurable function (i.e., Fa). Now we establish that the class of all measurable discriminant functions Fa is correctly specified under any glassiication-calibaaeee surrogate loss.
The class of all measurable functions Fa is correctly specified for the weighted method (i.e., in the sense of Definition 2) under the 0/1 loss, and any dlasificationncaliiraaee surrogate loss V()..
Proposition 2
Combining this with Theorem 3, it follows that if V-)) is classification and F Fa. then the weighted method using the surrogate loss can recover the optimal ROC curve. In other words, for weighted method using classification-calibain loss over F = F. generates consistent estimation of the optimal ROC curve.
Finally, we give an example in Theorem S1 of the supplementary material to show that in contrast to the constrained method (c.f. Proposition 1), the population ROC curve of the weighted method may miss some components of optimal ROC curve when the model space F is mis-specified under surrogate loss V(.). Importantly, these components cannot be recovered even after taking the convex hull transformation.
7

---

3.3 Cutoff method
Cutoff method is another type methods commonly used in practice. It first produces a discriminant function using some classification method, and then generates set of classifiers by thresholding sequence of cutoffs to the discriminant function. In order to study the population analogue of the cutoff method, we assume that the discriminant function is generated from given classification method with class weight w [0, 1] for negative instances:
(w)(-)) arg min B((1 w)I(Y =1) wI(Y --===-))VV V)) fEF
(17)
where F is the set of discriminant functions. We define the population ROC curve of the cutoff method over F to
TI.VO), wc ({ ( ( 6)), T/ -))) 1 ER].
(18)
Next, we establish sufficient conditions on F and (-)) to ensure that the cutoff method can recover the optimal ROC curve. Similar to the weighted method, we define a notion correct model specification for the cutoff method.
Definition 4 (Correct model specification for cutoff method) We say that a set of discriminant function F is correctly specified under surrogate loss function V() for the cutoff method for some E (0, 1), if any solution to (17) at w is a strictly increasing transformation to 7)x²) almost surely, that is,
f M(((X)) almost surely,
where M() is a strictly increasing function.
Under this notion of correct model specification, show that the cutoff method targets the optimal ROC curve when (xX) is continuous random variable. This is established in the following theorem.
Theorem 4 Assume x)() is continuous random variable. If is correctly specified under surrogate loss (.)) for the cutoff method for some w E [0, 1]. then we have that
(F, ()) -
>HH.)
For the cutoff method, specified under any surrogate loss (-) that is diffcrentiable, strictly decreasing, and strictly convex.
show that the set of all measurable discriminant functions is correctly
Theorem Assume rXX) is continuous random variable. Suppose that V(-) is a differentiable, strictly decreasing, proper and strictly convex loss. Then the class of all measurable functions Fa is correctly specified under V (-) for the cutoff method at any (0,
An important implication of the above two theorems is that, the cutoff method defined (18) can recover the optimal ROC curve if F Fa and the surrogate loss V(-) is differentiable. strictly decreasing and strictly convex. Note that the requirement on the surrogate loss for the model to be correctly specified for the cutoff method is more stringent than the cussiffcaationcalliban requirement for the weighted method (c.f., Lemma S7 in the supplementary material).
For general model space F, the requirement of correct model specification for the cutoff method also generally stronger than those needed for the weighted method. This because gen- eral we would not know whether (w.v(.) (æ: is strictly increasing function of 17(x), even if Sign(fiivee (z)) Sign(n(=>) w) and (XX is a continuous random variable. In Theorem S2 of the supplementary material, we give an example to show that in contrast to the constrained method (c.f. Proposition 1), the population ROC curve generated by the cutoff method over F may be dominated by the optimal ROC curve over = [Sign(f- - 5) f E F, E RR), suggesting that the cutoff method may not recover the optimal ROC curve over H in general.
4 Simulations and real data analysis
In this section, we examine the operating characteristics of the three methods analyzed in this article with both simulation studies and real data example. In simulation, investigate the effect of

---

model mis-speciiiiationn by considering linear classifiers over two simulated data sets. One dataset generated under a linear discriminant analysis (LDA) setting, which imitates the scenario where model is correctly specified. The other is based on a quadratic discriminant analysis (QDA) setting, which is used to show the differences across three methods under model mis-specification. We also compare the three methods by using a bank marketing data set [Moro et al., 2014 4),,, which allows us to investigate the effect model mis-speccification on the performance of ROC curve estimation methods in real problem setting. Throughout all the experiments, methods including constrained d-learning, weighted SVM and its cutoff version, and also typical kernel methods that include kernel weighted SVM and its cutoff version
consider linear classification
Example (LDA setting). This example considers linear discriminant analysis model, where P(Y = 1) = P(Y = -1) = 1/2, and conditioned on Y. X Y N(Y μ. 4f), where μ = (L,1)T& E R The sample size is n 2000.
Example 2 (QDA setting). This example considers a quadratic discriminant analysis model, where F(Y- = 1) = PPY = -1) = 1/2, and conditioned on Y, X Y ~ N(Y,,, p, Ey), where 1 = (1, 1) E IR?, and
Σ+ 88 5 E_ =
-3
-3 16
The sample size is n = 2000.
Example 3 (Real data example). This example considers bank marketing dataset [Moro et al., 2014], which records the direct marketing campaigns of Portuguese banking institution and are available at https: paaps://archhi /arph//arciieeee ics. uci edu/ aol/datasets /Bank Maakeeia This real dataset consists of 4521 examples with 17 features and binary response variable.
We visualize the scatter plots of two simulation examples in Figure 1. For two simulation examples, compare the average estimated ROC curve for the five aforementioned methods over 100 replicates; while for the real data example, we present the estimated ROC curves directly. For all three examples, to generate the estimated ROC curve we vary weight w and the constraint upper bound a from (i/500 i = 0, 1, 500} for the weighted method and the constrained method, respectively. For the two cutoff methods, we choose w 1/2. The results are summarized in Figure 2 and Figure $1 of the supplementary material.
The left panel of Figure 2 is for the simulations under LDA setting, where the model is correctly specified for all methods. In this case, all methods perform almost the same. The right panel of Figure 2 is the for the simulations under QDA setting. In this case, the model is mis-specified for linear methods. As expected, the two kernel methods perform the best. Moreover, among linear methods, the constrained method performs the best, which corroborates with our theoretical findings that constrained method performs best under possible model mis-specification. For our real data example, can in Figure S1 that among all these linear method the constrained method performs best, but is no better than the weighted kernel SVM. These results again corroborate with our theoretical analysis on the goodness of using constrained method when model is mis- miessiec..
Discussion
In this article, we define a general notion of optimal ROC curve, which we argue should be the theoretical target of any ROC curve estimation methods. We analyze three popular ROC estimation methods, and show that when the model space contains all measurable discriminant functions all three methods target the optimal ROC curve, although the cutoff' method requires a stronger set of conditions on the surrogate loss for it be consistent. When model mis-specificatiin present, we show that only the constrained method under the 0/1 loss targets the optimal ROC curve over the used model space. This together with our simulations and real data studies suggests that the constrained method with non-convex surrogate loss (e.g. vú loss) would be the preferred method when the model possibly mis-specified. Although we have observed good empirical performances using the constrained method with 1e loss, we have not investigated its theoretical guarantees in this article. Further theoretical research on non-convex surrogate loss to achieve guaranteed performance may be necessary.

---

-2
-6-
positive
-10-
pesitive class
negative class
negative class
2
2
10
Figure Scatter plots of dataset used in LDA setting (left panel) and QDA setting (right panel).
1.0
1.0
0.8
0.8
positive
positive
0.4
0.4
Weighted lineer SVM
Weighted liner SVM
0.2
Weighted Kemal SVM
0.2
Weighted kemal SVM
Cutort
Cutoff kemel SVM
Cutoff kemel SVM
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
False positive rate
False positive rate
Figure 2: Estimated ROC curves of five different methods under the LDA setting (left panel) and QDA setting (right panel). Here "Constrained linear v6"' "Weighted linear SVM", "Cutoff linear SVM", "Weighted kernel SVM" and "Cutoff kernel SVM" denote constrained vé-learning with linear discriminant functions, weighted SVM with linear discriminant functions, cutoff method applied to SVM with linear discriminant functions, weighted SVM with RBF kernel, and cutoff method applied SVM with RBF kernel.
Acknowledgments and Disclosure of Funding
The authors are supported in part by the US National Science Foundation (NSF) under grant DMS- 20- 15-90 The authors thank the reviewers for valuable comments and suggestions that improved the article.
10

---

References
F. R. Bach, D. Heckerman, and E. Horvitz. Considering asymmetry in learning classifiers. Journal of Machine Learning Research, 1733)11713-1171, 2006.
P. L. Bartlet, M. L. Jordan, and D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-1 156, 2006.
A. Cannon, Howse. D. Hush, and C. Scovel. Learning with the neyman-pearson and min-max criteria. Los Alamos National Laboratory, Tech. Rep. LA-UR, pages 2951, 2002.
L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science Business Media, 2013.
C. Elkan. The foundations of cost-sensitive learning. In International joint conference artificial intelligence, volume 17, pages 973 978. Lawrence Erlbaum Associates Ltd, 2001.
T. Fawcett. An introduction
analysis. Pattern recognition letters, 2768):61-8774 2006.
M. W. McIntosh and M. S. Pepe. Combining several screening tests: optimality of the risk score. Biometrics, 58 (3):6576664, 2002.
K. Miettinen. Nonlinear multiobjective optimization, volume 12. Springer Science & Business Media, 2012.
S. Moro, P. Cortez, and P. Rita. data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
P. Rigollet and X. Tong. Neyman- pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12(00c):2831-2855 201
C. Scott. Performance measures for neyman-pearson classification. IEEE Transactions on Information Theory, 2388):2852-2863, 2007.
C. Scott and R. Nowak. A neyman pearson approach to statistical learning. IEEE Transactions on Information Theory, 51 (111)):806-3819 2005.
X. Shen, G. C. Tseng, X. Zhang, and W. H. Wong. On v--lcarnigg Journal of the American Statistical Association, 98(463):724-783 2003.
H. L. Van Trees. Detection, estimation, and modulation theory, part I: detection, estimation, and linear modulation theory. John Wiley & Sons, 2004.
V. Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991.
T. Zhang al. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32( (2(1))56888 2004.

---

Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [No] We will release codes later.
(b) Did specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experiments multiple times)? [No] We report average performance of experiments results by multiple replicates.
(d) Did you include total amount of compute the type resources used (e.g.. type GPUs, internal cluster, or cloud provider)? [No] Computational speed is not the main concern our simulations.
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're us-
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "qMhKp1UYNXy", "reviewer": "Reviewer_DSre", "summary": "The problem of estimating ROC curves under possible model misspeciffication is\nstudied. A notion of optimal ROCs under arbitrary model spaces is introduced,\nand three existing methods of estimating ROC curves are studied with respect to\nthis optimal curve. The optimal ROC is shown to coincide with existing\ndefinitions when the model space includes all measurable classifiers. All three\nestimation methods are shown to be consistent when correctly specified, however\nonly one estimation method (constrained/Neyman–Pearson) targets the optimal\ncurve under model misspecification.\n", "questions": "A significant portion of the theory handles seemingly pathological corner cases,\ne.g., non-differentiable parts of the weighted method and pieces dealing\nspecifically with equalities. Would some mild assumptions allow for meaningful\nsimplifications of the theory?\n\nThere are no real-world experiments, how big a difference is there on real world\ndata?\n", "limitations": "The limitations of the theory are clear from the stated assumptions. No real\nworld experiments are a limitation that could be briefly discussed.\n", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is novel and the results broadly applicable as ROC analysis is widely\nused and forms the basis for many methods. The presentation is good, writing\nclear, and the novelty well placed amongst existing literature. No proofs are\npresented in the main text, but the interpretation and general presentation of\nthe theory is excellent.\n\nThe proposed framework is shown to coincide with existing results, and indeed\ngeneralises some results as there are no assumptions on the data generating\ndistribution.\n\nThe theory is lightly explored in simulation studies. As expected, the\nsimulation results align with the theory, but the main results figures are\npresented in the supplementary materials as there is a lack of space in the main\ntext. There are no experiments on real-world data.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lYKkzR2BdIY", "reviewer": "Reviewer_hAdd", "summary": "The authors present a more general notion of \"optimal ROC curve\" for binary classification. They show that their definition relies on weaker assumptions than predecessors when considering the set of all possible classifiers, and they extend the definition for general sets of classifiers. They also show sufficient conditions for three common ROC generating procedures to be consistent, under this definition of optimal ROC, when the model is correctly specified. Results on simulated data agree with the theory.", "questions": "Questions:\n \nCould you clarify the assumption of continuous data distribution? I notice what appear to be some contradictions. Line 84: \"However, our definition is quite general and does not make any assumptions on the data generating distribution,\" and a similar statement is made on line 150. However, line 104 states \"Throughout, we make the assumption that the marginal distribution $X$, denoted as $\\mathbb{P}_X$, is continuous...\" and in some places you make the similar assumption that $\\eta(X)$ is continuous.\n\nSuggestions:\n\nIf possible, it would be beneficial to move some of the technical details from sections 2 and 3 to the supplementary material so that (assuming the brevity of other sections was a result of page limit) the motivation, context, and discussion can be improved. For example, many points in section 2 are relatively less significant in the context of prior work and may merit only a mention in the main paper with deeper analysis in the supplementary material; similarly, many key takeaways in section 3 can be stated while moving most of the bulky math to the supplementary material. Some figures in the main paper, both to aid understanding of concepts and to show the main results being discussed, might help too. If it were me, the priority would be:\n1. placing the main experiment results in the main paper\n2. making the discussion more thorough, including more detailed interpretation of experiment results, potential impacts, limitations resulting from assumptions, practical uses, future work\n3. more clearly motivating the problem and its significance (why should someone using ROC curves for model evaluation care about these results?) in the introduction\n\nUnderstanding would be greatly aided by making sure that all terms and symbols are defined. Some that would aid my understanding:\n - \"model misspecification\" in this context\n - \"at the population level\"\n - $\\mathbb{I}(...)$ (I assumed this was the indicator function, but see places where I'm not sure that makes sense, such as when there is a random variable with no $\\mathbb{P}$ or $\\mathbb{E}$)\n - $p^+$ and $p^-$\n - $cl(...)$\n\nSince the synthetic data being used is 2D, include a scatterplot showing the data and its labels. Putting it in the supplementary material is fine.", "limitations": "The authors state the assumptions that are necessary for their results, but the realistic limitations implied by these are not always clear. In particular, one of the novel elements of the work is that the \"optimal ROC\" definition can be extended to general sets of classifiers; however, many of the key results require the assumption that the set contains all possible classifiers, which has important implications in practice that should be discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this paper has a solid core with some weaknesses in the presentation and analysis. Some of the weaknesses are easy to address; if they are addressed, I would improve my score.\n\nEDIT: the authors have largely addressed my concerns, so I am changing my overall score from 4 (borderline reject) to 7 (accept).\n\nStrengths:\n\nI am not deeply familiar with related work, but based on the authors' presentation of it, the work contains original, significant contributions, particularly in section 3. The technical portions are thorough and most sections are clear and easy to read. The problem being addressed is general, fundamental, and broadly relevant in machine learning.\n\n\nWeaknesses:\n\nThe main paper is largely consumed by technical details, and as a result, many higher-level parts (motivation, related work/context, experiment results and analysis, discussion) are not thorough. This makes it difficult to determine the significance and potential impact and limitations of the work. \n\nThe originality/significance of section 2 is weak. Most of the results are noted to be only slight generalizations of previous work. The key novelty is the notion of \"optimal ROC\" for general sets of classifiers, and there is hardly any useful analysis in this context compared to the context of all possible classifiers.\n\nThere are some terms and notations throughout the text that are not clearly defined before they are used, and for which I couldn't find definitive information when searching online. These hinder understanding of high-level concepts as well as technical details. This should be easy to fix, though. I've listed some in the Questions/Suggestions section.\n\nThe experimental results are very limited and not thoroughly discussed. There are only results for two simple synthetic datasets, the results are relegated to the supplementary material, and the discussion of the results is limited. This would be a good place to test on some real datasets, where assumptions will not necessarily hold, and discuss the practicality and limitations of the paper's contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eAT3qJXwUG", "reviewer": "Reviewer_gfsm", "summary": "This theoretical paper studied three popular ROC curve estimation methods (i.e. Neyman-Pearson classification,  weighted method, and cutoff method) and then analyzed at the population level under both correct and incorrect model specifications.  In particular, the authors showed that all three methods are consistent in the sense that they all target the optimal ROC curve under 0/1 loss or some surrogate loss under correct model specification. Such results can be regarded as an extension of the classical consistency results from binary classification to ROC estimation methods.  The introduced definition of the optimal ROC curve extended the definition in [Scott (2007)] which has much less assumptioin. ", "questions": "I have no time to go through the proofs step by step. I am wondering what is the main novelty in the proof techniques in addition to the statements about the new results obtained and the relaxed conditions.  For instance, what are the main reasons that you can relax the continuous conditions made in Scott's paper? ", "limitations": "The authors have not addressed the potential limitation of the work.  it would be nice to see what are the remain questions for future work. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros; \n\n1. It seems that this work is the first-ever-known study to investigate theoretical conditions under which the most popular three methods can recover the optimal ROC optimal curve in the statistical decision framework. \n\n2. The proposed definition of the optimal ROC curve using the Pareto frontier is new and has played a central role in the paper. \n\n3.  Some conditions in the literature [Van Trees (2004) and Scott (2007)] are significantly relaxed and extended in the paper. \n\nCons: \n\nThe proofs provided in the supplementary materials are very technical and lengthy. My main question is what is the main novelty in the proof techniques compared to those in the literature. \n\nI have read the authors' reponse and my score remains the same. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OluPV9r9SBF", "reviewer": "Reviewer_8S33", "summary": "The authors present a definition of 'optimal ROC curve' which is applicable under model misspecification, i.e., when the model class does not contain the target function.  Three different supervised learning approaches for producing a set of fitted functions generating an ROC curve are analyzed in the limit of infinite training data (i.e. at the \"population level\"): the constrained (Neyman-Pearson) method of maximizing true positive rate subject to an upper bound on the false positive rate, the risk minimization/cost optimization approach in which false positive and false negative errors are weighted differently, and a thresholding (a.k.a. .\"cutoff\" method) in which one real-valued-output discriminant function is learned and an ROC curve is generated by varying the threshold above which one class is predicted instead of the other. If the model class contains all measurable classifiers, then all 3 methods are shown to be consistent in the sense of converging on the optimal ROC curve, although the cutoff method requires a stronger set of assumptions on the loss function used. If there is model misspecification, however, the authors show that only the constrained method is consistent in estimating the optimal ROC curve. Some simulations are presented where the model class is linear but the target function is either linear (to illustrate the case where the model is correctly specified) or quadratic (to illustrate model misspecification).", "questions": "Does the cutoff method analysis cover the case of cross entropy? Maybe it does and I am not seeing it, but it is not clear to me. \n\nAre you sure you want to publish this in NeurIPs rather than a journal? Wouldn't you rather be able to include the proofs as part of the paper itself?", "limitations": "I don't see any concerns regarding negative societal impacts. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results are original to the best of my knowledge.\n\nAssuming correctness, I do believe the result that only the constrained method is consistent under model misspecification is a significant result with practical implications (i.e. that the constrained method should be used unless using nonparametric methods).\n\nHowever, I have some concerns about whether the cutoff method result is derived under realistic assumptions.  The assumption is made that a discriminant function f(x) is chosen to minimize a weighted expectation of  V( Y f(x) ), where V is a surrogate loss function and Y is the binary class (1 or -1).  It is not clear to me whether this construction covers the most likely real world scenario for binary classification: logistic regression, where f(x) is chosen to minimize cross-entropy (sometimes described as log likelihood). Here f(x) would range between 0 and 1 and represent the probability of class 1 and we would be minimizing -log(f(x)) if Y=1, -log(1-f(x)) if Y=-1.  I might be mistaken, but it is not clear to me whether assuming the loss surrogate V is a function of Y f(x) covers the cross entropy case. \n\nRegarding clarity and presentation, my main concern is that NeurIPs might not be the ideal venue for this work, given that the supplemental contains 59 pages (!!!) of mostly proofs.  I wonder whether it would be better to publish this work in a journal where the reader has access to the full proofs.   \n\nI also had one very specific presentation complaint. The indicator function notation used (for instance) on line 157 in s(alpha):\n\n ...indicator(eta(x) > c(alpha))\n\n...is not the standard notation for indicator function. Maybe this notation is used more than I realize, but I am much more familiar with indicator being represented as a fancy 1 with 2 vertical lines...\n\nhttps://ewens.caltech.edu/public-code-data/indicator-function-latex \n\n...or simply with I().  I would suggest at least adding a note explaining that the symbol you used represents the indicator function. It took me a while to figure out what that symbol meant, and I had to ask the area chair to confirm for me.\n\nHere are some suggested edits to the writing:\n\nLine 24 empirical risk minimization goes back a lot farther than Elkan 2001 with cost-sensitive learning e.g. Vapnik 1992 empirical risk minimization:\nhttps://proceedings.neurips.cc/paper/1991/file/ff4d5fbbafdf976cfdc032e3bde78de5-Paper.pdf\n...and probably further back than that.\n\nLine 27 another type of methods ->. another type of method\n\n31 the set of classifier -> the set of classifiers\n\nLine 34 what is “population level”? I deduced that it is the N->infinity training data limit, but it might be helpful to explain that.\n\nLine 49 all three methods targets -> all three methods target\n\nLine 58 \"when simple classifers (linear) are used\"….I actually think the result is more broadly applicable...most ML situations will have at least some model misspecification, so suggesting that it's only useful in the linear case is underselling the result …in any practical application the model probably space does not contain the perfect model\n\nLine 63 or mostly focuses - > or mostly focus\nLine 134 set of classifier -> set of classifiers\nLine 185 of special class -> of special classes\nLine 204 the set FPR-TPR pairs -> the set of FPR-TPR pairs\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept