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 paper investigates the connection between 2x2 confusion matrices and show that any measure that is defined on those, can be optimized with a threshold optimization method. 
strengths_and_weaknesses: The strength of this paper is its formal rigor. Most of the points are also very well explained, the non-trivial math is reserved for the appendices.

Yet, I did not get the impression that I have learned something new here. The fact that any 2x2 matrix can be optimized with a threshold is, in my opinion, already known from ROC analysis. You can analyze arbitrary measures with their isometric structure, and use a cost-threshold for finding the optimal point. Note that the class distribution (skewness) can also be viewed as a cost ratio. This has been investigated by Peter Flach in the early 2000s in a series of papers. Maybe the following are good starting points:

* Peter A. Flach:
Classifier Calibration. Encyclopedia of Machine Learning and Data Mining 2017: 210-217
* José Hernández-Orallo, Peter A. Flach, César Ferri:
ROC curves in cost space. Mach. Learn. 93(1): 71-91 (2013)
* Peter A. Flach:
The Geometry of ROC Space: Understanding Machine Learning Metrics through ROC Isometrics. ICML 2003: 194-201

In the reviewer-discussion of the paper, the following has also popped up:
Optimal Thresholding of Classifiers to Maximize F1 Measure
https://link.springer.com/content/pdf/10.1007/978-3-662-44851-9_15.pdf

(BTW: In case you are wondering: none of the above is a self citation... :-))

