Statistical Theory for Imbalanced Binary Classification

Within the vast body of statistical theory developed for binary classification, few meaningful results exist for imbalanced classification, in which data are dominated by samples from one of the two classes. Existing theory faces at least two main challenges. First, meaningful results must consider more complex performance measures than classification accuracy. To address this, we characterize a novel generalization of the Bayes-optimal classifier to any performance metric computed from the confusion matrix, and we use this to show how relative performance guarantees can be obtained in terms of the error of estimating the class probability function under uniform (L∞) loss. Second we show that optimal classification performance depends on properties of class imbalance that have not previously been formalized. Specifically, we propose a novel sub-type of class imbalance, which we call Uniform Class Imbalance. We analyze how Uniform Class Imbalance influences optimal classifier performance and show that it necessitates different classifier behavior than other types of class imbalance. We illustrate these two contributions in the case of k-nearest neighbor classification, for which we develop novel guarantees.


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;Krawczyk, 2016;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 et al., 2002), or reformulating classification algorithms to optimize different performance metrics (Dembczynski 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 (2013) and Fernández et al. (2018).
Despite the pervasive challenge of class imbalance, our theoretical understanding of class imbalance is limited. The vast majority of theoretical performance guarantees for classification characterize classification accuracy or, equivalently, misclassification risk (Mohri et al., 2018), which is typically an uninformative measure of performance for imbalanced classes. Under measures that are used with imbalanced classes in practice, such as precision, recall, F β scores, and classweighted scores (Van Rijsbergen, 1974, 1979, existing theoretical guarantees are limited to statistical consistency, in that the algorithm under consideration asymptotically optimizes the metric of choice (Koyejo et al., 2014;Menon et al., 2013;Narasimhan et al., 2014); specifically, there is no finite-sample theory that would allow comparison of an algorithm'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 should influence the behavior of a classifier.
This paper provides two main contributions. First, in Section 4, we provide a novel characterization of classifiers optimizing general performance metrics that are arXiv:2107.01777v2 [math.ST] 6 Oct 2021 functions of a classifier's confusion matrix. This characterization generalizes a classical result, that the Bayes classifier optimizes classification accuracy, to a much larger class of performance measures, including those commonly used in imbalanced classification. Interestingly, we show that, in general, a Bayes classifier always exists if one considers stochastic classifiers, but not if one considers only deterministic classifiers. While this result may be of independent interest, we use it here to show how to provide relative performance guarantees under these more general performance measures. In particular, we show that performance guarantees can be derived in terms of the error of estimating the class probability function under uniform (L ∞ ) 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 kNN 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 the development of classifiers that perform well on specific imbalanced classification problems of practical importance.
Collectively, these contributions provide finite-sample performance guarantees for nonparametric binary classification under performance metrics that are appropriate for imbalanced data and show how 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.

Theoretical Guarantees for Imbalanced Binary Classification
To the best of our knowledge, there are no existing statistical guarantees in terms of the functions of the confusion matrix in the generality that we propose. Extensive statistical learning theory for classification in terms of accuracy can be found in Mohri et al. (2018). However, in the presence of severe class imbalance, accuracy ceases to be an informative measure of performance (Cortes and Mohri, 2004). A straightforward alternative is cost-weighting. This is intuitive in applications where costs can be explicitly assigned, and statistically, weighting is equivalent to threshold selec-tion in the case of binary classification. Interestingly, cost-weighting has been studied under the motivation of addressing class imbalance before (Scott, 2012), but in the context of calibrated losses, i.e., the guarantee that minimizing a surrogate loss for zero-one loss leads to a Bayes-optimal estimator in the classical sense (see Eq. (1); Liu (2007); Tewari and Bartlett (2007)).
In addition to class-weighting, other methods commonly used for imbalanced binary classification include resampling, margin adjustment, and Neyman-Pearson classification. Various forms of resampling appear most common in practice (He and Ma, 2013). Undersampling the dominant class is straightforward and provides computational benefits, often with little loss in statistical performance (Fithian and Hastie, 2014), while interest in oversampling rare classes, sometimes referred to as data augmentation, has grown with the advent of sophisticated generative models (such as generative adversarial networks (GANs)) 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. Margin-adjustment involves adjusting the margins of support vector machines (SVMs) to appropriately handle class-weighting (Lin et al., 2002), and Scott (2012) allows for class-based modifications to the margin as well. More recent work adjusts the margins for deep neural network classifiers (Cao et al., 2019).
A family of techniques related to our work comes from the perspective of Neyman-Pearson classification, which attempts to minimize misclassification error on one class subject to a constraint on the maximum misclassification error on a second class, following the structure of statistical hypothesis testing. Our first main result (Theorem 3) implicitly involves re-framing optimization of general classification performance measures in the Neyman-Pearson framework, and some of our results for classification have analogues in the classical hypothesis testing literature (Lehmann and Romano, 2006). Unlike other methods, substantial theoretical guarantees do exist for Neyman-Pearson classification (Rigollet and Tong, 2011;Tong, 2013;Tong et al., 2016), but these results focus on performance within the Neyman-Pearson framework, rather than in terms of general classification performance measures.
Finally, the most similar existing results to our Theorem 3 are due to Yan et al. (2018) and Wang et al.
(2019a); we discuss these in detail in Section 4.

kNN Classification and Regression
The kNN classifier, first published by Fix and Hodges (1951), is one of the oldest and most well-studied non-parametric classifiers. Early theoretical results include those of Cover and Hart (1967), who showed that the misclassification risk of the kNN classifier with k = 1 is at most twice that of the Bayes-optimal classifier, and Stone (1977), who showed that the kNN classifier is Bayes-consistent if k → ∞ and k/n → 0. An extensive literature on the accuracy/misclassification risk of kNN classification has since developed (Devroye et al., 1996;Györfi et al., 2002;Samworth, 2012;Chaudhuri and Dasgupta, 2014;Biau and Devroye, 2015;Gadat et al., 2016;Döring et al., 2018;Cannings et al., 2019).
Rather than accuracy bounds for kNN classification, the bounds on uniform error we present in Section 5 are most closely related to risk bounds for kNN regression, of which the results of Biau et al. (2010)  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, 2011;López et al., 2014;Vluymans et al., 2016), and gravitational methods (Cano et al., 2013;Zhu et al., 2015). To our knowledge, no statistical guarantees exist for such methods.

SETUP AND NOTATION
Let (X , ρ) be a separable metric space, and let Y = {0, 1} denote the set of classes. For any x ∈ X and > 0, B(x, ) := {y ∈ X : ρ(x, y) < } denotes the open radius-ball around x. Consider n independent samples (X 1 , Y 1 ), . . . , (X n , Y n ) drawn from a distribution P X,Y on X × Y with marginals P X and P Y .
To optimize general performance metrics, we must consider stochastic classifiers. Formally, letting B := {Y ∼ Bernoulli(p) : p ∈ [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 ∈ X , E[ Y (x)] is the probability that the classifier assigns x to class 1. We use SC to denote the class of stochastic classifiers.
The true regression function η * : X → [0, 1] is defined that is, given an instance X i , the label Y i has a Bernoulli distribution with mean η(X i ). As we show in the next section, an optimal classifier can always be written in terms of the true regression function η, motivating estimates η : X → [0, 1] of η. Such estimates η are called "regressors".

OPTIMAL CLASSIFICATION BEYOND ACCURACY
A famous result states that classification accuracy is maximized by the "Bayes" classifier This is of limited practical value when η * is unknown, but it is a cornerstone of the statistical theory of binary classification because it provides an optimal performance benchmark against which a classifier can be evaluated in terms of accuracy (Devroye et al., 1996;Mitchell, 1997;James et al., 2013). As discussed previously, accuracy can be a 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 a broad class of classification performance measures, including those commonly used in imbalanced classification. First, we specify performance measures for which our results apply.

Confusion Matrix Measures (CMMs)
Nearly all measures of classification performance, including accuracy, precision, recall, F β scores, and others, can be computed from the confusion matrix, which counts the number of test samples in each (true class, estimated class) pair. Formally, let C := {C ∈ [0, 1] 2×2 : C 1,1 + C 1,2 + C 2,1 + C 2,2 = 1} denote the set of all possible binary confusion matrices. Given a classifier Y , the confusion matrix C Y ∈ C and empirical confusion matrix C Y ∈ C are given by wherein the true positive rate TP Y and the empirical true positive rate TP Y are given by and the true and empirical false positive (FP Y and FP Y ), false negative (FN Y and FN Y ), and true positive (TP Y and TP Y ) rates are defined similarly. Note that the expectation in Eq. (3) is over both stochasticity in the data and stochasticity in the classifier.
Intuitively, any measure of a classifier's performance should improve as 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 function M : C → R is called a confusion matrix measure (CMM) if, for any confusion matrix Essentially, correcting an incorrect classification should not reduce a CMM. This condition is satisfied by most performance measures used in practice, including weighted accuracy, precision, recall, F β scores, and MCC. On the other hand, the area under the receiver operating characteristic (AUROC) and area under the precision-recall (AUPR) are not CMMs because they are computed by averaging across confusion matrices from different classification thresholds. Our main result generalizes the Bayes classifier (1) to arbitrary CMMs.

Generalizing the Bayes Classifier
The Bayes classifier given thresholds the regression function deterministically at the value 0.5. The following generalizes this to a stochastic threshold: Definition 2 (Regression-Thresholding Classifier). A classifier Y : X → B is called a regression-thresholding classifier if, for some p, t ∈ [0, 1] and η : X → [0, 1], for all x ∈ X . In the sequel, we will denote such classifiers Y p,t,η , and refer to the pair (p, t) as the threshold.
Now we can state the main result of this section: Theorem 3 states that, if a CMM M is maximized by any stochastic classifier, then M can be maximized by a regression-thresholding classifier. As a special case, the classical Bayes classifier corresponds to M (C) = TN + TP, p = 0, and t = 0.5. However, as discussed in the next paragraph, without stronger assumptions, Theorem 3 does not hold for deterministic classifiers. Since classifiers of the form (4) generalize both the regression-thresholding structure and optimality properties of the Bayes classifier, we refer to them as generalized Bayes classifiers. The existence of any maximizer Y of M (C Y ) depends on specific properties, such as (semi)continuity or convexity of M ; we do not investigate existence here and focus on characterizing a maximizer when it exists. Maximizers Y of M (C Y ) are typically not unique, since changing Y on sets of P X -measure 0 does not change C Y ; however, among maximizers, generalized Bayes classifiers are an important, well-behaved subclass.
To the best of our knowledge, no previous results provide such a precise and general characterization of an optimal classifier. The most similar results of which we are aware are those of Yan et al.  ) shows that, under a "karmic" assumption stronger than our monotonicity assumption in Definition 1, if the random variable η(X) is absolutely continuous (i.e., has a density with respect to Lebesgue measure on [0, 1]), then an optimal classifier can be obtained by deterministically thresholding the regression function η. Our Theorem 3 is strictly more general, since if η(X) is absolutely continuous, then one can set p = 0 without changing C Yp,t,η . More recently, Wang et al. (2019a) showed in their Corollary 2, under absolute continuity of η(X) and a monotonicity assumption comparable to our Definition 1, that the optimal classifier can always be written as a mixture of two deterministic classifiers. Although Wang et al. (2019a) consider more general multiclass and multilabel settings, in the binary setting, our result is more precise, since our regressionthresholding classifiers are deterministic except for a single value of η. We leave it to future work to develop a similarly precise generalization of this result to multiclass and multilabel settings. Interestingly, Wang et al. (2019a) claim that regularity assumptions on η(X) such as absolute continuity "seem to be unavoidable", and our Theorem 3 appears to be the first result to omit such assumptions, Specifically, we show that this comes at the cost of the optimal classifier possibly being non-deterministic for a single atom of η(X). Finally, there exist a number of relevant results that are specific to certain CMMs, such as Lemma 12 of Zhao et al. (2013), which provides a similar characterization of the deterministic classifier that maximizes F 1 score.
We prove Theorem 3 in Appendix A using a series of variational arguments. Roughly speaking, given a classifier Y , we construct a perturbation Y of Y such that either M (C Y ) < M (C Y ) or Y is of the form (4) and M (C Y ) ≤ M (C Y ). Since, the classifier Y might be quite poorly behaved (e.g., its behavior on sets of P Xmeasure 0 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 a series of constructions of increasingly well-behaved classifiers.
Theorem 3 shows that the generalized Bayes classifier can be written in terms of the regression function η and at most 2 scalar parameters p and t depending on the distribution of η(X) and the CMM M . The next example shows that this characterization cannot be simplified without additional assumptions: is uniquely maximized by p = θ θ+1 ∈ (0, 1) and t = η(0) ∈ (0, 1). This shows that both generalized threshold parameters p and t in Eq. (4) are necessary in the absence of further assumptions on M or η. This example also illustrates the need for stochasticity to optimize general CMMs. Specifically, for any determin-

Relative Performance Guarantees in terms of the Generalized Bayes Classifier
Theorem 3 motivates a two-step approach to imbalanced classification in which one first estimates the regression function η and then selects a generalized threshold (p, t) that optimizes empirical performance M ( C Y ). Such an approach has a number of practical advantages; for example, one can address covariate shift or retune a classifier trained under one CMM to perform well under another CMM, by simply reselecting the two scalar parameters p and t. This may be 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 a classifier decomposes into errors in selecting (p, t) and errors in estimating η, facilitating the derivation of performance guarantees relative to the generalized Bayes classifier (4). All results in this section are proven in Appendix B.
Our first lemma bounds the performance difference of thresholding two regressors in terms of their L ∞ distance. This allows us to bound the error of using a regressor η instead of the true regression function η. Lemma 5. Let p, t ∈ [0, 1] and η, η : X → [0, 1]. Then, Intuitively, Lemma 5 bounds the largest difference in the confusion matrices of Y p,t,η and Y p,t,η by the probability that the threshold t lies between η and η .
Our next lemma bounds the worst-case error over thresholds (p, t) ∈ [0, 1] of the empirical confusion matrix. This allows us to bound error due to using an empirical threshold ( p, t) instead of the threshold (p * , t * ) that is optimal for the true regression function.
Lemma 6. Let η : X → [0, 1] be any regression function. Then, with probability at least 1 − δ, Lemma 6 follows from Vapnik-Chervonenkis (VC) bounds on the complexity of the set { Y p,t,η : p, t ∈ [0, 1]} of possible regression-thresholding classifiers with fixed regression function η. In fact, Appendix B proves a 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 log(n/δ)/n. As we formalize later, this 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 instability of commonly used CMMs. Because Theorem 3 shows that any CMM can be optimized by a regressionthresholding classifier, we state here only the specific result for regression-thresholding classifiers.
Before combining Lemmas 5 and 6 to give the main result of this section, we note a margin assumption, which characterizes separation between the two classes: Definition 7 (Tsybakov Margin Condition). Let C, β ≥ 0, t ∈ (0, 1). A classification problem with covariate distribution P X and regression function η satisfies a (C, β)-margin condition around t if, for any > 0, The Tsybakov margin condition, introduced by Mammen and Tsybakov (1999) in the case t = 0.5, is widely used to establish convergence rates for classification in terms of accuracy (Audibert and Tsybakov, 2007;Arlot et al., 2011;Chaudhuri and Dasgupta, 2014).
Together with the margin condition and a Lipschitz condition on the CMM M , Lemmas 5 and 6 give the following bound on sub-optimality of a regressionthresholding classifier if the threshold is selected by maximizing M over the empirical confusion matrix: Corollary 8. Let η : X → [0, 1] be the true regression function, and let η : X → [0, 1] be any regressor. Let denote the empirical and true optimal thresholds, respectively. Suppose M is Lipschitz continuous with constant L M with respect to the uniform (L ∞ ) metric on C. Finally, suppose P X and η satisfy a (C, β)-margin condition around t * . Then, with probability ≥ 1 − δ, Appendix B.1 computes L M for a few CMMs.

UNIFORM ERROR OF THE kNN REGRESSOR
Above, we bounded relative performance in terms of uniform (L ∞ ) 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 a parameter r, introduced in Section 5.2, 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, of class imbalance in a given dataset.

k-Nearest Neighbor Regressor
Given a point x ∈ X , order the training data X σ1(x) , . . . , X σn(x) such that i.e., X σi(x) is the i th -nearest neighbor of x among X 1 , ..., X n . For an integer k > 0, the kNN regressor η k : X → [0, 1], is defined as the proportion of x's k-nearest neighbors in class 1:

Uniform Class Imbalance
We formalize a novel sub-type of class imbalance called Uniform Class Imbalance. First, note that any regression function η can be written as η = rζ, where r ∈ (0, 1] and ζ : X → [0, 1] is a regression function with sup x∈X ζ(x) = 1. In Uniform Class Imbalance, r ≈ 0; thus, the class Y = 1 is rare regardless of X.
Uniform Class Imbalance occurs in "difficult" classification problems where the covariate X provides only partial information about the class Y . 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, for which η(X) is relatively high, for follow-up investigation. Uniform Class Imbalance can be distinguished from "easier" problems in which, for some x ∈ X , η(X) ≈ 1 and so, given enough training data, a classifier can confidently assign the label Y = 1. These include well-separated classes or deterministic problems (e.g., protein structure prediction; Noé et al. (2020)).
To our knowledge, such notions of class imbalance have not previously been distinguished. In the particular case that the data are drawn from a logistic model, Uniform Class Imbalance reduces to the notion of class imbalance described in Wang (2020); however, Uniform Class Imbalance applies in more general contexts.

Upper Bounds
Here, we present bounds (proven in Appendix C.1) on uniform error η − η ∞ = sup x∈X |η(x) − η(x)| of the kNN regressor η k . First, recall two standard quantities, covering numbers and shattering coefficients: Definition 9 (Covering Number). Suppose (X , ρ) is a totally bounded metric space. Then, for any > 0, the -covering number N ( ) of (X , ρ) is the smallest integer such that there exist N ( ) points x 1 , ..., . Definition 10 (Shattering Coefficient). For integers n > 0, the shattering coefficient of balls in (X , ρ) is We now state two assumptions data distribution P X,Y : Assumption 11 (Dense Covariates Assumption). The marginal distribution P X of covariates is lower bounded in the sense that, for some constants p * , * , d > 0, for any x ∈ X and ∈ (0, * ], we have P X (B (x)) ≥ p * d .
Assumption 11 ensures that each query point's nearest neighbors are sufficiently near to be informative. We also assume that the regression function ζ is smooth: We now state our upper bound on uniform error: Theorem 13. Under Assumptions 11 and 12, whenever k/n ≤ p * ( * ) d /2, for any δ > 0, with probability at least If r ∈ O ((log S(n)/n), this bound is minimized by k n, giving η − η ∞ ∈ O P ((log S(n))/n). Otherwise, under a mild simplifying assumption that N ( ) increases at most polynomially with 1/ , this bound is . (7) Of the three terms in (6), the first term, of order r(k/n) α/d , comes from smoothing bias of the kNN classifier. The second and third terms are due to label noise, with the second term dominating under extreme class imbalance r ∈ O (log S(n)/n) and the third term dominating otherwise. Theorem 6 shows that the optimal choice of the tuning parameter k is much larger under Uniform Class Imbalance than in the case of balanced classes; indeed, setting k n 2α 2α+d (log S(n)) d 2α+d , which is optimal in the balanced case, gives a rate that slower by a factor of r −d/(4α+d) .
The following example demonstrates how to apply Theorem 13 in a concrete setting of interest: Corollary 14 (Euclidean, Absolutely Continuous Case). Suppose (X , ρ) = ([0, 1] d , · 2 ) is the unit cube in R d , equipped with the Euclidean metric, and P X has a density that is lower bounded away from 0 on X . Then, N ( ) ≤ (2/ ) d and S(n) ≤ 2n d+1 + 2, and so, .
The most problematic term in this bound is the exponential dependence on the dimension d of the covariates. Fortunately, since Theorem 13 utilizes covering numbers, it improves if the covariates exhibit structure, such as that of a low-dimensional manifold. This is illustrated in further detail in Appendix C.1.
We close with a lower bound, proven in Appendix C.2, on the uniform error, showing that the rate in Theorem 13 is minimax optimal over (α, L)-Hölder regression functions, up to a polylogarithmic factor in r: Theorem 15. Suppose X = [0, 1] d is the d-dimensional unit cube and X is uniformly distributed on X . Let Σ α (L) denote the family of (α, L)-Hölder continuous regression function. Then, for any α, L > 0, there exist constants n 0 and c > 0 (depending only on α, L, and d) such that, for all n ≥ n 0 and any estimator η,

Discussion
The upper bounds on η − η ∞ given in this section can be plugged directly into Corollary 8 to provide error bound under arbitrary CMMs, in terms of the sample size n, hyperparameter k, degree r of Uniform Class Imbalance, and complexity parameters (margin β, smoothness α, intrinsic dimension d, etc.) of X and P X,Y . Thus, these results collectively give some of the first finite-sample guarantees under general performance metrics used for imbalanced classification.
Our analysis shows that, under severe Uniform Class Imbalance, the optimal choice of the hyperparameter k is much larger than in balanced classification. Importantly, as we illustrate with an example in the next section, this larger k leads to sub-optimal, or even inconsistent, estimates of the regression function under other (nonuniform) forms of class imbalance.

NUMERICAL EXPERIMENTS
We provide two numerical experiments to illustrate our results from Sections 4 and 5. We repeated each experiment 100 times and present average results with 95% confidence intervals computed according to the central limit theorem. Python implementations can be found at https://gitlab.tuebingen.mpg.de/shashank/ imbalanced-binary-classification-experiments.

Experiment 1
Suppose X = [0, 1], X has a discrete uniform distribution over three points {0, 0.5, 1}, and, for all x ∈ X , η(x) = x. Consider the CMM M (C) = TP · TN. Similar to the analysis in Example 4, one can check that the optimal value of M (C) = (5/12) 2 = 25 144 is achievable only by a stochastic classifier, whereas as deterministic classifiers can achieve at most M (C) = 1/6 < 25 144 . For 10 logarithmically spaced values of n between 10 2 and 10 4 , we drew n independent samples of (X, Y ) according the above distribution. Using this training data, we selected optimal deterministic and stochastic thresholds t ∈ [0, 1] and (t, p) ∈ [0, 1] 2 for the kNN classifier by maximizing M ( C) over 100 uniformly spaced values in [0, 1] and 10, 000 uniformly spaced values in [0, 1] 2 , respectively. Since, in this example, α = d = 1, we set k = n 2/3 as suggested by Theorem 14. As another point of comparison, we also include a very different deterministic classifier, a random forest, trained using the 10 3 10 4 Sample Size ( default parameters of Python's scikit-learn package. We estimated M (C) for each classifier using 1000 more independently generated "test" samples of (X, Y ). Figure 1 presents regret, i.e., sub-optimality of each classifier relative to the optimal classifier, in terms of M (C). Consistent with our analysis, as n increases, regrets of the deterministic classifiers are bounded away from 0, while regret of the stochastic classifier vanishes.
For 10 logarithmically spaced values of n between 10 2 and 10 4 , we drew n independent samples of (X, Y ) according the joint distributions corresponding to each of η 1 and η 2 , as described above. Since, in this example, α = d = 1, to ensure r ∈ o n −d/(2α+2d) , we set r = n −1/2 . As indicated by Theorem 14, we set k = n 2/3 r −1/3 . We then computed L ∞ and L 1 distances between the kNN regressor (Eq. (5)) and true regression function. We also drew 1000 independent test samples of (X, Y ) and used these to estimate the F 1 score of thresholding the kNN regressor at a threshold t determined by optimizing the empirical F 1 score (over  Figure 2: Uniform (L ∞ ) and average (L 1 ) errors of kNN regressor, as well as F 1 regret (i.e., F 1 score of Bayes optimal classifier minus that of optimally thresholded kNN regressor) of estimating regression functions η 1 and η 2 . Error bars indicate 95% confidence intervals. the training data) over 100 uniformly-spaced values of t ∈ [0, 1]. Figure 2 shows the uniform (L ∞ ) error, the average (L 1 ) error, and the F 1 regret, i.e., the suboptimality of the F 1 score of the kNN classifier under optimal thresholding relative to that of the generalized Bayes classifier, which we bounded in Corollary 8. Consistent with our analysis above, the uniform (L ∞ ) error decays to 0 under η 1 but not under η 2 . Meanwhile, the average error (L 1 ) decays to 0 under both η 1 and η 2 . Consistent with Corollary 8, the F 1 regret of the thresholded classifier, which decays to 0 under η 1 but not under η 2 , mirrors performance of the regressor in uniform (L ∞ ) error rather than average (L 1 ) error.

CONCLUSIONS
The main conclusions of this paper are as follows. First, without assumptions on the IID data generating distribution, the Bayes-optimal classifier can be generalized from accuracy to other measures of classification performance using a stochastic thresholding procedure with two additional scalar parameters. However, in general, deterministic classifiers may not be able to achieve Bayes-optimality. This generalized Bayes classifier provides an optimal performance benchmark relative to which one can analyze many classifiers in terms of their ability to estimate the regression function in uniform loss. This includes the kNN classifier, for which we provided new guarantees, including minimax-optimally under uniform loss in the presence of Uniform Class Imbalance. We also showed that the parameter k 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 these sub-types can be distinguished in practice, (b) develop adaptive classifiers that perform well under multiple distinct sub-types of imbalance, and (c) extend these findings to the multiclass case, in which class imbalance emerges naturally when the number of classes is large.

A Derivation of the Generalized Bayes Classifier
In this Appendix, we prove Theorem 3, in which we characterize a stochastic generalization of the Bayes classifier to arbitrary CMMs. We reiterate the theorem for the reader here: Theorem 3. If argmax Y ∈SC M (C Y ) = ∅, then there exists a regression-thresholding classifier As described in the main paper, unlike prior results (Koyejo et al., 2014;Yan et al., 2018;Wang et al., 2019b), we do not assume that the distribution of η(X) is absolutely continuous. This makes proving Theorem considerably more complicated than these previous results. We prove Theorem 3 in a sequence of steps, constructing optimal classifiers in forms progressively closer to that of the generalized Bayes classifier described in Theorem 3. Specifically, we first show, in Lemma 16, that there exists an optimal classifier that is a (stochastic) function of the regression function η. We then construct an optimal classifier in which this function of η is non-decreasing. Finally, we construct an optimal classifier in which this function of η is a threshold function, as in Theorem 3.
Lemma 16. For any stochastic classifier Y : X → P({0, 1}), there is a stochastic classifier Y : and note that Y has the desired form. Note that both Y (X) and Y (X) are conditionally independent of the true label Y given η(X). Thus, and, similarly, Additionally, by construction of Y , Putting these together, we have Similarly, one can check that C Y = C Y .
It follows from Lemma 16 that, if M (C Y ) is maximized by any classifier, then it is maximized by a classifier Y of the form in Eq. (8). It remains to show that f in Eq. (8) can be of the form z → p1{z = t} + 1{z > t} for some threshold (p, t) ∈ [0, 1] 2 . Before proving this, we give a simplifying lemma showing that the problem of maximizing a CMM can be equivalently framed as a particular functional optimization problem. This will allow us to to significantly simplify the notation in the subsequent proofs.
Then, the classifier Y (x) ∼ Bernoulli(f (η(x))), Proof. This result follows from the definition (Definition 1) of a CMM. Specifically, by construction of Y , Moreover, since, since the actual proportions of positives and negatives are fixed (i.e., Lemma 17 essentially shows that maximizing any CMM M is equivalent to performing Neyman-Pearson classification, at a some particular false positive level α depending on M (through f * ) and on the distribution of η(X). For our purposes, this simplifies the remaining steps in proving Theorem 3 by allowing us to ignore the details of the particular CMM M and regression function η and focus on characterizing solutions to an optimization problem of the form (9) (see, specifically, (10) below).
Proof. We prove the contrapositive. Suppose that, for every z ∈ We are now ready for the main remaining step in the proof of Theorem 3, namely characterizing solutions of (a generalization of) the optimization problem (9) has a solution. Then, there is a solution to (10) that is a generalized threshold function.
Proof. Suppose that there exists a solution f to (10). We will construct a generalized threshold function that solves (10) in two main steps. First, we will construct a monotone solution to (10). Second, we will show that this monotone solution is equal to a generalized threshold function except perhaps on a set of probability 0 with respect to Z. This generalized threshold function is therefore a solution to (10). (10) where the essential supremum and infimum are taken with respect to the measure P Z of Z, with the conventions g(z) = 0 whenever P Z ([0, z]) = 0 and h(z) = 1 whenever P Z ((z, 1]) = 0. We first show that, for all z ∈ [0, 1], g(z) ≤ h(z). We will then use this to show that g = f except on a set of P Z measure 0 (i.e., P Z ({z ∈ [0, 1] :

Construction of Monotone Solution to
is clearly monotone non-decreasing, the result follows.
Suppose, for sake of contradiction, that, for some z ∈ noting that, by construction of , φ(z) ∈ [0, 1] for all z ∈ [0, 1]. Then, by construction of φ, since the function z → z 1−z is strictly increasing. This contradicts the assumption that f optimizes (10), implying g ≤ h.
On the other hand, suppose, for sake of contradiction, that P Z (B δ ) > 0. Applying Lemma 18 to the measure E → P Z (B δ ∩ E), there exists z ∈ R such that, for any > 0, P Z (B δ ∩ (z − , z)) > 0. Since g is continuous at z, there exists > 0 such that g(z − ) ≥ g(z) − δ. At the same time, since g is non-decreasing, for t ∈ B δ ∩ (z − , z), contradicting the previously shown fact that g ≤ h.

Construction of a Generalized Threshold Solution:
We now construct a solution to (10) that is equal to a generalized threshold function (i.e., a function that has the form p1{z = t} + 1{z > t}) except on a set of P Z -measure 0. To show this, it suffices to construct a function f : [0, 1] → [0, 1] such that (a) f is monotone non-decreasing and (b) the set f −1 ((0, 1)) is the union of the singleton {t} and a set of P Z -measure 0.
From the previous step of this proof, we may assume that we have a solution f to (10) that is monotone non-decreasing. It suffices therefore to show that A := f −1 ((0, 1)) is the union of a singleton and a set of P Z -measure 0. Define Then, for all > 0, by countable subadditivity, P Z (A\{t 0 }) = 0, which implies that A = {t 0 } ∪ (A\{t 0 }) is the union of a singleton and a set of measure 0.
Combining Lemma 19 with Lemma 17 completes the proof of our main result, Theorem 3.

B Relative Performance Guarantees in terms of the Generalized Bayes Classifier
In this Appendix, we prove Lemmas 5 and 6, as well as their consequence, Corollary 8. Also, in Section B.1, we demonstrate, in a few key examples, how to compute the Lipschitz constant used in Corollary 8.
We begin with the proof of Lemma 5, which, at a given threshold (p, t), bounds the difference between the confusion matrices of the true regression function η and an estimate η of η. We restate the result for the reader's convenience: Lemma 5. Let p, t ∈ [0, 1] and let η, η : X → [0, 1]. Then, Proof. For the true negative rate, we have This type of inequality is standard and follows from the fact that, if t lies between η and η , then the difference of η and t is necessarily less than η and η . Repeating this calculation for the true positive, false positive, and false negative rates gives (11).
Note that, in the presence of degree r Uniform Class Imbalance (see Section 5.2), one can obtain a tighter error bound r P [|η(X) − t| ≤ η − η ∞ ] for the true positive and false negative rates because, for all x ∈ X , P[Y = 1|X = x] ≤ r. However, the weaker bound (11) simplifies the exposition.
We now turn to proving Lemma 6, which we use to bound the maximum difference between the empirical and true confusion matrices of a regression-thresholding classifier over thresholds (p, t). Specifically, we will use this result to bound the difference in confusion matrices between the optimal threshold (p * , t * ) and the threshold ( p, t) selected by maximizing the empirical CMM. We actually prove a more general version of Lemma 6, for arbitrary classifiers, based on the following definition: Definition 20 (Stochastic Growth Function). Let F be a family of is the maximum number of distinct classifications of n points x 1 , ..., x n by a stochastic classifier Y with (x → E[ Y (x)]) ∈ F and randomness given by z 1 , ..., z n .
Definition 20 generalizes the growth function (Mohri et al., 2018), a classical measure of the complexity of a hypothesis class originally due to Vapnik and Chervonenkis (2015), to non-deterministic classifiers. Importantly for our purposes, one can easily bound the stochastic growth function of regression-thresholding classifiers: Example 21 (Stochastic Growth Function of Regression-Thresholding Classifiers). Suppose so that { Y f,η : f ∈ F} is the class of regression-thresholding classifiers. Any set of points (x 1 , z 1 ), ..., (x n , z n ), can be sorted in increasing order by η(x)'s, breaking ties in decreasing order by z's. Having sorted the points in this way, {f (x) > z} = 0 for the first j points and {f (x) > z} = 1 for the remaining n − j points, for some j ∈ [n] ∪ {0}. Thus, Π F (n) = n + 1.
We will now prove the following result, from which, together with Example 21, Lemma 6 follows immediately: Lemma 6 (Generalized Version). Let F be a family of [0, 1]-valued functions on X . Then, with probability at least 1 − δ, Before proving Lemma 6, we note a standard symmetrization lemma, which allows us to replace the expectation of TN Yp,t,η with its value on an independent, identically distributed "ghost sample".
Lemma 22 (Symmetrization; Lemma 2 of Bousquet et al. (2003)). Let X and X be independent realizations of a random variable with respect to which F is a family of integrable functions. Then, for any > 0, We now use this lemma to prove Lemma 6.
Proof. To facilitate analyzing the stochastic aspect of the classifier Y f,η , let Z 1 , ..., Z n Now suppose that we have a ghost sample (X 1 , Y 1 , Z 1 ), ..., (X n , Y n , Z n ). Let TN Y f,η denote the empirical true negative rate computed on this ghost sample, and let TN (i) Y f,η denote the empirical true negative rate computed on (i.e., replacing only the i th sample with its ghost). By the Symmetrization Lemma, where the second inequality is a union bound over the Π F (2n) distinct classifications of 2n points that can be assigned by Y f,η with f ∈ F, and the last inequality is from the fact that TN Y f,η and TN Y f,η are identically distributed and the algebraic fact that, if a − b > , then either a − c > /2 or b − c > /2.
For any particular f ∈ F, by McDiarmid's inequality (McDiarmid, 1998), since, for any i ∈ [n], Plugging Inequality (13) into Inequality (12) gives Repeating this argument with − TN instead of TN, as well as with TP, FN, FP and their negatives, and taking a union bound over these 8 cases, gives the desired result.
Finally, we will use these two lemmas, together with the margin and Lipschitz assumptions, to prove Corollary 8, which bounds the sub-optimality of the trained classifier, relative to the generalized Bayes classifier, in terms of the desired CMM.
Corollary 8. Let η : X → [0, 1] denote the true regression function, and let η : X → [0, 1] denote any empirical regressor. Let denote the empirically selected and true optimal thresholds, respectively. Suppose that M is Lipschitz continuous with constant L M with respect to the uniform (L ∞ ) metric on C. Finally, suppose that P X and η satisfies a (C, β)-margin condition around t * . Then, with probability at least 1 − δ, Proof. First, note that since, by definition of ( p, t), this term sits between the second and third lines above. By the Lipschitz assumption, Corollary 8 follows by applying Lemma 5 and the (C, β)-margin condition to (14) and applying Lemma 6 to both terms (15) and (16).

B.1 Lipschitz constants for some common CMMs
Corollary 8 assumed that the CMM M was Lipschitz continuous with respect to the sup-norm on confusion matrices. In this section, we show how to compute appropriate Lipschitz constants for several simple example CMMs. We begin with a simple example: Example 23 (Weighted Accuracy). For a fixed w ∈ (0, 1), the w-weighted accuracy is given by M (C) = (1 − w)TP + wTN. In this case, M clearly has Lipschitz constant L M = max{w, 1 − w}.
For the remainder of this section (only), we will use P := E[Y ] to denote the positive rate of the true labels and P := 1 n n i=1 Y i to denote the empirical positive rate of the true labels. Many CMMs of interest, such as Recall and F β scores, are not Lipschitz continuous over all of C. Fortunately, inspecting the proof of Corollary 8, it suffices for the CMM M to be Lipschitz continuous on the line segments between three specific pairs of confusion matrices, given in Eqs. (14), (15), and (16). Deriving the appropriate Lipschitz constants is a bit more complex, and we demonstrate here how to derive them for the specific CMMs of Recall and F β scores.
Of the six confusion matrices in Eqs. (14), (15), and (16), four are true confusion matrices. These four matrices have the same positive rate TP + FN = P , which is a function of the true distribution of labels. The remaining two matrices are empirical confusion matrices, and hence have the positive rate TP + FN = P , which is a function of the data. By a multiplicative Chernoff bound, with probability at least 1 − e −nP/8 , P ≥ P/2. Thus, with high probability, it suffices for the CMM M to be Lipschitz continuous over confusion matrices with positive rate at least P/2. For Recall and F β scores, this gives the following Lipschitz constants: Example 24 (Recall). Recall is given by M (C) = TP TP+FN = TP P . Thus, M is Lipschitz continuous with constant L M = 2 P over the confusion matrices in Eqs. (14), (15), and (16). Example 25 (F β Score). For β ∈ (0, ∞), the F β score is given by Hence, Hence, M is Lipschitz continuous with constant 2(1+β 2 ) P max β −2 , β −4 over the confusion matrices in Eqs. (14), (15), and (16).
As Examples 24 and 25 demonstrate, the Lipschitz constants of many CMMs can become large when the proportion P is positive samples is small. In particular, when P ∈ O log n n , the L M log(n/δ) n term of Corollary 8 fails to vanish as n → ∞. We believe that some loss of convergence rate is inevitable if P → 0 as n → ∞, due to the inherent instability of such metrics, but further work is needed to understand if the rates given by Corollary 8 are optimal under these metrics. See also Dembczyński et al. (2017) for detailed discussion of Lipschitz constants of many common CMMs.

C Bounds on Uniform Error of the Nearest Neighbor Regressor
In this appendix, we prove our upper bound on the uniform risk of the kNN regressor (Theorem 13), as well as the corresponding minimax lower bound (Theorem 15).

C.1 Upper Bounds
Here, we prove Theorem 13, our upper bound on the uniform error of the k-NN regressor, restated below: Theorem 13. Under Assumptions 11 and 12, whenever k/n ≤ p * ( * ) d /2, for any δ > 0, with probability at least For any x ∈ X , let denote the mean of the true regression function over the k nearest neighbors of x. By the triangle inequality, wherein η − η k ∞ captures bias due to smoothing and η k − η ∞ captures variance due to label noise. We separately show that, with probability at least 1 − N and that, with probability at least 1 − δ, Bounding the smoothing bias Fix some r > 0 to be determined, and let {B r (z 1 ), ..., B r (z N (r) )} be a covering of (X , ρ) by N (r) balls of radius r, with centers z 1 , ..., z N (r) ∈ X .
By the lower bound assumption on P X , each P X (B r (z j )) ≥ p * r d . Therefore, by a multiplicative Chernoff bound, with probability at least 1 − N (r)e −p * nr d /8 , each B r (z j ) contains at least p * nr d /2 samples. In particular, if r ≥ 2k p * n 1/d , then each B k contains at least k samples, and it follows that, for every x ∈ X , ρ(x, X σ k (x) ) ≤ 2r. Thus, by Hölder continuity of η, Finally, if k n ≤ p * 2 (r * ) d , then we can let r = 2k Bounding variance due to label noise Let Σ := {σ(x) ∈ [n] k : x ∈ X } denote the set of possible k-nearest neighbor index sets. One can check from the definition of the shattering coefficient that |Σ| ≤ S(n).
Since the right-hand side is independent of X 1 , ..., X n , the unconditional bound Recall that there is a small (polylogarithmic in r) gap between our upper and lower bounds. We believe that the upper bound may be slightly loose, and that this might be tightened by using a stronger concentration inequality, such as Bennett's inequality (Bennett, 1962), instead of Bernstein's inequality in Inequality (18).
Naively applying Theorem 13 results in very slow convergence rates in high dimensions. For this reason, we close this section with a corollary of Theorem 13, illustrating that the convergence rates provided by Theorem 13 improve if the covariates are assumed to lie on an (unknown) lower dimensional manifold: Corollary 26 (Implicit Manifold Case). Suppose Z is a [0, 1] d -valued random variable with a density lower bounded away from 0, and suppose that, for some Lipschitz map T : [0, 1] d → R D , X = T (Z). Then, N ( ) ≤ (2/ ) d , and S(n) ≤ 2n D+1 + 2, and so, by Theorem 13, k n 2α 2α+d (log n) . This shows that, if the D covariates lie implicitly on a d-dimensional manifold, convergence rates depend on d, which may be much smaller than D.

C.2 Lower Bounds
In this section, we prove Theorem 15, our lower bound on the minimax uniform error of estimating a Hölder continuous regression function. We use a standard approach based on the following version of Fano's lemma: Lemma 27. (Fano's Lemma; Simplified Form of Theorem 2.5 of Tsybakov 2009) Fix a family P of distributions over a sample space X and fix a pseudo-metric ρ : P × P → [0, ∞] over P. Suppose there exist P 0 ∈ P and a set T ⊆ P such that Now, we proceed with the proof. We now proceed to construct an appropriate P 0 ∈ P and T ⊆ P. Let g : [−1, 1] d → [0, 1] defined by g(x) = exp 1 − 1 1− x 2 2 if x 2 < 1 0 else denote the standard bump function supported on [−1, 1] d , scaled to have g X ,∞ = 1. Since g is infinitely differentiable and compactly supported, it has a finite α-Hölder semi-norm: where is any β -order multi-index and g is the corresponding mixed derivative of g. Define M := 64(2α+d)nr d log(nr) Statistical Theory for Imbalanced Binary Classification Note that, for any m ∈ [M ] d , so that ζ m satisfies the Hölder smoothness condition. For any particular η, let P η denote the joint distribution of (X, Y ). Note that P ζ (x, 1) = ζ(x) ≥ 1/4. Moreover, one can check that, for all x ≥ −2/3, − log(1 + x) ≤ x 2 − x.

D Further Experimental Details
Experiments were run using the numpy and scikit-learn packages in Python 3.9, on a machine running Ubuntu 20.04 with an Intel Core i5-9600 CPU and 64 gigabytes of memory. Instructions for reproducing Figures 2 and 1 are included with the code in the supplementary material.