Optimal Binary Classification Beyond Accuracy
Authors: Shashank Singh
Justin Khim
Venue: NeurIPS 2022 Accept (2022)
Keywords: binary classification
imbalanced classification
bayes classifier
minimax risk
nearest neighbor classification

Abstract: The vast majority of statistical theory on binary classification characterizes performance in terms of accuracy. However, accuracy is known in many cases to poorly reflect the practical consequences of classification error, most famously in imbalanced binary classification, where data are dominated by samples from one of two classes. The first part of this paper derives a novel generalization of the Bayes-optimal classifier from accuracy to any performance metric computed from the confusion matrix. Specifically, this result (a) demonstrates that stochastic classifiers sometimes outperform the best possible deterministic classifier and (b) removes an empirically unverifiable absolute continuity assumption that is poorly understood but pervades existing results. We then demonstrate how to use this generalized Bayes classifier to obtain regret bounds in terms of the error of estimating regression functions under uniform loss. Finally, we use these results to develop some of the first finite-sample statistical guarantees specific to imbalanced binary classification. Specifically, we demonstrate that optimal classification performance depends on properties of class imbalance, such as a novel notion called Uniform Class Imbalance, that have not previously been formalized. We further illustrate these contributions numerically in the case of $k$-nearest neighbor classification.

this gen- Optimal Binary Classification Beyond Accuracy
Shashank Singh
Justin Khim Amazon New York, NY jk ikhimamazon..com com
Max Planck Institute for Intelligent Systems
Tübingen, Germany shassaankssinng444@gaaa....cc
Abstract
The vast majority of statistical theory on binary classification characterizes per- formance in terms of accuracy. However, accuracy is known in many cases poorly reflect the practical consequences of classification error, most famously in imbalanced binary classification, where data are dominated by samples from one of two classes. The first part of this paper derives a novel generalization the Bayes-optimal classifier from accuracy to any performance metric computed from the confusion matrix. Specifically, this result (a) demonstrates that stochastic classifiers sometimes outperform the best possible deterministic classifier and (b) removes an empirically unverifiable absolute continuity assumption that is poorly understood but pervades existing results. We then demonstrate how eralized Bayes classifier to obtain regret bounds in terms of the error of estimating regression functions under uniform loss. Finally, some of the first sample statistical guarantees specific to imbalanced binary classification. Specifically, we demonstrate that optimal classification performance depends on properties of class imbalance, such novel notion called Uniform Class Imbalance, that have not previously been formalized. We further illustrate these contributions numerically in the case of k-nearest neighbor classification.
use these results develop
Introduction
Many binary classification problems exhibit class imbalance, in which one of the two classes vastly outnumbers the other. Classifiers that perform well with balanced classes routinely fail for imbalanced classes, and developing reliable techniques for classification in the presence of severe class imbalance remains a challenging area of research [He and Ma 2013 Krawezyk] [016 Fernández et al.) [2018) Many practical approaches have been proposed to improve performance under class imbalance, including reweighting plug-in estimates of class probabilities [Lewis] 1995), resampling data to improve class imbalance [Chawla la et al., 2002), or reformulating classification algorithms to optimize different performance metrics [Dembezynski et al.) 2013] |Fathony and Kolter [2019 [Joachims) 2005). ) Extensive discussion of practical methods for handling class imbalance are surveyed in the books of
He and Ma 20133 and Fernández et al. 20188
Despite the pervasive challenge of class imbalance, our theoretical understanding of class imbalance limited. The vast majority of theoretical performance guarantees for classification characterize classification accuracy or, equivalently, misclassification risk [Mohri et al., 22018) which is typically an uninformative measure performance for imbalanced classes. Under measures that are used with imbalanced classes in practice, such precision, recall, F3 scores, and class- scores (Van Ri. jsbergen 1974 1979), existing theoretical guarantees are limited statistical consistency, in that algorithm under consideration asymptotically optimizes the metric of choice [Koyejo al.) 2014 Menon et al. 2013 Narasimhan et al. 2014]; specifically, there is no finite-sample theory that would
"The contributions in this paper were made prior to joining Amazon.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

allow comparison of an algorithm's 's performance to that of other algorithms or to theoretically optimal performance levels. Additionally, existing theory for classification does not explicitly model the effects of class imbalance, especially severe imbalance (i.e., as the proportion of samples from the rare class vanishes), and hence sheds little light on how severe imbalance influences optimal classification.
This paper provides two main contributions. First, in Section 4 we provide a novel characterization of classifiers optimizing general performance metrics that are functions of classifier's confusion matrix. This characterization generalizes classical result, that the Bayes classifier optimizes classification accuracy, to much larger class of performance measures, including those commonly used in imbalanced classification, while relaxing certain empirically unverifiable distributional assumptions that pervade existing such results. Interestingly, we show that, in general, a Bayes classifier always exists if one considers stochastic classifiers, but not if one considers only deterministic classifiers. We then use this result to provide relative performance guarantees under these more general performance measures, in terms of the error of estimating the class probability (regression) function under uniform (Loo)) loss.
This motivates our second main contribution: an analysis of k-nearest neighbor (kNN) classification under uniform loss. In doing so, we also propose an explicit model of a sub-type of class imbalance, which we call Uniform Class Imbalance, and we show that the ANN classifier behaves quite differently under Uniform Class Imbalance than under other sub-types of class imbalance. To the best of our knowledge, such sub-types of class imbalance have not previously been distinguished in either the theoretical or practical literature, and we hope that identifying such relevant features of imbalanced datasets may facilitate development of classifiers that perform well on specific imbalance problems of practical importance. Collectively, these contributions provide some of the first sample performance guarantees for nonparametric binary classification under performance metrics that are appropriate for imbalanced data and show how optimal performance depends on the nature of imbalance in the data.
Related Work
Here, we discuss how our results relate to existing theoretical guarantees for imbalanced binary classification and prior analyses of kNN methods.
2.1 Theoretical Guarantees for Imbalanced Binary Classification
Statistical learning theory has studied classification extensively in terms of accuracy [Mohri et al. 2018). However, when classes are severely imbalanced, accuracy ceases to be an informative measure of performance [Cortes and Mohri 2004], necessitating guarantees in terms of other performance metrics. Several papers have sought to address this Naaassmhaan al. 2014 2015 Koyejo et al.) 2014 Yan et al., 2018 [Wang et al. 2019a] by generalizing the Bayes optimal classifier, a well-known classifier that provably optimizes accuracy, to more general performance measures better reflecting the desiderata of imbalanced classification. Relatedly, several works have investigated relationships between these different performance measures and demonstrated that they differ essentially in how they determine the optimal threshold between the two classes [Flach] 2003] Hernández- Orallo et al.) 2013 Flach 2016). However, existing results make empirically unverifable assumptions about the distribution of the data, leaving questions about their relevance to real data. We discuss these assumptions in detail in Section 4 where our main result, Theorem 3 leverages the idea of stochastic thresholding to relax these assumptions.
Another body of closely related theoretical work studies Heyman-Pearee classification, which attempts to minimize misclassification error on one class subject to constraints on misclassification error on other classes, analogous to the approach of statistical hypothesis testing. While substantial theoretical guarantees do exist for Neyman- Pearson classification [Rigollet and Tong 2011 Tong 2013, Tong et al.) 2016)), these focus on performance within the Neyman- Pearson framework, rather than under general performance measures as in our work, and we know of no work considering stochastic classification under the Neyman-Pearse Pearsson framework. Interestingly, our use of stochastic classifiers in Theorem 3 parallels classical results in hypothesis testing [Lehmann and Romano 2006). and our proof of Theorem 3 involves reduction (Lemma) 22 in the Appendix) of optimization of general classification performance measures to Heyman-Pearson classification.
2