The paper discusses related work (> 2 pages of references), but does not discuss concepts that are obviously related, such as calibrating classifiers, isotonic regression, Brier scores, etc. Similarly, ROC analysis is briefly mentioned in section 4.1., but restricted to the area under curve, which is quickly done away with the argument that it is not a confusion matrix measure (which is correct). However, ROC analysis does exactly what the authors set out to do, namely to find optimal regression thresholding classifiers (in the authors' terminology). 

Now, I am not 100% sure whether the main result of the paper, namely that every confusing matrix measure can be optimized with a regression-thresholding classifier, has formally been proven before (probably not), and this may very well be a contribution that is worth-while to be reported, but that this is possible seemed to be clear to me from ROC analysis.

In any case, I think a discussion of the relation of this work to the above work on finding optimal performance under different skew/cost distributions would be essential for this paper. 

The authors have responded to that point, and shed some light on the relation of the above-mentioned works to this paper. I do think that this is much more relevant to this work than some of the works that are currently discussed in the related works section (such as SMOTE et al.). They have not been very clear about whether they intend to actually incorporate this, but I give them the benefit of the doubt and trust that they will do so.

A minor point is that the practical relevance of the experimental results is not entirely clear. I do think that they are interesting, and also well selected, and I am also fine without a real-world case study, but I do think it would be important to discuss whether, e.g., Experiment 1 is an interesting artifact or something that we can also expect to see in practice.
questions: * How does your work relate to works  on finding optimal performance under different skew/cost distributions using ROC analysis and related methods?
limitations: The authors briefly state some obvious limitations at the end. But I also would not know what else they should do, so fine with me.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Motivated by imbalanced classification problems, the paper generalizes the analysis of Bayes-optimal classifier to any performance metric supported in the confusion matrix. 
In a second part, the paper analysis the specific case of the k-NN classifier under a specific setting (uniform loss) of the previous generalization.

strengths_and_weaknesses: Strengths
+good theoretical analysis
+good theoretical insights
+well-written paper and technically sound

Weaknesses
-not explored enough how the theoretical knowledge can impact the design of models in practice.





questions: "Such an approach has many practical advantages. For example, as we show in Appendix D, a simple algorithm can exactly optimize the threshold (p, t) over large datasets in O(n log n) time. Additionally, one can address covariate shift or retune a classifier trained under one
CMM to perform well under another CMM, simply by re-optimizing (p, t), which is statistically and computationally much easier than retraining a classifier from scratch."

For the special case of  the classical Bayes classifier, is this a good strategy? Is this SOTA?
limitations: yes
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 authors consider general measures over confusion matrices and propose a generalized Bayes classifier. This is claimed to be an upper bound for any stochastic binary classifier of type P(Y=1|X=x) for the given measure over confusion matrices.
They prove bounds on differences of confusion matrices for differently parameterized generalized Bayes classifiers.
strengths_and_weaknesses: strength: if they results hold, it would be of  theoretical interest.
weakness: there are lots of small notational issues in the paper.

The paper can be correct or wrong. it is hard to judge due to the brevity of the proofs.
The reviewer believes that many proofs needs to be extended to be readable.

eq(1) is superfluous: 1{\eta^*(x)>0.5} is either 0 or 1. Thus putting a Bernoulli in front of it makes no sense.

The paper makes a mistake in equation (3):
Confusion matrices contain joint probabilities
P( Y, \hat{Y} ), as also stated in line 141:
C_{1,1} + C_{1,2} + C_{2,1} + C_{2,2} =1
The true positive **rate**, however, is a conditional probability, conditioned on groundtruth being positive:
P(\hat{Y}=1| Y=1)  = P( \hat{Y}=1, Y=1 ) / P(Y=1) = \frac{ E_X[ P(Y=1|X=x) \hat{Y}(X=x)   ] }{  E_X[ P(Y=1|X=x)] }

the empirical true positive rate is given as

\frac{\sum_i Y_i \hat{Y}(X_i) }  {\sum_i Y_i}

not as (wrongly) stated in eq(3).

Their TN, TP terms inside the C matrices are joint probabilities:

TN + FP = P(Y=0)
FN + TP = P(Y=1)


TN + TP = P(Y=1,\hat{Y}=1) + P(Y=0,\hat{Y}=0)

ACC = P( Y= \hat{Y}  )

Theorem 3 is  wrong, but there might be a typo and they might mean stochastic classifiers.
 
take \hat{Y}(x) as the perfect oracle which can look at the ground truth label y_i in a pair (x_i,y_i) and use this to predict. This has accuracy 1 independent of P(Y=1|X=x). Therefore, theorem 3 does not hold for *any* classifier $\hat{Y}$.

Theorem 3 in  the appendix states it for a stochastic classifier, not for any classifier.

Lemma 18 in the supplement / line 579:

The statement of lemma 18 is trivially true if we assume that f and \eta can be anything: set f(\eta(x)) = P(\hat{Y}=1|X=x). Done.

The proof of Lemma 18 contains a problem:
E_{Z \sim P_X} [ \hat{Y}(Z) | \eta(Z)=\eta(x) ] is a conditioned expectation, conditioned on the set
P( \{ z: \eta(z) = \eta(x)\}) - this probability can be 0, then this conditional expectation can become undefined.

Lemma 18 would make sense if one considers \eta(x) to be P(Y=1|X=x) and thus \eta^*(x). Then the proof makes more sense.

line 589 in the supplement is wrong: it does not hold for any classifier, but for a stochastic classifier.



Lemma 20 and 21 seem to be correct - except for likely mixing up sup_{z \in A} f(z) > inf_{z \in B} f(z) in line 639 of the supplement
questions: Lemma 19: Moreover, since the actual proportions of positives and negatives are fixed - why does that hold?
 line 639 of the supplement: could it be sup_{z \in A} f(z) > inf_{z \in B} f(z) instead ? As far as the reviewer remembers, the essential supremum is up to removal of a set of measure 0.
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the problem of imbalanced binary classification. First, the Bayes-optimal classifier is generalized to any performance metric determined from the confusion matrix. This result is then employed to obtain regret bounds in terms of the error of estimating the class probability function under uniform loss. Second, a specific type of class imbalance (Uniform Class Imbalance) is proposed and analysis of how this affects the optimal classifier performance is carried out. Two numerical examples are provided to illustrate the theoretical results in the case of k-nearest neighbor classification.

The contributions of the paper are as follows:
1. A novel characterization of classifiers optimizing general performance metrics that are functions of a classifier's confusion matrix is derived.
2. The authors show that in general, a Bayes classifier always exists if one considers stochastic classifiers, but not if one considers only deterministic classifiers.
3. Performance guarantees are derived under more general performance measures in terms of the error of estimating the class probability function under uniform loss.
4. Analysis of k-nearest neighbor classification under uniform loss is provided.
strengths_and_weaknesses: Strengths:
+ Generalization of the Bayes optimal classifier to any performance metric computed from the confusion matrix.
+ Regret bounds in terms of the error of estimating the class probability function under uniform loss.
+ Definition and analysis of specific type of class imbalance.
+ Analysis and insights on the performance of k-nearest neighbor classification under uniform loss.

Weaknesses:
- Numerical experiments are provided only for synthetically generated datasets and not real-world imbalanced datasets.
- The motivation behind the proposed uniform class imbalance and the study of the k-nearest neighbor classifier is unclear.
- The abstract implies that classifier behavior is studied in the context of different types of class imbalance, which is not true.
- The definition of uniform class imbalance is unclear.
questions: 1. The numerical experiments provide certain confidence on the correctness of the theoretical results presented in the paper. However, it will be much more useful to see experiments in actual imbalanced datasets. Given the prevalence of imbalanced classification problems in practice and the plethora of algorithmic solutions, there is a large number of datasets available in the public domain. I understand that the numerical results included in the paper serve the role of verifying the theoretical contributions and sharing important insights in a more palatable way. However, providing actual experiments on real-world imbalanced datasets can provide unique insights and help practitioners understand on how to use the findings of this paper when developing their algorithmic solutions.

2. Currently, the abstract focuses primarily on imbalanced classification even though the generalization of the Bayes optimal classifier seems like a more general result. Furthermore, it implies that classifier behavior is studied in the context of different types of class imbalance, which is not true. I strongly suggest rewriting the abstract in much cleaner way to clarify the contributions of this line of work and place it in the right context.

3. The definition of uniform class imbalance is unclear in the sense that it seems to be defined in terms of the behavior of a regression function. I may have misunderstood the focus of the definition, but shouldn't class imbalance types be defined in a more generic way with respect to the structure of the data itself? Also, why not in terms of a general classification function? Finally, it is unclear what is the motivation behind the particular type of class imbalance and how often this is encountered in practice.

4. The motivation behind the study of the k-nearest neighbor classifier is unclear. Why this classifier? Is it commonly used in real-world imbalanced classification problems? How difficult it is to analyze the behavior of other types of classifiers, which are commonly used in practice for these types of problems?
limitations: The authors have adequately addressed the limitations of their work. However, they haven't discussed any potential negative societal impact of their work, and thus, they are encouraged to do so.
review_title: null

Meta-review: metareview: After discussion with the authors, reviewers are positive about this paper. Some loose ends remain, but it is impressive that the authors have discovered something new about binary classification, the single most intensively studied topic in all of ML.
confidence: Less certain
Decision: Accept