Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

EDIT: the authors have largely addressed my concerns, so I am changing my overall score from 4 (borderline reject) to 7 (accept).

Strengths:

I 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.


Weaknesses:

The 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. 

The 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.

There 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.

The 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.
questions: Questions:
 
Could 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.

Suggestions:

If 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:
1. placing the main experiment results in the main paper
2. making the discussion more thorough, including more detailed interpretation of experiment results, potential impacts, limitations resulting from assumptions, practical uses, future work
3. more clearly motivating the problem and its significance (why should someone using ROC curves for model evaluation care about these results?) in the introduction

Understanding would be greatly aided by making sure that all terms and symbols are defined. Some that would aid my understanding:
 - "model misspecification" in this context
 - "at the population level"
 - $\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}$)
 - $p^+$ and $p^-$
 - $cl(...)$

Since 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The problem of estimating ROC curves under possible model misspeciffication is
studied. A notion of optimal ROCs under arbitrary model spaces is introduced,
and three existing methods of estimating ROC curves are studied with respect to
this optimal curve. The optimal ROC is shown to coincide with existing
definitions when the model space includes all measurable classifiers. All three
estimation methods are shown to be consistent when correctly specified, however
only one estimation method (constrained/Neyman–Pearson) targets the optimal
curve under model misspecification.

strengths_and_weaknesses: The work is novel and the results broadly applicable as ROC analysis is widely
used and forms the basis for many methods. The presentation is good, writing
clear, and the novelty well placed amongst existing literature. No proofs are
presented in the main text, but the interpretation and general presentation of
the theory is excellent.

The proposed framework is shown to coincide with existing results, and indeed
generalises some results as there are no assumptions on the data generating
distribution.

The theory is lightly explored in simulation studies. As expected, the
simulation results align with the theory, but the main results figures are
presented in the supplementary materials as there is a lack of space in the main
text. There are no experiments on real-world data.

questions: A significant portion of the theory handles seemingly pathological corner cases,
e.g., non-differentiable parts of the weighted method and pieces dealing
specifically with equalities. Would some mild assumptions allow for meaningful
simplifications of the theory?

There are no real-world experiments, how big a difference is there on real world
data?

limitations: The limitations of the theory are clear from the stated assumptions. No real
world experiments are a limitation that could be briefly discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).
strengths_and_weaknesses: The results are original to the best of my knowledge.

Assuming 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).

However, 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. 

Regarding 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.   

I also had one very specific presentation complaint. The indicator function notation used (for instance) on line 157 in s(alpha):

 ...indicator(eta(x) > c(alpha))

...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...

https://ewens.caltech.edu/public-code-data/indicator-function-latex 

...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.

Here are some suggested edits to the writing:

Line 24 empirical risk minimization goes back a lot farther than Elkan 2001 with cost-sensitive learning e.g. Vapnik 1992 empirical risk minimization:
https://proceedings.neurips.cc/paper/1991/file/ff4d5fbbafdf976cfdc032e3bde78de5-Paper.pdf
...and probably further back than that.

Line 27 another type of methods ->. another type of method

31 the set of classifier -> the set of classifiers

Line 34 what is “population level”? I deduced that it is the N->infinity training data limit, but it might be helpful to explain that.

Line 49 all three methods targets -> all three methods target

Line 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

Line 63 or mostly focuses - > or mostly focus
Line 134 set of classifier -> set of classifiers
Line 185 of special class -> of special classes
Line 204 the set FPR-TPR pairs -> the set of FPR-TPR pairs

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. 

Are 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Pros; 

1. 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. 

2. The proposed definition of the optimal ROC curve using the Pareto frontier is new and has played a central role in the paper. 

3.  Some conditions in the literature [Van Trees (2004) and Scott (2007)] are significantly relaxed and extended in the paper. 

Cons: 

The 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. 

I have read the authors' reponse and my score remains the same. 
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.
review_title: null

Meta-review: metareview: I have read all the reviews and discussions carefully.

The reviewers all praised the novelty and the significance of the work. The major complaint is that the proofs are too long to be carefully checked. The authors have appropriately addressed some comments from the reviewers. Given the unanimous support, I have decided to recommend the acceptance of the paper. 
confidence: Certain
Decision: Accept