---

Meanwhile, many practical approaches to handling class imbalance, such as class blasswweighting and resampling have been proposed, but the theoretical understanding of these methods limited. wlaghtneig is a natural choice in applications where costs, or cost ratios [Flach] 2003). can be explicitly assigned and, in the case of binary classification, is statistically equivalent to threshold selection, which we discuss later in this paper (Scott, 2012]. In practice, resampling appears to be the most popular approach to handling class imbalance [He and Ma 2013]. Undersampling the dominant class is straightforward and can provide computational benefits with little loss in statistical performance [Fithian and Hastie, 2014], while interest in oversampling rare classes, sometimes referred to data augmentation, has grown with the advent of sophisticated generative models to produce additional data [Mariani et al. 2018). However, the theoretical ramifications of oversampling techniques used for imbalanced classification, most commonly variants of SMOTE [Chawla et al. 2002]. are poorly understood.
2.2 &NN Classification and Regression
The ANN classifier is of the oldest and most well-studied nonparametric classifiers Fix and Hodges [95T]. Early theoretical results include. Cover and Hart [967],, who showed that the misclassification risk of the &NN classifier with it is most twice that of the Bayes-optimal classifier, and 1977]. who showed that the ANN classifier is Bayes-consistenm
1: - op and the accuracy of :NN classification has since developed (Devroye
k/n 0. Extensive literature Sammorth 2012 Chaudhuri and Dasguptal 2014] Gottlieb et al.
iet al. 1996. Györf et al.] 2002,
2014 Biau and Devroye 2015 Gadat al.
2016 Döring et al. 2018 Kontorovich and Weiss 2015
Gottlieb et al. 2018 Cannings et al. 2019
Hanneke et | 2020].
Rather than accuracy bounds for ANN classification, the bounds uniform error present in
Section 5 are most closely related to risk bounds for ANN regression, of which the results of BBau et al. 2010 representative. [Biau et al. [010)] gives convergence rates for kNN regression in L2 risk, weighted by the covariate distribution, in terms of noise variance and covering numbers of the covariate space. While closely related to our bounds
uniform (Cx) risk, their results differ in
at least three main ways. First, minimax rates under Loo risk are necessarily worse than under La risk by logarithmic factor, as implied by our lower bounds. Second, the fact that Biau et al. [2010) use a risk that is weighted by the covariate distribution allows them to avoid our assumption that the covariate density is lower bounded away from O, whereas, the lower boundedness assumption is unavoidable under Cop risk. Finally, Biau et al. (010) assume additive noise with finite variance; Bernoulli noise is crucial for us to model severe class imbalance.
Extensive research on KNN for imbalanced classification has focused on algorithmic modifications, which are surveyed by Fernández et al. (2018). Examples include prototype selection [Liu and Chawla la 2011 López et al. 2014 Vluymans et al.] [016]) and gravitational methods [Cano et al. 2013
hu et al.] 2015). We aware of no statistical guarantees exist for such methods.
3 Setup and Notation
Let (X p) be separable metric space, and let y {00, 1} denote the set of classes. For any
E X' and c > 0, c(z,c) := {= E X p(x, 2) < c} denotes the open radius-c ball around
x. Consider n independent samples (II, (Xn, Yn) drawn from a distribution Px, on
X' x )' with marginals Px and Pr. For positive sequences 100 and 12 an = b, means lim inf an/b, > and lim sup an/b,, < 00.
To optimize general performance metrics, we must consider stochastic classifiers. Formally, letting B : (Y~ Bernoullipp) : p E [0, 1]} denote the set of binary random variables, a stochastic classifier can be modeled as a mapping Y: : X - B, where, for any x E X, E Ex(())) is the probability that the classifier assigns Z to class 1. We use SC to denote the class of stochastic classifiers.
The true regression function 1/* X - [0, 1] is defined as 1)x(2) := P[Y- = 1|X = xr] = E [ ærI: that is. given an instance X,, the label Y; is Bernoulli-distributed with mean n(X)). As we show in the next section, an optimal classifier can always be written in terms of the true regression function 7, motivating estimates 7 X [0, 1] of 17. Such estimates 7 are referred to as "regressors".
3

---

Optimal Classification Beyond Accuracy
famous result states that classification accuracy is maximized by the "Bayes" classifier
(x) Bernoulli (1)))(()) > 0.5)).
(I)
Here, (xx) is simply constant (deterministic) random variable that takes either the value or the value 1 with probability (depending 17" (z)). Our reason for writing Eq. (1) in this seemingly redundant way will become clear with Definition below.
Although n7* is unknown in practice, this result is cornerstone of the statistical theory of binary classification because provides an optimal performance benchmark against which a classifier can be evaluated in terms of accuracy (Devroye et al. [996] Mitchell 1997 James et al. [013]. As discussed previously, accuracy can be poor measure of performance in the imbalanced case. Therefore, the main contribution of this section, provided in Theorem 3 below, is to generalize this result to broad class of classification performance measures, including those commonly used imbalanced classification. First, we specify performance measures for which our results apply.
[997|amms
4.1 Confusion Matrix Measures (CMMs)
Nearly all measures of classification performance, including accuracy, precision, recall, Fg scores, and others, can be computed from the confusion matrix, which counts the number of test samples each (true class, estimated class) pair. Formally, C. :- {Ce e [0, 1j2x2 C₁ + C1 C2,1 + C2,2 1) denote the set all possible binary confusion matrices. Given classifier Y, the confusion matrix Cg E and empirical confusion matrix Cg C. are given by
Cp
TN FN
FPy TPp
C
TN y FN
FP TPp
()
wherein the true positive probability T and empirical true positive probability TPp are given by
TP3 = E (x))((()) TPP 1 n Σ (x)),
(3)
and the true and empirical false positive (FPý and FPy.). false negative (FNg and FN and true positive (TP& and TPy)) probabilities are defined similarly. Note that the expectation in Eq. (3) is over randomness both in the data and in the classifier.
Intuitively, measures of classifier's performance should improve TN and TP increase and FN and FP decrease. We therefore define the class of Confusion Matrix Measures (CMMs) as follows:
Definition 1 (Confusion Matrix Measure (CMM)). A functin M C - R is called a confusion matrix measure (CMM) if. for any confusion matrix
TN
FP
[TN+ FN TP TP+
FP -
C
e CC, [O,FP), FN], we have M(C) & M TP
FN
Essentially, correcting an incorrect classification should not reduce a CMM. This true of any reasonable measure of classification performance, and hence analyzing CMMs allows to obtain theoretical guarantees for all performance measures used in practice. Specifically, by evaluating their gradients in the directions 1 -1 and o 2 one can verify that most performance measures, such as weighted accuracy, precision, recall, F3 scores, and Matthew's 's Correlation Coefficient are CMMs. We note that the area under receiver operating characteristic (AUROC) and area under precision-recal curve (AUPRC) are not CMMs because they evaluate (R-valled) scoring functions rather than (/0, 1}-valued) classification functions. However, both AUROC and AUPR are averages of CMMs computed at various classification thresholds, and, as we discuss in Appendix A. our results for CMMs thus imply similar results for these measures. We next present our main result of Section which generalizes the Bayes classifier I to arbitrary CMMs.

---

4.2 Generalizing the Bayes Classifier
The Bayes classifier thresholds the regression function deterministically at the value 0.5. The following generalizes this to stochastic threshold:
Definition 2 FRegression-Threshoooeo
Classifier (RTC)). classifier V X B is called ggrressionthheshooldig classifier (RTC) if. for some p. t E [0. 1] and 11 X [0. 1].
Ý (x) Bernoulli(p 1(((a)) = t] + 1((())) >f), for all x E N.
In the sequel, we will denote such classifiers Ppt. and refer to the pair (1, as the threshold.
Now we can state the main result of this paper:
Theorem 3. For any CMM M and stochastic classifier Y, there is an RTC Ppa. with M (YPa..) 2 M ). In particular, if M is maximized by any stochastic classifier, then M is maximized by RTC.
As special case of Theorem 3 the classical Bayes classifier corresponds M(C) TN + TP. 0. and t = 0.5. However, as discussed in the next paragraph. without stronger assumptions, Theorem does not hold for deterministic classifiers. Since RTCs generalize both the RTC structure and optimality properties of the Bayes classifier, we also refer to them as generalized Bayes classifiers. We note that existence of any maximizer Ý of (C²) ) may depend on specific properties, such as (semi)continuity or convexity of M, which we do not investigate here.
We emphasize that Theorem 3 makes absolutely no assumptions on the distribution of the data. In particular, all prior characterivations optimal classifiers under general performance metrics assume that the distribution of the class probability of X)) is absolutely continuous (Narasihhan et al. 2014 2015 Koyejo al., 2014| Yan al. 2018 Wang et al., 2019a and Wang al. [209a]] claim that regularity assumptions on (7(x)) such as absolute continuity "seem to be unavoidable". Our Theorem is the first result to omit such assumptions, and we specifically show that this comes at the cost of the optimal classifier possibly being non-deterministic for single atom of 17( vX). Figure]] visually compares the stochastic thresholding classifier in Theorem 3 to prior approaches.
Mixture of Deterministic
Classical Bayes
Deterministic
Stochastic (ours)
0.8
77
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.0
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
m(A)
m(x)
((x)
m(x)
Figure 1: Examples of four different approaches to thresholding the regression function. Classical Bayes thresholding (Eq. (T)) always thresholds deterministically at 17(x) = 0.5 to optimize accuracy. Koyejo et al. [2014). Narasimhan et al. (2014) and others have suggested using other Deterministic
thresholds (c.g.. ( 0.3, shown here) to optimize other CMMs, assuming ry(X) is absolutely
continuous. Wang et al. 2019a] showed that the optimal classifier can always be written as Mixture of Deterministic (MD) classifiers (e.g., a (0.3, -ii)-me of thresholds at 7)x)) 0.2 and 1)(x) = 0.4, shown here). Finally, we propose using a single Stochastic threshold (e.g., (t. = (0.3. 0.75), shown here). Only MD and Stochastic approaches are optimal in general (for arbitrary CMMs, without 7/ (X) absolutely continuous), while Stochastic thresholding is strictly simpler than MD.
The generality of Theorem necessitates a significantly more complex proof than prior work. In particular, prove Theorem 3 in Appendix A using series of variational arguments. Roughly speaking, given a classifier Y, we construct a perturbation G of Y such that either ACCc)
EEceetioos for the case of Fi score are Zhao et al.
2013 Lemma 12) and Lipton et al. 2014
Theorem 1].
5

---

M(C),) or Y is an RTC and M(C)) < M(C).). Since, the classifier Ý might be quite poorly behaved (e.g., its behavior on sets of Px-measure could be arbitrary). the technical complexity lies in constructing admissible perturbations (i.e., those that are well-defined classifiers). For this reason, the proof of Theorem 3 involves series of constructions of increasingly well-behaved classifiers.
Theorem 3 tells us that a generalized Bayes classifier can always be written in terms of the regression function 7 and two scalar parameters (t. depending on the distribution of n(X) and the CMM M. The next example shows that this characterization cannot be simplified without stronger assumptions:
Example 4. Suppose X' {0) is a singleton, 17(0) E (0, 1), and, for some 0 > 0. M(())
(TP) One can check that M is a valid CMM. Suppose Y is an RTC. It is straightforward to compute that M(Cp) = (pn(()) ( - (1 (()))1{tt = sy(0),, and that (Cp) is uniquely maximized by Ø+I E (0, 1) and = n(0) E (0, 1). This shows that both threshold parameters and in an RTC are necessary, in the absence of further assumptions on M or 77. This example also illustrates the need for stochasticity to optimize general CMMs. Specifically, for any deterministic classifier Y, either P(0)= = 0 (so TP- or Ý (0) = 1 (so TN- 0); in either case, MCp) O.
This performance gap between stochastic and deterministic classifiers is closely related to Theorem 1 of Cotter et al. 2019bb. which provides closely related lower bound how well stochastic classifier can be approximated by a deterministic one, in terms of the probability assigned to atoms of (X). However, Cotter et al. [2019b) only study how well stochastic classifiers can be approximated by deterministic ones (with the motivation of derandomizing classifiers), not whether stochastic classifiers can systematically outperform deterministic ones, as we show here.
4.3 Relative Performance Guarantees in terms of the Generalized Bayes Classifier
Theorem motivates a two-step approach to imbalanced classification in which one first estimates the regression function 17 and then selects stochastic threshold (t, that optimizes empirical performance M (Ctg).. Such an approach has many practical advantages. For example, as we show in Appendix D simple algorithm can exactly optimize the threshold (f,p) over large datasets in On 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 (t, p). which is statistically and computationally much easier than retraining a classifier from scratch. In this section, we focus on an advantage for theoretical analysis, namely that the error of such classifier decomposes into errors in selecting (1. p) and errors in estimating 7), allowing the derivation of performance guarantees relative a generalized Bayes classifier. All results in this section are proven in Appendix B
We first bound the performance difference of thresholding two regressors in terms of their Cx distance. This will allow us to bound error due to using a regressor 7) instead of the true 1).
Lemma 5. For p,t [0, 17, n, n : X - [0, 17. Cpp..
pic.n Cp pitas
& PP (X() E = In 7 7-lool
Intuitively, Lemma bounds the largest difference in the confusion matrices of Pp.t.n and Py.t.r by the probability that the threshold lies between and n/. As we will show later, under margin assumption, this can be bounded by the Cae distance between 17 and r/'
Our next lemma bounds the worst-case error over thresholds (t.p) E [o, 1] of the empirical confusion matrix. This allows us to bound error due to using empirical threshold (Ê,p) instead of the threshold (t* .p*) that is optimal for the true regression function.
Lemma 6. Let n X [0, 1] be any regression function. Then, with probability at least 1 8,
16
8
32(2n + 1)
sup pote
CD
Cg
log
8
n
8
Lemma 6 follows from Vapnik-Clie Chervonenkis (VC) bounds on the complexity of the set (Pp.... p, t [J of possible RTCs with fixed regression function 7). In fact, Appendix B proves more general bound on the error between empirical and true confusion matrices uniformly over any family F of stochastic classifiers in terms of the growth function of F. Consequently, when F has finite VC dimension, we obtain uniform convergence at the fast rate / Vlog(n/8)/r As we formalize later, this

---

log suggests that the difficulty in tuning an imbalanced classifier to optimize a CMM M comes not from difficulty in estimating the confusion matrix but rather from the sensitivity of commonly used CMMs to the selected threshold. Because Theorem 3 shows that any CMM can be optimized by RTC, we state here only the specific result for RTCs.
Before combining Lemmas[jand give the main result of this section, we note a margin assumption, which characterizes separation between the two classes:
Definition (Tsybakov Margin Condition). Let C, e O, t E 1). A classification problem with covariate distribution Px and regression function r) satisfies (C, B) -margin condition around t if. for any > 0, P [l) - tl & c & Cc.
The Tsybakov margin condition, introduced by Mammen and Tsybakov [1999] for = 0.5, is widely used to establish convergence rates for classification in terms of accuracy (Audibert and Tsybakov 2007 Arlot and Bartlet 2011 Chaudhuri and Dasgupta 2014]. Together with the margin condition and a Lipschitz condition on the M, Lemmas 5 and 6 give the following bound on sub-optimality of
an RTC if the threshold is selected by maximizing M over the empirical confusion matrix:
Corollary 8. Let 11: X - [0. 1] be the true regression function and î) X [0, 1] be any regressor.
Let
(p. (t.p)e[0.1j2
argmnax M (Cineis) and (p=++)=== argmax M (Orpsn) (1.p)=(0,1]3
denote the empirical and true optimal thresholds, respectively. Suppose M is Lipschitz continuous with constant Lm with respect the uniform (Lx) metric on C. Finally, suppose Px and n satisfy (C, margin condition around t* Then, with probability " 1- 8.
M (Cg M (Crg.s)
8 C11n Tll 2
32 1)
Las
n
Uniform Error of the ANN Regressor
In the previous section, we bounded relative performance of an RTC in terms of uniform (Coo) loss of the regression function estimate. Here, we bound uniform loss of one such regressor, the widely used k-nearest neighbor (kNN) regressor. Our analyses include parameter r, introduced in Section 5 that characterizes a novel sub-type of class imbalance, which we call Uniform Class Imbalance. This leads to insights about how the behavior of the kNN classifier depends not only on the degree, but also on the structure, class imbalance in a given dataset. We begin with some notation:
Definition 9 (k-Nearest Neighbor Regressor). Given a point x E X, let a(x) denote a permula- tion of (1, ..., n) such that Xa,(x) is the ith -nearest neighbor of x among XI....,,,,, For integers E [1,n]] nl. the kNN regressor Îi X + [0, is defined as
1 k Yn for all x X.
- k
(x(=))
(4)
We now formalize a novel sub-type of class imbalance:
Definition 10 (Uniform Class Imbalance (UCI)). Write the regression function as 1) = rG, where r E (0, 1] and ( X - [0, 1] is a regression function with supaex ((x) 1. A classification problem has Uniform Class Imbalance (UCI) in the number of samples n if - 0 as - s.
Intuitively, in UCI, the class Y 1 is rare regardless of X. This includes "difficult" classification problems where the covariate X provides only partial information about the class Y and examples from the rare class lie deep within the distribution of the common class. Examples include rare disease diagnosis [Schaefer et al,, 2020] or fraud detection (Awoyemi et al. 2017]. In practice, the classifier's ' role is often to flag "high-risk" samples X, those with 7(X) relatively high, for follow-up investigation. UCI can be distinguished from "easier" problems in which, for some x E X, (X) > 1 and so, given enough training data, classifier can confidently assign the label Y 1. These include well-separated classes or deterministic problems (e.g., protein structure prediction; Noć et al. (2200).
To our knowledge, such notions of class imbalance have not previously been distinguished. In the particular case of data drawn from a logistic model, UCI reduces to the notion of class imbalance described in Wang 2020]: however, UCI applies in more general contexts.
7

---

5.1 Uniform Risk Bounds
We now present bounds (proven in Appendix C.1 on uniform error |リ- fr suprex In(a))-(()) of the KNN regressor îß. First, recall two standard quantities, covering numbers and shattering coefficients, by which we measure complexity of the feature space:
Definition 11 (Covering Number). Suppose (X, p) is totally bounded metric space. Then, for any <> 0, the e-covering number (e) of (X, p) is the smallest integer such that there exist (
points 21, NNe) E X satisfying X' (C(c)
= B(I,,e).
Definition 12 (Shattering Coefficient). For integers ni > 0, the shattering coefficient of balls in (K, is (n)
sup
[[ Un) B(x,e) I X, > 0f/.
We now state assumptions data distribution Px,y:
Assumption 13 (Dense Covariates Assumption). For some P+: 6* d > O, the marginal distri- bution Px of covariates is lower bounded, for any x X and e E (0, <* by Px(B.(x)) > P.c
Assumption ensuures that each query point's nearest neighbors are sufficiently near to informative. We also assume that the regression function Ç is smooth:
((x)) < C0.
Assumption 14 (Hölder Continuity). For some E (0, L = sup sup't (=(2,"")
We now state upper bound on uniform enror:
Theorem 15. Under Assumptions
13 and 14
whenever k/n & pn(e*)4/2, for any 8 0, with
probability at least 1 - N ((2k/ (pek) 1/d
k/4
8, we have
2k
a/d
2
25(n)
2r
25(n)
In 7l & 2d Lr
log
+
log
(5)
P&n
3k
8
k
5
Ifr O (log ((n)/m), this bound minimized by k n, giving Otherwise, this bound is minimized by k = nan+a (log S(n) 2ntar 2nta giving
|n7 2o Op ((log S(n))/n).
1n 7l Op ((llgg ((n))/n) zo+a Zo4d
Of the three terms in (5) the first term, of order rkk/n)a/d comes from smoothing bias of the ANN classifier. The second and third terms are due label noise, with the second term dominating under extreme class imbalance r e O (log ((n)/n)) and the third term dominating otherwise. Theorem 5 shows that, under UCI, one should use much larger choice of the tuming parameter À than in the case of balanced classes; indeed, setting = n 2a (log ((n)) zata, which is optimal the balanced case, gives a rate that is suboptimal by factor of r ddd(da++d))
The following example demonstrates how apply Theorem 15 in concrete setting of interest:
Corollary 16 (Euclidean, Absolutely Continuous Case). Suppose (X' = (IO, 1] 1--21-1122 11122) is the unit cube in Rd, equipped with the Euclidean metric, and Px has a density that is lower bounded away from 0 on X. Then, for = Ior (log n1) x 2=
|| T E Op (((log ()/og)nn//) 2n44
The most problematic term in this bound is the exponential dependence on the dimension d of the co- variates. Fortunately, since Theorem 15 utilizes covering numbers, it improves if the covariates exhibit structure, such that of low-dimensional manifold. We illustrate this in detail in Appendix C.I
We close with a minimax lower bound, proven Appendix C.2 on the uniform error of any estimator, over (a, L) Hölder regression functions. Up polylogarithmie factor in the rate of this lower bound matches that Theorem [5] suggesting that both bounds are quite tight.
Theorem 17. Suppose X [0. 1]d the d-dimensional unit cube and X Uniform(2)) Let Ex (L) denote the family of (a, L) Hööder continuous regression function. Then, there exist constants

---

no and c >> 0 (depending only on L, and d) such that, for all 2 and any estimator 17.
(log(nr)
20
1
P 11 71.0 2 c (L)
sup
20+2
n
8
Discussion Plugging the above upper bounds on || 7 into Corollary provides error bound under arbitrary CMMs, in terms of the sample size n, hyperparameter k, UCI degree r, and complexity parameters (margin 3, smoothness collectively give some of the first complete finite-sample guarantees under general performance metrics used for imbalanced classification. Our analysis shows that, under severe UCI, the optimal k is much larger than in balanced classification, whereas this same i leads to sub-optimal, or even inconsistent, estimates of the regression function under other (nonuniform) forms of class imbalance.
intrinsic dimension d, etc.) of X' and Px,Y. Thus, these results
6 Numerical Experiments
We provide two numerical experiments to illustrate our results from Sections repeat each experiment 100 times and present average results with 95% confidence intervals computed using the central limit theorem. Python implementations and instructions for re- producing each experiment can be found at https: //gtt///////bb../ tuebingen. mpg de/shashank/ iibaalaaced-bbnaryy- waw.aaar--lssssfiaaaa.a.a ieticcaiioo-eepeimmmmteee.ee
4 and We
Further technical details regarding the experiments can be found in Appendix while Appendix F explores some predictions of our theoretical results on real data from a credit card fraud detection problem.
Experiment Example showed that, under general CMMs, deterministic RTCs are sometimes unable to approach optimal classification performance, necessitating stochastic RTCs. This experi- ment demonstrates this gap numerically, Suppose X [0. 1J. over which X is uniformly distributed, and for all E X, v(()) = 0.5 1(1/3 & x < 2/3) + 1 < x).
Consider the CMM M(C = TP. . TN. Similar to the analysis in Example 4 the optimal value of (CC (5/12)²
achievable only by a stochastic classifier, whereas as deterministic classifiers achieve at most (C) = 1/6 < 25/144.
For 10 logarithmically spaced values of n between 102 and 10 drew independent samples of (X, Y) according the above distribution. Using this training data, we selected optimal deterministic and stochastic thresholds & e [o, 1] and (t,p) e [0, for the ANN classifier by maximizing M(C) over t uniformly spaced values in [o, 1] and [o. 1]2 respectively. Since, in this example, d 1, we set 2/3 as suggested by Theorem 16 As another point of comparison, we also include very different deterministic classifier, a random forest, trained with default parameters of Python's 's scikit- -learn package. We estimated M() using 1000 more independently generated test samples of (X.Y). Figure 2a shows regret, i.e., sub-optimality of each classifier relative to the optimal classifier, terms of M (C). Consistent with our analysis, regrets of the deterministic classifiers are bounded away from 0, while regret of the stochastic classifier vanishes increases.
This experiment demonstrates that making classifiers robust to severe class imbalance requires distinguishing different sub-types of class imbalance, such as UCL. Suppose X' [0, 1]. X Uniform((( (0) 1)). and r (0, 1). Consider two regression functions 7) ())x = r(1 x) and (1))) = max 1 2/r3. тΙ1 and 7/2 exhibit the same overall class imbalance, with r/2 proportion of samples from class 1. The regression function 7/1 satisfies UCI degree r, whereas 1/2 does not satisfy nontrivial degree of UCI. For sufficiently small E (0, 1), specifically r E o (n -d/(2x+2))) Theorem 15 gives that the optimal choice of & under 7)I satisfies e w(n)). On the other hand, if ke E wrrn), then, under 72, E [ (0) - 0, so that (0) is an inconsistent estimate of (0) =
Experiment 2
For 10 logarithmically spaced values of n between 1 and 10 we drew independent samples of (X,Y7 Y) according the joint distributions corresponding to each of 7)1 and 172- Since, in this example, a d 1, to ensure r E (n-44 4n-o/(2o+20)))
we set r = 112 As indicated by Corollary 16 we set k- = 11/33 We then computed L. and L1 distances between the &NN regressor (Eq. 4 and true regression function. We also drew 1000 independent test samples of (X, Y) and used these to estimate the F1 score of thresholding the ANN regressor at threshold t determined by optimizing the

---

Uniform Ernor (I/n All--
Deterministic Stochastic
Qlio All-
0.010
5. Ragrat
10
Regret
Random Forest
1."
0.005
10
10
10 Sample (n)
10*
16
10a
10
-10*
10a
10a
10
10a
10
Sample Size (n)
Sample Size (n)
Sample Size (n)
Experiment 1
(b) Experiment
Figure 2: (a) Regret of deterministically and stochastically thresholding the kNN classifier, under the CMM (C) TP. TN. (b) Uniform (Cop) and average (L1) errors of KNN regressor, as well as Fi regret of estimating regression functions and 7/2. Error bars indicate 95% confidence intervals.
empirical Fi score (over the training data) over 100 uniformly-spaced values of [0,1]. 1]. Figure 2b shows the uniform (Cx)) error, the average (C1) emror, and the Fi regret, which bounded in Corollary 8 Consistent with our analysis above, the uniform (Cz.) error decays to under 1 but not under 72- Meanwhile, the average error (Ci) decays to under both 7/2 and 7/2- Consistent with
Corollary g the F1 regret the thresholded classifier, which decays to under 1/ but not under 7/2 mirrors performance of the regressor in uniform (Lo)) error rather than average (L1) error.
7 Conclusions
Our main conclusions follows. First, without any assumptions the data-generan tettaagenerating distribu- tion, the Bayes-optimal classifier generalizes from accuracy to other performance metrics using a stochastic thresholding procedure, while, in general, deterministic classifiers may not achieve Bayes- optimality. This generalized Bayes classifier provides an optimal performance benchmark relative to which one analyze classifiers that threshold estimates of the regression function. This includes the under uniform
KNN classifier, for which we provided new guarantees, including minimax-optimall loss in the presence Uniform Class Imbalance. Our results imply that the parameter & needs to be tuned differently for different sub-types of imbalanced classification, suggesting that developing reliable classifiers for severely imbalanced classes may require a more nuanced understanding of the data at hand. Further work is needed to (a) understand how sub-types of class imbalance can be distinguished in practice, (b) develop adaptive classifiers that perform well under multiple imbalance sub-types, and (c) extend our results to the multiclass case.
While this paper focused statistical properties of stochastic classification, we should point that using stochastic classifiers real applications may require careful consideration of possible downstream consequences. On one hand, Theorem provides justification for using (a limited degree of) stochasticity to break certain ties between classes: sometimes, this is provably necessary optimize performance according to certain metries. Stochastic classifiers can also be easier to train [Cotter et al., 2019a| Lu et al.) 2020 or more robust to adversarial examples [Pinot et al. 2022]. However, stochastic classifiers have risks, including being harder interpret, explain, or debug. and being vulnerable to manipulation by downstream users (e.g., user might query the classifier multiple times produce desired prediction). Stochastic classifiers may also violate certain notions of fairness, as individuals with identical features might be assigned to different classes. Techniques for derandomizing classifiers [Cotter et al. 2019b Wu al. 2022 may help address these issues.
Acknowledgments and Disclosure of Funding
This work was supported by the German Federal Ministry Education and Research (BMBF) through the Tübingen AI Center (FKZ: QIISI8039B
10

---

References
Sylvain Arlot and Peter L Bartlttt Margin-adaptive model selection in statistical learning. Bernuuli, 17(2):67-7713, 2011.
Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2))608 2007.
John O Awoyemi, Adebayo O Adetunmbi, and Samuel A Oluwadare. Credit card fraud detection using machine learning techniques: A comparative analysis. In 2017 International Conference on Computing Networking and Informatics (ICCNI), pages 1 1-9. IEEE, 2017.
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962.
Gérard Biau and Luc Devroye. Lectures on the Nearest Neighbor Method. Springer, 2015.
Gérard Biau, Frédéric Cérou, and Arnaud Guyader. Rates of convergence of the functional k-nearest neighbor estimate. IEEE Transactions Information Theory, (664))::034-204) 2010.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: Nonasymp-
totic Theory of Independence. Oxford University Press, 2013.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, pages 169-207. Springer, 2003.
Timothy I Cannings, Thomas Berrett, and Richard J Samworth. Local nearest neighbour clas- sification with applications to semi-supervised learning, arXiv preprint arXiv:1704.0064 v3, 2019.
Alberto Cano, Amelia Zafra, and Sebastián Ventura. Weighted data gravitation classificatton for standard and imbalanced data. JEEE Transactions Cybernetics, 43(6):1672-1687) 2013.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, pages 3437-3445, 2014.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. SMOTE: synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 16:321-357, 2002.
Corinna Cortes and Mchryar Mohri. AUC optimization vs. error rate minimization. Advances in
Neural Information Processing Systems, 16(16):313-30,, 2004.
Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In Algorithmic Learning Theory, pages 300-332. PMLR, 2019 9a.
Andrew Cotter, Harikrishna Narasimhan, and Maya R Gupta. On making stochastic classifiers deterministic. Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21-27, 1967.
Krzysztof Dembezynski, Arkadiusz Jachnik, Wojciech Kotlowski, Willem Waegeman, and Eyke Huellermeier. Optimizing the F-measure in multi-label classification: Plug-in rule approach versus structured loss minimization. In Proceedings of the 30th International Conference Machine Learning. PMLR, 2013.
Krzysztof Dembezyúski, Wojciech Kotlowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Con- sistency analysis for binary classification revisited. In International Conference on Machine Learning, pages 961-969. PMLR, 2017.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition. Springer Science Business Media, 1996.
Maik Döring, Lászłó Györfi, and Harro Walk, Rate of convergence k-nearest-neighhor classification rule. The Journal of Machine Learning Research, 18(227):1-16, 2018.

---

Rick Durrett. Probability: Theory and Examples. Cambridge university press, fourth edition, 2010.
Rizal Fathony and Zico Kolter. AP-perf: Incorporating generic performance metrics in differentiable learning. arXiv preprint arXiv:1912.00900 2019.
Alberto Fernández, Salvador García, Mikel Galar, Ronaldo C Prati, Bartosz Krawezyk, and Francisco Herrera. Learning from Imbalanced Data Sets. Springer, 2018.
William Fithian and Trevor Hastie. Local case-control sampling: Efficient subsampling in imbalanced data sets. Annals of Statistics, 42(5):1693, 2014.
Evelyn Fix and Joseph Hodges. Discriminatory analysis- discrimination: consistency properties. Technical report, USAF School of Aviation Medicine, Randolph Field, Texas, 1951.
Peter A Flach. The geometry of ROC space: understanding machine learning metrics through isometrics. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 194-201, 2003.
Peter Flach. Classifier calibration. In Encyclopedia of Machine Learning and Data Mining. Springer US, 2016.
Sébastien Gadat, Thierry Klein, and Clément Marteau, Classification in general finite dimensional spaces with the k-nearest neighbor rule. The Annals of Statistics, 44(3):982-1009, 2016.
L. Gottlieb, A. Kontorovich, and P. Nisnevitch. Near-optimal sample compression for nearest neighbors. IEEE Transactions on Information Theory, 64(6)::120-411 4128, 2018.
Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient classification for metric data. IEEE Transactions on Information Theory, 60(9):5750-$759, 2014.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk, distribution-free theory of nonparametric regression. Springer Science & Business Media, 2002.
Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal Bayes consistency in metric spaces. In 2020 Information Theory and Applications Workshop (ITA), pages 1-33. IEEE,
2020.
Haibo He and Yunqian Ma. Imbalanced Learning: Foundations, Algorithms, and Applications. John Wiley & Sons, 2013.
José Hernández-Oralln Orallo, Peter Flach, and César Ferri. Roc curves in cost space. Machine learning, (1):71-91, 2013.
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An Introduction Statistical Learning, volume 112. Springer, 2013.
Thorsten Joachims. A support vector method for multivariate performance measures. In Proceedings of the 22nd International Conference on Machine Learning, pages 377-384. ACM, 2005.
Aryeh Kontorovich and Roi Weiss. A Bayes consistent 1-NN classifier. In Artificial Intelligence and Statistics, pages 480 488. PMLR, 2015.
Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit Dhillon. Con- sistent Binary Classification with Generalized Performance Metries. In Advances in Neural Information Processing Systems 27, pages 2744-7752 Curran Associates, Inc., 2014.
Bartosz Krawezyk. Learning from imbalanced data: open challenges and future directions. Progress in Artificial Intelligence, 5(4):221 222, 2016.
Erich I. Lehmann and Joseph Romano. Testing Statistical Hypotheses. Springer Science & Business Media, 2006.
David D Lewis. Evaluating and optimizing autonomous text classification systems. In SIGIR, volume 95, pages 246-254. Citescer, 1995.
12

---

Zachary C Lipton, Charles Elkan, and Balakrishnan Naryanaswany. Optimal thresholding of classifiers to maximize fl measure. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 225-239. Springer, 2014.
Wei Liu and Sanjay Chawla. Class confidence weighted knn algorithms for imbalanced data sets. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 345-356. Springer, 2011.
Victoria López, Isaac Triguero, Cristóbal J Carmona, Salvador García, and Francisco Herrera. Addressing imbalanced classification with instance generation techniques: IPADE-ID. Neurocom- puting, 126:15-28, 2014.
Zhihe Lu, Yongxin Yang, Xiatian Zhu, Cong Liu, Yi-Zhe Song, and Tao Xiang. Stochastic classifiers for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9111-9120, 2020.
Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 1708)1988 1999.
Giovanni Mariani, Florian Scheidegger, Roxana Istrate, Costas Bekas, and Cristiano Malossi. Bagan: Data augmentation with balancing GAN. arXiv preprini arXiv: 1880.09955, 2018
Colin McDiarmid. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195-248. Springer, 1998.
Aditya Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statistical con- sistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 603-611, 2013.
Tom M Mitchell. Machine Learning. McGraw-hill New York, 1997.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018
Harikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. On the statistical consistency of plug-in classifiers for non-decomposable performance measures. In Advances in Neural Information Processing Systems, pages 1493-1501, 2014.
Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha, and Shivani Agarwal. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pages 2398-2407. PMLR, 2015.
Frank Noé, Gianni De Fabritüis, and Cecilia Clementi. Machine learning for protein folding and dynamics. Current Opinion in Structural Biology, 60:77-84, 2020.
Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Gouy-Pailler, Yann Chevaleyre, and Jamal Atif. On the robustness of randomized classifiers to adversarial examples. Machine Learning, pages 1-33, 2022.
Philippe Rigollet and Xin Tong. Neyman-Pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12(0ct):2831-288) 2011.
Richard Samworth. Optimal weighted nearest neighbour classifiers. Annals of Statistics, 40(5): 2733-2763, 2012.
Julia Schaefer, Moritz Lehne, Josef Schepers, Fabian Prasser, and Sylvia Thun. The use machine learning in rare diseases: a scoping review. Orphanet Journal of Rare Diseases, 15(1):1-10, 2020.
Clayton Scott. Calibrated asymmetric surrogate losses. Electronic Journal of Statistics, 2012.
Charles Stone. Consistent nonparametric regression. The Annals of Statistics, pages 595 995-620, 1977.
Xin Tong. plug-in approach Neyman-Pearsnn classification. The Journal of Machine Learning Research, 14(1):301130400 2013.
13

---

Xin Tong, Yang Feng, and Anqi Zhao. A survey on Seyman-Pearson classification and suggestions for future research. Wiley Interdisciplinary Reviews: Computational Statisties, 8(2):64 1144--1,1-1 2016.
Alexandre B Tsybakov. Introduction Nonparametric Estimation. Revised and extended from the 2004 French original. Translated by Vladimir Zaiats. Springer Series in Statistics. Springer, New York, 2009.
Cornelis Joost Van Rijsbergen. Foundation of evaluation. Journal of Documentation, 30(4):365-373, 1974.
Cornelis Joost Van Rijsbergen. Information Retrieval. Butterworth-Heinemmmn London, 2nd edition, 1979.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity, pages 11-30. Springer, 2015.
Sarah Vluymans, Isaac Triguero, Chris Cornelis, and Yvan Saeys. EPRENNID: An evolution- ary prototype reduction based ensemble for nearest neighbor classification of imbalanced data. Neurocomputing, 216:596 610, 2016.
HaiYing Wang. Logistic regression for massive data with rare events. In International Conference Machine Learning, pages 9829-9836. PMLR, 2020.
Xiaoyan Wang, Ran Li, Bowei Yan, and Oluwasanmi Koyejo. Consistent classification with general- ized metrics. arXiv preprint
2019a.
Xin Wang, Hao Helen Zhang, and Yichao Wu. Multiclass probability estimation with support vector machines. Journal of Compulational and Gruphical Statistics, pages 1-18, 2019b.
Jimmy Wu, Yatong Chen, and Yang Liu. Metric-fair classifier derandomization. In International Conference Machine Learning, pages 24096. PMLR, 2022.
Bowei Yan, Sanmi Koyejo, Kai Zhong, and Pradeep Ravikumar. Binary classification with karmic, prreshold-qaas-conean metrics. In International Conference on Machine Learning, pages 5531- 5540. PMLR, 2018.
Ming-Jic Jic Zhao, Narayanan Edakunni, Adam Pocock, and Gavin Brown. Beyond Fano's incquality: Bounds on the optimal F-score, BER, and cost-sensitive risk and their implications. The Journal of Machine Learning Research, 14(1):1033-109) 2013.
Yujin Zhu, Zhe Wang, and Daqi Gao. Gravitational fixed radius nearest neighbor for imbalanced problem. Knowledge- Systems, 90:224-238, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(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 all theoretical results? [Yes] See Appendices C]
3. If you experiments...
14

---

(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code and instructions for reproducing the experimental results are included in the supplemental material.
(b) Did you 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 experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix E
4. 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? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'ne 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "DkFreeDmuFH", "reviewer": "Reviewer_c1ro", "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. ", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nYet, 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:\n\n* Peter A. Flach:\nClassifier Calibration. Encyclopedia of Machine Learning and Data Mining 2017: 210-217\n* José Hernández-Orallo, Peter A. Flach, César Ferri:\nROC curves in cost space. Mach. Learn. 93(1): 71-91 (2013)\n* Peter A. Flach:\nThe Geometry of ROC Space: Understanding Machine Learning Metrics through ROC Isometrics. ICML 2003: 194-201\n\nIn the reviewer-discussion of the paper, the following has also popped up:\nOptimal Thresholding of Classifiers to Maximize F1 Measure\nhttps://link.springer.com/content/pdf/10.1007/978-3-662-44851-9_15.pdf\n\n(BTW: In case you are wondering: none of the above is a self citation... :-))\n\nThe 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). \n\nNow, 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.\n\nIn 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. \n\nThe 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.\n\nA 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.", "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": "CG4fjOAhEW-", "reviewer": "Reviewer_rWrH", "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.\nThey prove bounds on differences of confusion matrices for differently parameterized generalized Bayes classifiers.", "questions": "Lemma 19: Moreover, since the actual proportions of positives and negatives are fixed - why does that hold?\n 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", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength: if they results hold, it would be of  theoretical interest.\nweakness: there are lots of small notational issues in the paper.\n\nThe paper can be correct or wrong. it is hard to judge due to the brevity of the proofs.\nThe reviewer believes that many proofs needs to be extended to be readable.\n\neq(1) is superfluous: 1{\\eta^*(x)>0.5} is either 0 or 1. Thus putting a Bernoulli in front of it makes no sense.\n\nThe paper makes a mistake in equation (3):\nConfusion matrices contain joint probabilities\nP( Y, \\hat{Y} ), as also stated in line 141:\nC_{1,1} + C_{1,2} + C_{2,1} + C_{2,2} =1\nThe true positive **rate**, however, is a conditional probability, conditioned on groundtruth being positive:\nP(\\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)] }\n\nthe empirical true positive rate is given as\n\n\\frac{\\sum_i Y_i \\hat{Y}(X_i) }  {\\sum_i Y_i}\n\nnot as (wrongly) stated in eq(3).\n\nTheir TN, TP terms inside the C matrices are joint probabilities:\n\nTN + FP = P(Y=0)\nFN + TP = P(Y=1)\n\n\nTN + TP = P(Y=1,\\hat{Y}=1) + P(Y=0,\\hat{Y}=0)\n\nACC = P( Y= \\hat{Y}  )\n\nTheorem 3 is  wrong, but there might be a typo and they might mean stochastic classifiers.\n \ntake \\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}$.\n\nTheorem 3 in  the appendix states it for a stochastic classifier, not for any classifier.\n\nLemma 18 in the supplement / line 579:\n\nThe 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.\n\nThe proof of Lemma 18 contains a problem:\nE_{Z \\sim P_X} [ \\hat{Y}(Z) | \\eta(Z)=\\eta(x) ] is a conditioned expectation, conditioned on the set\nP( \\{ z: \\eta(z) = \\eta(x)\\}) - this probability can be 0, then this conditional expectation can become undefined.\n\nLemma 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.\n\nline 589 in the supplement is wrong: it does not hold for any classifier, but for a stochastic classifier.\n\n\n\nLemma 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", "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": "9JCrORzpDGS", "reviewer": "Reviewer_p1uP", "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.\n\nThe contributions of the paper are as follows:\n1. A novel characterization of classifiers optimizing general performance metrics that are functions of a classifier's confusion matrix is derived.\n2. The authors show that in general, a Bayes classifier always exists if one considers stochastic classifiers, but not if one considers only deterministic classifiers.\n3. Performance guarantees are derived under more general performance measures in terms of the error of estimating the class probability function under uniform loss.\n4. Analysis of k-nearest neighbor classification under uniform loss is provided.", "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.\n\n2. 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.\n\n3. 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.\n\n4. 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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Generalization of the Bayes optimal classifier to any performance metric computed from the confusion matrix.\n+ Regret bounds in terms of the error of estimating the class probability function under uniform loss.\n+ Definition and analysis of specific type of class imbalance.\n+ Analysis and insights on the performance of k-nearest neighbor classification under uniform loss.\n\nWeaknesses:\n- Numerical experiments are provided only for synthetically generated datasets and not real-world imbalanced datasets.\n- The motivation behind the proposed uniform class imbalance and the study of the k-nearest neighbor classifier is unclear.\n- The abstract implies that classifier behavior is studied in the context of different types of class imbalance, which is not true.\n- The definition of uniform class imbalance is unclear.", "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": "2uJMFU4vVHs", "reviewer": "Reviewer_jgDJ", "summary": "Motivated by imbalanced classification problems, the paper generalizes the analysis of Bayes-optimal classifier to any performance metric supported in the confusion matrix. \nIn a second part, the paper analysis the specific case of the k-NN classifier under a specific setting (uniform loss) of the previous generalization.\n", "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\nCMM 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.\"\n\nFor the special case of  the classical Bayes classifier, is this a good strategy? Is this SOTA?", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+good theoretical analysis\n+good theoretical insights\n+well-written paper and technically sound\n\nWeaknesses\n-not explored enough how the theoretical knowledge can impact the design of models in practice.\n\n\n\n\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