{'fraction_non_alphanumeric': 0.0507765746229776, 'fraction_numerical': 0.014447245025838884, 'mean_word_length': 4.1451133811490255, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 18, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multiclass Classification via Class-Weighted Nearest Neighbors

We study statistical properties of the k-nearest neighbors algorithm for multiclass classification, with a focus on settings where the number of classes may be large and/or classes may be highly imbalanced. In particular, we consider a variant of the k-nearest neighbor classifier with non-uniform class-weightings, for which we derive upper and minimax lower bounds on accuracy, class-weighted risk, and uniform error. Additionally, we show that uniform error bounds lead to bounds on the difference between empirical confusion matrix quantities and their population counterparts across a set of weights. As a result, we may adjust the class weights to optimize classification metrics such as F1 score or Matthew's Correlation Coefficient that are commonly used in practice, particularly in settings with imbalanced classes. We additionally provide a simple example to instantiate our bounds and numerical experiments.


Introduction
Classification is a fundamental problem in statistics and machine learning that arises in many scientific and engineering problems. Scientific applications include identifying plant and animal species from body measurements, determining cancer types based on gene expression, and satellite image processing (Fisher, 1936(Fisher, , 1938Khan et al., 2001;Lee et al., 2004); in modern engineering contexts, credit card fraud detection, handwritten digit recognition, word sense disambiguation, and object detection in images are all examples of classification tasks.
These applications have brought two new challenges: multiclass classification with a potentially large number of classes and imbalanced data. For example, in online retailing, websites have hundreds of thousands or millions of products, and they may like to categorize these products within a pre-existing taxonomy based on product descriptions (Lin et al., 2018). While the number of classes alone makes the problem difficult, an added difficulty with text data is that it is usually highly imbalanced, meaning that a few classes may constitute a large fraction of the data while many classes have only a few examples. In fact, Feldman (2019) notes that if the data follows the classical Zipf distribution for text data (Zipf, 1936), i.e., the class probabilities satisfy a power-law distribution, then up to 35% of seen examples may appear only once in the training data. Additionally, natural image data also seems to have the problems of many classes and imbalanced data (Salakhutdinov et al., 2011;Zhu et al., 2014).
Focusing on the problem of imbalanced data, researchers have found that a few heuristics help "do better," and the most principled and studied of these is weighting. There are a number of forms of weighting; we consider the most basic in which we incur a loss of weight for misclassifying an example of class and refer to this method as class-weighting. Class-weighting provides a principled binary classification in the appendix, and we note that the results are stronger than for multiclass classification.

Related Work
The kNN classifier, first published by Fix and Hodges Jr (1951), is one of the oldest and most well-studied nonparametric classifiers. Early theoretical results include those of Cover and Hart (1967), who showed that the misclassification risk of the kNN classifier with = 1 is at most twice that of the Bayes-optimal classifier, and Stone (1977), who showed that the kNN classifier is Bayes-consistent if → ∞ at an appropriate rate. For overviews of the theory of kNN methods in binary classification (as well as in regression and density estimation), see Devroye et al. (1996); Györfi et al. (2002); Biau and Devroye (2015). Presently, we discuss some of the most recent related work in kNN.
Samworth (2012) studies schemes for reweighting the kNN classifier in order to improve rates for highly smooth regression function; to do this, he uses the order of neighbors' distances, but not their labels as in this paper. Chaudhuri and Dasgupta (2014) proves general distribution-dependent upper and lower bounds for the excess risk with respect to accuracy of kNN. Additionally, they introduce a general smoothness condition and specialize their results to a few specific settings. Döring et al. (2018) considers the excess risk with respect to accuracy and the 2 risk of kNN under a modified Lipschitz condition, which is a special case of the smoothness condition of Chaudhuri and Dasgupta (2014), while avoiding the assumption that the density is lower bounded away from 0. Gadat et al. (2016) considers classification accuracy for general distributions without a strong density assumption and provides rates of convergence of excess risk where is allowed to vary across the covariate space. Cannings et al. (2019) also considers a semi-supervised classification setting where is allowed to vary across the covariate space. Here, the unlabeled samples are used to estimate the density, and the authors obtain an asymptotic form of the excess risk.
Unlike accuracy bounds, our bounds on uniform risk are more closely related to risk bounds for kNN regression, of which the results of Biau et al. (2010) are representative. Biau et al. (2010) gives convergence rates for kNN regression in 2 risk, weighted by the covariate distribution, in terms of covering numbers of the sample space and the variance of the noise. While closely related to our bounds on uniform ( ∞ ) risk, their results differ in a few key ways. First, minimax rates under ∞ are necessarily worse than under 2 risk by a logarithmic factor (as implied by our lower bounds). Second, instead of assuming categorical labels, they assume noise with finite variance; as a result, naively applying their bound to our multiclass setting would give a logarithmic dependency on the number of classes, whereas we derive rates independent of . Perhaps most importantly, that fact that their risk is weighted by the covariate distribution allows them to avoid our assumption that the covariate density is lower bounded away from 0. However, the lower boundedness assumption is unavoidable under ∞ risk and is ultimately necessary for our confusion matrix bounds.
Convergence rates for classification typically require an assumption about how well classes are separated. In binary nonparametric classification, this is commonly specified by the Tsybakov margin condition (also called the Tsybakov or Mammen-Tsybakov noise condition), first proposed by Mammen and Tsybakov (1999). This condition allows for fast rates of convergence for the excess risk; in particular, the rate may be faster than the parametric ( −1/2 ) rate. Audibert and Tsybakov (2007) further demonstrate that plug-in classifiers can achieve very fast rates of convergence under strict conditions. Our results for classification accuracy rely on an appropriate generalization of the Tsybakov noise condition to the weighted multiclass case.
Relative to the large body of statistical theory on kNN classification, little attention has been given to the multiclass case. To the best of our knowledge, the only results are the recent ones of Puchkin and Spokoiny (2020), who consider a method for aggregating over many values of in multiclass kNN in order to adapt to the unknown smoothness of the regression function. As in Samworth (2012), the underlying kNN regression estimates are weighted by distance and not by class label. To derive fast convergence rates, Puchkin and Spokoiny (2020) introduce a natural multiclass analogue of the margin condition of (Mammen and Tsybakov, 1999). We note that their unweighted setting differs from our class-weighted setting in terms of the margin assumption, kNN classifier, and loss function used.
In statistical learning theory, basic multiclass results in terms of accuracy can be found in standard texts (Mohri et al., 2012). Interestingly, cost-weighting has been studied in the multiclass case before with class imbalance as a motivation (Scott, 2012) but in the context of calibrated losses, i.e., the guarantee that minimizing a surrogate loss for the zero-one classification loss does in fact lead to a Bayes-optimal estimator (Liu, 2007;Tewari and Bartlett, 2007).
In addition to weighting, there are three other methods that are commonly used for imbalanced classification: margin adjustment, data augmentation, and Neyman-Pearson classification. Prior work considers adjusting the margins of 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). Although theoretical interest in data augmentation is growing as a result of its success in deep learning (Chen et al., 2019), the techniques used for imbalanced classification, particularly SMOTE, are poorly understood (Chawla et al., 2002). A number of variants have followed, including the use of generative adversarial networks (GANs) to produce additional data (Mariani et al., 2018). Neyman-Pearson classification attempts to minimize the misclassification error on one class subject to a constraint on the maximum misclassification error on a second class. Unlike many methods in imbalanced classification, Neyman-Pearson classification is fairly well-understood theoretically (Rigollet and Tong, 2011;Tong, 2013;Tong et al., 2016). The results build on work in both empirical risk minimization and plug-in methods for nonparametric classification.
Finally, while the focus of our paper is statistical first and foremost, we do point out related computational work, particularly regarding a large number of classes and kNN. In the text-processing community, the problem of a large number of classes is known as extreme classification. Most of the work in this area focuses on efficient computation when algorithms must be sublinear in the number of classes (Joulin et al., 2016;Yen et al., 2018).
There is also extensive work on computing the exact -nearest neighbors estimate more efficiently, but, particularly in high dimensions, fast approximations to -nearest neighbors are also considered (Andoni and Indyk, 2006;Andoni et al., 2018;Indyk and Wagner, 2018;Dong et al., 2019). The goal is to design a classifier that can be quickly evaluated on a large amount of data, especially in higher dimensions. While such approximate algorithms are certainly of interest in the case of modern large-scale datasets, in this paper, we consider simpler exact algorithms and focus on the statistical problem. Additionally, there is some work that attempts to bridge the gap between computational and statistical efficiency in classification. Work in this area is motivated by Hart (1968), who first proposed compressing a data sample for use in classification. Kontorovich et al. (2017) considers a compression scheme that leads to a 1-nearest neighbor classifier and proves that this is Bayes consistent in finite-dimensional and certain infinite-dimensional settings. Gottlieb et al. (2018) studies the computational hardness of approximate sampling compression, gives a compression scheme, and provides a PAC-learning guarantee. Finally, Efremenko et al. (2020) provides a compression algorithm based on locality sensitive hashing and quantifies the convergence rate of the excess risk.

The Class-Weighted Nearest Neighbor Classifier
In this section, we define the kNN regressor and classifier. Given a point in , we define the reordered points 1 ( ) , . . . , ( ) Tie-breaking procedures are well-known; so we assume without loss of generality that there are no ties. Let ⊆ be a measurable set. We define the nearest neighbors regression estimator on bŷ︀ We are most interested in using this with balls in . Thus, we define the open ball of radius centered at to be ( , ) = { ′ ∈ : ( , ′ ) < } and the closed ball of radius centered at to be ( , ) = { ′ ∈ : ( , ′ ) ≤ } . Now, we turn to defining the kNN regression estimate. Fix an integer > 0. Then, the -nearest neighbor regressor at for class is defined to bê︀ (1) In words, the kNN classifier , ( ) is the plurality class of the nearest points to . Finally, we define the -weighted kNN classifier. Let be a vector in the positive orthant R + . Then, the -weighted kNN classifier is Intuitively, is the weight put on classifying an example of class = , and the usual unweighted case corresponds to selecting = (1, . . . , 1). In the unweighted case, we drop the from the classifier subscript and write , ( ) for the standard kNN estimate at . Finally, in many of our results, we reference the maximum element of , and so we write max = max =1,..., .

Error Measures
In the following sections, we define various error measures and additional terminology. Accuracy and uniform error are the first two, and these are the quantities for which we derive bounds for kNN. Subsequently, we consider the confusion matrix.

Accuracy and Risk
In the usual setting, we are interested in two quantities when evaluating the nearest neighbor classifier: the probability of a suboptimal prediction and the risk. First, we define the -Bayes-optimal classifier * by * ( ) = argmax Again, if = (1, . . . , 1), we drop the subscript and write * . For a new test sample ( , ), denote let P be the probability measure with respect to . Then, the first quantity we are interested in is the accuracy, denoted by which is the probability of a suboptimal choice on new data. Note that this is still a random quantity depending on the sample of data points. When we need to take the probability or expectation with respect to the sample, we occasionally emphasize this by writing P and E . Second, we consider the risk. The risk of a classifier is The Bayes risk is * = ( * ( )), and we analyze the excess risk Finally, we consider the -weighted risk. Define the class-conditioned risk of class to be Note that this is related to the population precision of on class . Define the vector of marginal probabilities by = P , ( = ) . Then, the -weighted risk is Note that the -weighted risk does reduce to the usual risk ( ) when = (1, . . . , 1), but we have considered the risk and weighted risks separately because they require different assumptions to analyze. Additionally, the -Bayes classifier * is the minimizer of , and so we define the -Bayes risk to be * and the excess -risk to be ℰ ( ) = ( ) − * .

Uniform Error
In this section, we consider the uniform error. We define the uniform error to be where, for a function : → R, ‖ ‖ ,∞ := sup ∈ | ( )| denotes the sup-norm of . For our results on uniform error, we impose additional requirements on our space and regression function, and so we discuss additional notation. One of the key assumptions is that ( , ) is a totally bounded metric space, and under the assumption that ( , ) is totally bounded, we may introduce covering numbers. For any > 0, let ( ) denote the -covering number of ( , ); that is, ( ) is the smallest positive integer such that, for some 1 , ..., ( ) Finally, for positive integers , let denote the shattering coefficient of the class of open balls in ( , ).

General Classification Metrics
In this section, we consider general classification metrics. A number of commonly-used metrics are derived from the confusion matrix of a classifier, i.e., the true positive, true negative, false positive, and false negative rates. Presently, we define the confusion matrix entries. Usually, practitioners consider the empirical versions of the confusion matrix entries, and we denote these bŷ︂ TP,̂︂ TN,̂︂ FP, and̂︂ FN respectively. For simplicity, let The confusion matrix entries are then defined bŷ︂ In contrast to the usual empirical use of the confusion matrix, we normalize each entry in order to discuss convergence. The population confusion matrix is a result of evaluating the confusion matrix quantities on the true distribution, which gives As we must discretize the space of weights, we define the weights that are covered by a given discretization.

Definition 1. A weight is class -covered by
Let ⊂ R be a finite set of weights. We say that class -covers if it contains a class -cover ( ′ , ′′ ), and we say that is a multiclass cover if it is a cover for all in [ ].

Main Results
In this section, we present our main results for accuracy, risk, and uniform error of nearest neighbor classifiers.

Accuracy and Risk
First, we consider bounds on the accuracy, risk, and weighted risk. The results and proofs divide the space into two parts: a "good" region where the optimal classification is made with high probability and a "bad" region near the true decision boundary. The results are largely multiclass extensions from Chaudhuri and Dasgupta (2014), although we note that the rate differs in for the multiclass risk.
Let Δ in (0, 1] be a constant. We define the effective boundary , ,Δ by where ( ) = inf{ : ( ( , )) ≥ }. That is, , ,Δ is the set of points such that the difference in probability between the optimal class * ( ) at and some other class, on some small ball ( , ), is less than Δ. We can now state the theorem.
Theorem 1. Let be in (0, 1), and pick a positive integer ≤ . Define the terms = · 1 1 − √︀ (4/ ) log(2/ ) and Δ = min Then, with probability at least 1 − with respect to the training data, for a new sample ( , ) we have Theorem 1 tells us that, with high probability over the training data, sub-optimal classifications of new test points are most likely to occur within the effective boundary , ,Δ . Compared to binary classification, here the boundary terms Δ must be larger by a factor of log within the root. Of course, the effect it has on the error depends on the underlying distribution. This theorem can be specialized to more traditional cases of interest where we impose more restrictions. In the following sections, we consider smooth regression functions and a margin condition.

Smooth Measures
In this section, we specialize our accuracy result to smooth regression functions. The first step is to define a notion of smoothness. In the binary classification case of Chaudhuri and Dasgupta (2014), the authors define a regression function to be ( , )-smooth if The regression function is observed to be ( , )-smooth if it is -Hölder.
In the multiclass case, we define smoothness entry-wise. Given scalars in (0, 1/ ) and > 0, we say that is ( , )-smooth if for each in [ ]. As in the univariate case, this is implied if the th coordinate of the regression function is -Hölder.
Remark 1. Suppose that ≥ 16 log 2/ so that ≤ 2 / . The optimal choice of is where , is some constant depending on and . This leads to the bound Note that both and the error probability depend sub-logarithmically on the number of classes .

Margin Conditions
One of the key assumptions for obtaining fast rates in plug-in classification is the Tsybakov margin condition (Audibert and Tsybakov, 2007). Here, we consider two variants: a weighted margin condition and a conditional margin assumption. These allow us to obtain concrete rates of convergence for the excess risk of the kNN classifier. Define Δ ( ) = * ( ) * ( ) ( ) − max ̸ = * ( ) ( ). The weighted margin condition is If we have = (1, . . . , 1), then we recover the usual Tsybakov margin condition. Under this condition, we have the following result.

Corollary 2.
Let be an ( , )-smooth function, and suppose that , satisfies the ( , )-margin condition. Pick according to Remark 1. Then, we have Additionally, if we have the uniform weights = (1, . . . , 1) and pick = ′ , , 2 /(2 +1) , then we can bound the excess risk by We can also consider weighted risk. Since the weighted risk is a linear combination of conditional risks, this requires a conditional margin assumption. Proposition 1. Assume that is an ( , )-smooth function and that the distribution , satisfies the ( , )-conditional margin assumption. Then, we have

Lower Bounds
Finally, as a converse to Theorem 1, we provide a lower bound for accuracy. The strategy for the lower bound is somewhat different in that we need to reduce to the binary case; hence, the set of in providing the lower bound does not naturally mirror the corresponding set , ,Δ in the upper bound as closely as in the binary classification case.
We define our set to be ′ , , ⊆ , and since the definition is lengthy, we first state a few auxiliary definitions. Let ( ) = * ( ) /( * ( ) + ), and define ′ ( , Conditions (A) and (B) are specific assumptions for binomial distributions and, in the unweighted case, can be ignored. Condition (C) is the requirement that is near the decision boundary. Now, we can state the theorem.
Theorem 2. There exists a constant > 0 such that

Uniform Error
We now give bounds on the uniform error (̂︀) defined in (3). We start with additional assumptions.
Assumption 2. We make the following three assumptions.
(a) The pair ( , ) is a totally bounded metric space.
(b) For any positive integers < , let , , denote the marginal is lower bounded in the sense that, for some constants * , * , > 0, for any point in and radius in (0, * ], we have the inequality ( ( )) ≥ * .
(c) Each is -Hölder continuous with constant .
We now provide our bound on the uniform error, proved in Appendix B.
Theorem 3. Under Assumption 2, whenever / ≤ * ( * ) /2, for any > 0, with probability at Of the three terms in (9), the first term, of order ( / ) / , comes from implicit smoothing bias of the kNN classifier, while the remaining two terms, effectively of order √︀ −1 log( ( )/ ), come from variance due to label noise. Notably, in contrast to the risk bounds in the previous section, this bound is entirely independent of the number of classes; indeed the result holds even in the case of infinitely many classes. While this may initially be surprising (as the estimand̂︀ is function taking -dimensional values), the constraint that̂︀ lies in the ( − 1) dimensional probability simplex is sufficiently restrictive to prevent a growth in error with ; that is, adding new classes that occur only with very low probability does not increase the uniform error. As shown in the next two examples, can be selected to balance these two terms.

Lower Bounds
We close this section with the following lower bound on the minimax uniform error, which shows that the rate provided in Theorem 3 is minimax optimal over Hölder regression functions: where the infimum is taken over all estimatorŝ︀.

Application to General Classification Metrics
In this section, we consider general classification metrics to which Theorem 3 may be applied. We start by examining upper and lower bounds for estimating confusion matrix quantities; then we turn to precision, recall, and F1 score, which are derived from the confusion matrix.

Confusion Matrix Entries
First, we consider the uniform convergence of empirical confusion matrix entries to the population confusion matrix. The results of this section do not depend on the choice of regression estimator; so we start with an assumption on the uniform error of the regression estimator.
We showed that this assumption holds for nearest neighbors under additional conditions in the previous section. We now turn to definitions used in our main theorem of this section. Recall that we define max = max =1,..., . Define the quantities For brevity, we write ′ and ′ to denote ( ′ , ·) and ( ′ , ·, ·), and we handle double-primes similarly. Now, we state the theorem.
Theorem 5. Suppose that Assumption 3 holds. Consider a set of weights , and let be a multiclass cover for of size . Let be an element of that is multiclass covered by ( ′ , ′′ ), where ′ and ′′ are in . Define Then with probability at least 1 − , we have

for all in [C] and in simultaneously.
Simultaneous uniform convergence of the confusion matrix entries is a powerful tool for proving the uniform convergence of general classification metrics. We consider an example in Section 5. However, we do note that this bound cannot be calculated from the data itself, unlike in empirical risk minimization, since the bounds depend on the underlying data distribution.

Lower Bounds
In this section, we consider a lower bound for estimating confusion matrix entries. We make two simplifications. First we just consider estimating the true negatives, since similar results may be derived analogously for the true positives, false positives, and false negatives. Second, we consider the binary case. In terms of notation, we consider a threshold , which in binary classification is equivalent to = 1 /( 1 + 2 ). For a more detailed treatment of the binary case, see Appendix C. , belonging to P( , ) for an appropriately-chosen such that with probability at least < 1/4, there is a threshold such that where is defined by = P ( − ≤ ( ) ≤ + ) and can be chosen to satisfy the inequality for some constant .
At this point, we take a moment to clarify how to view Proposition 2 as a natural lower bound to Theorem 5. First, the lower bound is the natural analogue to (tne)( ′ , ′′ , ). Here, since we have to specify the distribution for the lower bound, we get the actual threshold in the expression for instead of ′ ( , ) and ′′ ( , ) as in the expression for (tne)( ′ , ′′ , ) from a covering argument. Second, for the class of -Hölder regression functions, we obtain the proper rate in . Using Theorem 3 in conjunction with Theorem 5, the in (tne)( ′ , ′′ , ) is of order ( − /(2 + ) ) up to logarithmic factors. Our lower bound contains such an of order Ω( − /(2 + ) ), and so the bounds match in . Finally, the expansion of via the union to include the discrete point ′ is solely to control the size of and may be omitted by simply considering = 1.

Precision, Recall, and F1 Score
Now, we turn to the uniform convergence of class-wise precision, class-wise recall, and macro-averaged F1 score with respect to weights. Similar results can be obtained for other general classification metrics such as macro-averaged and micro-averaged precision and recall, usually simultaneously with these results in the sense that there is no further degradation of the probability with which these events hold.
First, we define class-wise precision, recall, and F1 scores by Next, the macro-averaged F1 score is We note that the empirical versions of these quantities may be obtained by simply replacing the confusion matrix entries by their empirical counterparts, and we denote them bŷ︂ prec ,̂︁ rec ,̂︁ F1 , and̂︁ F1. Now, we present our corollaries for these quantities.
Corollary 5. Define prec, ( ) and rec, ( ) by Suppose Assumption 3 holds. Then we have for all for which prec, ( ) > 0 and for all for which rec, ( ) > 0 with probability at least 1 − . Corollary 6. Suppose that Assumption 3 holds. Define F1, ( ) by Then with probability at least and consequently we obtain

An Example
In this section, we consider an example with three classes on the unit interval to make our results on general classification metrics clearer. Specifically, we specify a concrete distribution, illustrate the effects of weighting on optimal class selection, and compute the theoretical errors for estimating the confusion matrix implied by our bounds. Finally, we investigate the error empirically through a simulation study. Python code for reproducing the results in this section is available at https://github.com/neilzxu/weighted_knn_classification. First, we specify the distribution. We let be drawn uniformly from [0, 1], and we set Note that the vector of marginal probabilities is approximately = (0.22, 0.35, 0.43). Next, we examine the effect of weighting. Figure 1 gives the unweighted and weighted regression function for the weighting = (0.5, 0.3, 0.2), which emphasizes the first class most prominently.
Finally, we examine the error region that defines (tne) and (fne) for this regression function and weighting = (0.5, 0.3, 0.2). To determine the error, we have to define a set of permissible
With these parameters, we estimate the true negative error and false negative error. To estimate these, we compute a fine grid 1 , . . . , of the unit interval. Then, we set With a grid of size = 1, 000, we obtain (̂︂ tne)( ′ , ′′ , 1) = 0.20 and (̂︁ fne)( ′ , ′′ , 1) = 0.06. While the error is large for these parameters, it is consequently easy to visualize in Figure 2. Specifically, we plot the curves 1 ( ), ′ (1, ) − ′ (1), and ′′ (1, ) + ′′ (1). Additionally, we shade the region down to the -axis where 1 ( ) is between the other two curves, and the measure of the shaded region on the -axis is equal to (̂︂ tne)( ′ , ′′ , 1) + (̂︁ fne)( ′ , ′′ , 1). Informally, when 1 ( ) is not between the other two curves, then there is enough signal to determine that class 1 should or should not be chosen with high probability; when 1 ( ) is between the other two curves, then making an error is more likely. Our final task in analyzing this example is to draw samples, compute a kNN estimator, and then determine the true errors in estimating the confusion matrix. For this, we run 1, 000 trials in which we pick sample points and use weighted -nearest neighbors with = (0.5, 0.3, 0.2). For each trial, we calculate the error of the confusion matrix entries, and then we average this over the trials. The results can be seen in Table 1. For a large enough sample size, we see that the errors do indeed diminish, e.g., for = 1, 000 and = 49, all confusion matrix errors are under 0.05. Note that these numbers are not directly comparable to the theoretical error upper bound obtained earlier because we did not have an exact relationship between and due to unknown constants. However, the numerical results do suggest that the confusion matrix entries may be accurately Table 1. Average confusion matrix errors over 1, 000 trials of samples with -nearest neighbors weighted by = (0.5, 0.3, 0.2). For this particular distribution and weighting, true negatives are hardest to estimate.
estimated when the sample size is sufficiently large. This ultimately serves as justification for using empirical estimates of the target metric to adjust weights when attempting to optimize a general classification metric such as F1 score. We discuss this further in the next section.

Optimization
In this section we introduce two basic algorithms for optimizing a general classification metric and perform experiments on real and synthetic data to examine the error with respect to the macro-averaged F1-score defined in equation (10). In contrast to the example given in the previous section where was fixed, here we choose adaptively. Python code for reproducing the results in this section is available at https://github.com/neilzxu/weighted_knn_classification.

Algorithms
We start by introducing our algorithms. Our first algorithm is a coordinate-wise greedy algorithm for choosing . At each step, we construct candidates by increasing or decreasing a single coordinate of and normalizing to obtain a new ′ . We do this for all coordinates, yielding 2 candidates, and then we select new weighting ′′ that has the highest̂︁ F1-score. Our algorithm is given in Algorithm 7, and we use to denote the th standard basis vector. In addition to the greedy algorithm, we also perform a grid search over the weights, and we defer details of this algorithm to the Appendix. The benefit of grid search is that it is attains better performance than greedy algorithms in the absence of additional structure; the drawback is that in general computation scales exponentially in the number of classes .  . Empirical and population F1-score by step in the greedy algorithm and by sample size in the greedy algorithm, grid search, and unweighted classifier. For (a), the sample size is = 1, 000. The quality of the solution depends very modestly on the step size. For (b), the greedy algorithm is run with = 20 and = 0.01, and grid search is conducted with differences of 0.01. The greedy algorithm achieves similar performance to that of grid search, and the difference between empirical and population F1 decreases with . It also has marginally better population F1 than the baseline unweighted classifier for sample sizes greater than = 1, 000.

Data
We use two types of data for our experiments: synthetic and real. The synthetic data comes from the simple distribution described in Section 5. For the synthetic experiments, we use an initial weighting (0) = (0.3, 0.3, 0.4), which is close to the unweighted classifier, and use = min nearest neighbors, which leads to asymptotically optimal convergence of the uniform error, on a sample of size .
For real data, we use the Covertype dataset (Blackard and Dean, 1999) from the UCI dataset repository (Blake and Merz, 1998). This dataset contains 54 cartographic features and 7 classes corresponding to different types of forest cover for a patch of land. The dataset is split into train, dev, and test sets with 11,340, 3,780, and 565,892 samples respectively.

Results
In this section, we examine the performance of our algorithms on the two datasets.

Synthetic dataset
We start by considering the synthetic data. We perform two different experiments on the synthetic dataset. First, we examine the effect of different step sizes on the weights found by the greedy algorithm. Second, we compare the performance of each algorithm as the training set size increases. In addition to examininĝ︁ F1, we can also compute the population F1 score to determine how well the resulting classifier generalizes. For our experiments we use = 10, 000 to form a grid for numerical computation of the confusion matrix, and calculate the F1 score using the confusion matrix.
To examine the difference in̂︁ F1 and F1 achieved by the greedy algorithm for different step sizes, we use a step count = 20, a dataset of size = 1, 000, and step sizes of 0.01 and 0.05. Table 2. Training and testing F1 scores on the Covertype dataset for our greedy classifier, grid search classifier, unweighted kNN, and a linear classifier (logistic regression). The linear classifier performs best, reflecting the separability of the dataset. Greedy search outperforms both grid search and baseline unweighted classifier on test F1. The learned weights for the greedy and grid search have a similar distribution, yet thê︁ F1 score of grid search is much higher, suggesting overfitting. shows that a greedy algorithm with the step size 0.05 finds a weighting that is better in both empirical and population F1. However, the algorithm takes few steps, since it gets stuck quickly with both step sizes. Next, we examine the relationship between̂︁ F1 and F1 of the greedy algorithm, grid algorithm, and unweighted classifier as increases. For the greedy algorithm we choose parameters = 20 and = 0.01. To calculatê︁ F1 and F1, we average each score of each algorithm over 50 trials for each . For grid search, we choose a grid over the weight space with a spacing of 0.01 between points. Figure 3b shows that̂︁ F1 seems to converge towards F1 as increases for all 3 classifiers, although the greedy and grid algorithms converge much faster than the unweighted classifier. The convergence is consistent with the convergence of individual entries of the empirical confusion matrix to their corresponding entries in the true confusion matrix. For all 3 classifiers, the population F1 remains relatively similar across all , with the greedy algorithm performing marginally better than the unweighted classifier, and the grid algorithm performing marginally worse. The similarity in performance between the unweighted, i.e., usual kNN, and the approaches that optimize the weights may be in part due to the relatively balanced nature of the problem, since the class probabilities are 0.22, 0.35, and 0.43 respectively, leading to the optimal choice of weights being relatively close to having equal weights across classes.

Algorithm̂︁
The greedy algorithm also has consistently higher population F1 than grid search. This may be a consequence of the initial weighting being close to final weighting for the greedy algorithm, allowing it to do more slightly more granular search than the grid algorithm. In any case, these experiments demonstrate that greedy search over the weights can perform as well as grid search empirically.

Real dataset
For the real dataset, we fit the underlying kNN model to the training set, and then fit weights on the dev set. We finally evaluate the F1 performance of our optimized weights on the test set.
Here, we consider̂︁ F1 as the F1 score of classifier on the training set and population F1 as the F1 score on the test set. For the kNN classifier, we chose = 160. We set the initial weighting for our greedy algorithm to be the balanced weighting, and search for = 25 steps with a step size of = 0.02. For the grid algorithm, we use a grid with a spacing of 0.083 between points. In addition to considering these algorithms, we also consider the unweighted baseline kNN classifier, as well as a simple logistic regression classifier trained with stochastic gradient descent.
We present our results, consisting of the train F1, test F1, and final class weights, in Table 2. The linear classifier vastly outperforms the kNN models, showing the relatively linearly separable nature of this dataset. Reflecting their performances on the synthetic experiment, the greedy algorithm has the highest test F1 score when compared to the grid algorithm and the unweighted classifier, both of which have the same F1 score. The higher̂︁ F1 of the grid algorithm compared to the greedy algorithm suggests it overfit on the training dataset. We do note that the learned weights of the two algorithms are similar, however. In particular, both the greedy and grid algorithm place much of their weight on class 4.

Discussion
While we make progress in the theory of modern classification problems using nearest neighbors, there are still a number of future directions, both statistical and computational. First, there are still many questions on how to optimize a given metric such as F1 score. For instance, it is unclear that our algorithms find the optimal weighting, or whether such weighted plug-in approaches are even optimal as in the binary classification case. Second, we would also like a method that finds an optimal weighting as the number of classes grows large. In this regime, we cannot effectively use grid search because it requires exponential computation in the number of classes. Finally, the ultimate goal is to produce a computationally efficient classifier with minimax optimal statistical risk with respect to a given metric, again such as F1 score. To the best of our knowledge, such a classifier and the rate of convergence of the risk is not known for any non-trivial problem, parametric or nonparametric.

A Proofs for Accuracy and Risk
In this section, we consider proofs for accuracy and risk. Our main results are Theorem 1, Corollary 1, Corollary 2, Proposition 1, and Theorem 2.

A.1 Proof of Theorem 1
The goal of this section is to prove Theorem 1. Before the main proof, we establish a few lemmas.

Lemma 1. Let be an arbitrary point. Define the events
Then, we have the inequality Proof. Suppose that is not in ,Δ . Then, if event ℬ does not occur, there are + 1 sample points within a radius ( ) of . Thus, in order for , , ( ) ̸ = * ( ) to occur, we must have for some ̸ = * ( ). Since is not in ,Δ , this means that Thus, event must occur. Now, we present a union bound lemma. Let For simplicity, let , = ∅.
Lemma 2. We have the following inequality: The proof is immediate, since if the left hand side is 1, then one of the summands on the right must also be 1.

Lemma 3. We have the probability bounds
Proof. The proof consists of applying Hoeffding's inequality to a sampling scheme that makes it clear that the event , only depends on random variables. The sampling procedure is as follows: (1) first sample 1 , 1 from the marginal distribution of the ( + 1)-nearest neighbor of ; (2) sample pairs ( 2 2 ), . . . , ( +1 , +1 ) independently of each other from the distribution of the -nearest neighbors of conditional on the ( + 1)st-nearest neighbor; (3) sample the remaining − − 1 points indpendently of each other from the distribution of the remaining points, conditional on the ( + 1)st-nearest neighbor; (4) shuffle the points.
Now, the resulting sample has the same joint distribution as the standard iid sampling scheme. Additionally, the event , only depends on the points sampled in step (2). Thus, we can apply Hoeffding's inequality to the random variables for = 2, . . . , + 1 to obtain the first inequality of the lemma. The second follows immediately, completing the proof.

Lemma 4. Let be an arbitrary point of . Let and be constants in
Since ≤ E1 { ( , ) ≤ ( )}, we can apply the multiplicative Chernoff bound to obtain This completes the proof. Now, we can prove our main theorem.
Proof of Theorem 1. Applying Lemma 1 and taking expectations with respect to , we have Since P ( ) = ( ,Δ ), it simply remains to show that := P ( ) + P (ℬ) ≤ with probability at least 1 − .
By Lemma 4, we have Applying Lemma 2 and Lemma 3, we have The final step of the proof is to plug in values for Δ and and to use a simple concentration argument. First, we have Thus, we have ≤ 2 . Applying Markov's inequality, we then have Combining this with equation (11) completes the proof.

A.2 Proof of Corollary 1
In this section, we prove Corollary 1. We start with a lemma.
Proof. Pick ≥ 0, ≤ ( ). Let be in supp( ). Then by ( , ) smoothness, we have Similarly, we have Proof of Corollary 1. All that we have to do is apply Theorem 1 and Lemma 5 and then perform a few simple upper bounds. From these two results, we have which completes the proof.

A.3 Proof of Corollary 2
In this section, we prove Corollary 2. For the first bound, we apply the margin condition to the result of Remark 1. This yields which completes the proof. For the risk, we have two lemmas, proved in Appendix A.6. We start with a pointwise bound.

A.4 Proof of Proposition 1
The goal of this section is to prove Proposition 1. We start by examining excess weighted risk ℰ and its relation to accuracy of the -Bayes estimator * .

Lemma 8. We have the bound
Proof. The proof is straightforward; we observe that This completes the proof.
Lemma 9. Let * > 0. Then for such that Δ ( ) > * , we have Proof. By Lemma 1, we may apply the conditional measure P (·| = ) to obtain where the events , ℬ, and are as in Lemma 1. Thus, it suffices to bound these probabilities, and we do so in reverse order. First, set Δ = Δ ( ) − * . Then since by assumption Δ ( ) > * , we see that is not in ,Δ− . Thus, we have 1( ) = 0 and therefore P ( | = ′ ) = 0. Next, we consider the bound on the conditional probability of ℬ. Since ℬ is independent of the event { = ′ }, the bound of Lemma 4 holds for the conditional measure P (·| = ′ ) instead of the usual measure, and so we have when we set = 1/2.
Finally, we consider the bound on the conditional probability of . Since the events , are independent of the event { = ′ }, we may apply Lemma 2 and Lemma 3 to obtain and this completes the proof.
Proof. We start by decomposing the conditional error probability into two parts: when is in the margin and when is not in the margin. We need to set the margin carefully, and so we define = 2 . Here, and later are simply indices and are unrelated to the classes. To this end, we write For the first term, if is in ,Δ , then we require Δ( ) ≤ . Thus, we have where the last inequality follows from the conditional margin assumption. Thus, we simply need to bound 2 . By applying Lemma 9, we obtain Thus, we need to bound 3 .
We apply the margin condition for increasing values of Δ( ), which gives . Now, we need to pick a good so that the above series converges nicely. We set With this choice of , we wish to show that our upper bound on each element of the series decreases by a factor of at least 1/2. So, we have where the final inequality follows from Lemma 14. By our choice of , we have ≤ 2 exp (−(1 + )) ≤ 1 2 .
Returning to bounding 3 , we have where ′ = 2 is a constant. Putting everything together, we have where ′′ = 2 ′ = 4 is a constant and the final equality comes from plugging in our choice of . This completes the proof.
Proof of Proposition 1. By Lemma 8 and Lemma 10, we have If we set = 2 (2 +1) , then we obtain the bound for some constant , , . This completes the proof.

A.5 Proof of Theorem 2
For this proof, we embark on a three-part approach. First, we use the sequential sampling scheme to control the -nearest neighbors to a point . Next, we fix some sub-optimal class and reduce the multiclass classification to a binary classification where we get to choose between class and the optimal class. Third, we provide a lower bound on the probability of suboptimal classification for weighted binary classification. Putting the proof together then involves unraveling our steps in reverse order. The approach is largely based on the binary classification approach of Chaudhuri and Dasgupta (2014); however, we need to give a more extensive and careful conditioning argument.

Randomly permute the examples to obtain
By construction, we see that the resulting sample has the same distribution as simply sampling by the usual iid method. However, the upshot is that this approach makes it clear that we can think of sampling as a relatively simple sequential process that in turn clarifies conditional independences. More precisely, we ultimately need the sigma-fields 1 = ( ( , (1) )) = ( ( , +1 ( ) )) and 2 = ( ( , (1) ), ), where is a random variable to be defined shortly.
The ( + 1)st nearest neighbor of is given in step 1 of the sampling scheme, and we want to show that it lies in an annulus about . Define We then have the following lemma.
Ultimately, we want to treat the problem as one of choosing between and * ( ) using the observations. But before proceeding to that step, we state a simple lemma on the concentration of .
Proof. First, we quickly observe that the second inequality is an immediate consequence of the first. Assuming that 1( 1 ) = 1, then we have 2 ≤ P( 2 | 1 ) by the first conclusion of the theorem. If 1( 1 ) = 0, then the second inequality reduces to 0 ≤ 0, which is certainly true. Thus, we simply need to establish the first inequality. The proof is a straightforward application of Hoeffding's inequality. First, we note that )/ ] on the event 1 . Thus, it suffices to prove the result for ′ 2 ( ). By the two-sided version of Hoeffding's inequality, we have 2 = 1 − 2 exp(−2) ≤ P( ′ 2 ( )| 1) ≤ P( 2 | 1 ) on the event 1 and this completes the proof of the lemma.
Bounding the binary classification error. Finally, we arrive at the third step of the proof: analyzing the binary classification problem between and * ( ). In particular, define the event ). This event is contained within the event { , , ( ) ̸ = * ( )}. Moreover, we can rewrite this as We point out that in the case of uniform weighting, the threshold = * ( ) /( * ( ) + ) in the last expression reduces to 1/2; so indeed we have reduced the problem to a weighted binary classification problem (cf., Appendix C). Our task is now to lower bound the probability that̂︀ ( ′ ) exceeds a threshold . Since, under the appropriate conditioning, ′ =̂︀ ( ′ ) is a Binomial( , ′ ) random variable where ′ = ( ′ )/( ( ′ ) + * ( ) ( ′ )), we naturally return to Slud's inequalities.
Lemma 13. Assume that ′ satisfies 0 < ′ < 1/2. Suppose that ≤ 1 − ′ , that − 1/ √ ≤ ′ , and that is sufficiently large to guarantee 0 < − 1/ √ . Then, there exists a constant 3 > 0 such that on the event 2 we have the inequality 3 ≤ P ( 3, | 2 ) , and consequently, Before we prove the lemma, we make a brief remark. Note that if one is only interested in the unweighted setting, then we can drop the assumption that ′ < 1/2 because it is necessarily satisfied by the definition of * ( ).
Proof. The second inequality is a direct consequence of the first: if 3, occurs, then the former inequality provides the result; if 3, does not occur, then both sides are zero. Thus, it suffices to prove the second inequality.
First, we recall that ′ =̂︀ ( ′ ) has a Binomial( , ′ ) distribution, and both and ′ are measurable with respect to 2 . Thus by expanding the measure to include some standard normal random variable independent of all other variables and invoking Lemma 35, we have By our condition on ′ , we see that this is in turn lower bounded by So, the only remaining task is to apply the condition that 2 occurs. On 2 , the variable is upper bounded by + √ , and so we have Since the only random variable appearing in the probability on the left-hand size is the standard normal , the left-hand side is lower bounded by some constant 3 , and so we have 3 ≤ P ( 3, | 2 ), as desired.
Completing the proof. Now, the only thing left to do is to put the pieces together. As a first step, we wish to lower bound the probability for fixed , which we can randomize later. To this end, our strategy is to use the tower property and our preceding lemmas.
Using the tower property of conditional expectations, we have By Lemma 13, we obtain Next, we again use the tower property to obtain Applying, Lemma 12, we obtain 2 3 E[1( 1 )] ≤ . Finally, Lemma 11 yields Replacing the fixed by a random variable , taking expectations with respect to , and using Fubini's theorem then yields ( ′ , , ) ≤ E P ( , , ( ) ̸ = * ( )), which completes the proof.

A.6 Proofs of Lemmas
Proof of Lemma 6. Define the events , ℬ, and as in Lemma 1. For the following, we set Δ = Δ( ) − * , which implies that 1( ) = 0. By Lemma 1, we have So, it suffices to bound these two probabilities. By Lemma 4, with the choice of = 1/2, we have Thus, it suffices to bound the probability of event .
Proof of Lemma 7. We need to decompose the expectation into two parts based on when is in ,Δ . Define = · 2 . For the moment, let > 0 be an arbitrary integer. Set Δ = . We have The first term can be bounded by observing that ∈ ,Δ implies that Δ( ) ≤ . Thus, we have where the last inequality follows from the margin condition. Thus, it remains to bound 2 . For 2 , we apply Lemma 6 to obtain Thus, it only remains to bound 3 . To do this, we want to apply the margin condition for successively increasing values of Δ( ). Then, we have Now, our goal is to pick so that this sum is finite. To this end, we pick With this choice of , we observe that our upper bound for each element of the series decreases by a factor of at least 1/2. This can be seen by observing The last inequality follows from Lemma 14. From our choice of above, we see that for ≥ we have ≤ 2 exp(−(1 + )) ≤ 1 2 .
Returning to bounding 3 , we now have Putting everything together, we have where the maximum term comes from the definition of . This completes the proof.

A.7 Auxiliary Lemmas
Lemma 14. We have the inequality Proof. This is satisfied for the case of = 1 with equality; so we consider > 1. We can bound the left hand side by Note that in the second inequality we used < 2( − 1) for > 1. This completes the proof.

B.1 Upper Bounds
In this appendix, we prove Theorem 3. Note that, in this section, we use ‖ · ‖ ∞ to denote the vector sup-norm on R and ‖ · ‖ ,∞ to denote the function sup-norm on . We begin with a simple lemma concerning the behavior of multinomial random variables: is drawn from a multinomial distribution with trials and mean ∈ Δ −1 . Then, for any ∈ (0, 1), with probability at least 1 − , Proof. By Jensen's inequality and the fact that Note that ‖ / − ‖ ∞ is 1/ -Lipschitz in each of the independent trials of . Hence, by McDiarmid's inequality, with probability at least 1 − , We now proceed to prove Theorem 3. For any ∈ , let︀ denote the mean of the true regression function over the nearest neighbors of . By the triangle inequality, wherein ‖ −̃︀ , ‖ ,∞ captures bias due to smoothing and ‖̃︀ , −̂︀ ‖ ,∞ captures variance due to label noise. We separately show that, with probability at least 1 − and that, with probability at least 1 − , Bounding the smoothing bias. Fix some > 0 to be determined, and let { ( 1 ), ..., ( ( ) )} be a covering of ( , ) by ( ) balls of radius , with centers 1 , ..., ( ) ∈ . By the lower bound assumption on , each ( ( )) ≥ * . By a multiplicative Chernoff bound, with probability at least 1 − ( ) − * /8 , each ( ) contains at least * /2 samples.

B.2 Proof of Theorem 4
In this section, we prove 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: where the first inf is taken over all estimatorŝ︀. Now, we proceed with the proof. We now proceed to construct an appropriate 0 ∈ and ⊆ . Let : [−1, 1] → [0, 1] defined by denote the standard bump function supported on [−1, 1] , scaled to have ‖ ‖ ,∞ = 1. Since is infinitely differentiable and compactly supported, it has a finite -Hölder semi-norm: where ℓ is any ⌊ ⌋-order multi-index and ℓ is the corresponding mixed derivative of . Define Note that, for any ∈ [ ] , so that satisfies the Hölder smoothness condition. For any particular , let denote the joint distribution of ( , ). Note that ( , 1) = ( ) ≥ 1/4. Moreover, one can check that, for all ≥ −2/3, − log(1 + ) ≤ 2 − . Hence, for any ∈ , and, similarly, since ( , 0) = 1 − ( ) ≥ 1/4, Adding these two terms gives Fano's lemma therefore implies the lower bound inf︀ sup which completes the proof.

C General Classification Metrics in Binary Classification
While the main focus of our paper is the multiclass classification setting, in this appendix, we consider general classification metrics in binary classification. We consider the binary case because because it is an important case, it simplifies the notation, and the results are stronger. There are also two other important properties that have been observed previously in this setting. First, class-weighting of the regression function is equivalent to setting a threshold for classification, which we explain in greater detail in the sequel. Second, for a certain family of general classification metrics to be maximized, including precision and recall but not F1 score, choosing the correct threshold maximizes the general classification metric.
Thus, the organization of this section is as follows. In Section C.1, we discuss the notational simplifications for binary classification and the equivalence of weighting and thresholding. In Section C.2, we discuss the main results on the empirical convergence of confusion matrix quantities to the optimal confusion matrix quantities uniformly over the choice of threshold. In Section C.3, we provide corollaries for the uniform convergence of precision, recall, and F1 score, although our method is far more general and may be applied to other general classification metrics. Finally, in Section C.4, we prove the results of this appendix.

C.1 Binary Classification Setup
In this section, we discuss modifications for the binary case, examine the equivalence of weighting and thresholding, and define our confusion matrix quantities. For the binary case, we first let = {0, 1}, as is traditional in nonparametric classification. Here, the regression function : → [0, 1] is defined to be ( ) = P ( = 1| = ) .

C.1.1 Thresholding and Weighting in Plug-In Classification
Next, we consider the equivalence of weighting and thresholding in plug-in classification. Usually in plug-in classification, given a point to classify, we pick the class with the highest estimated probability. Thus, we pick 1 if̂︀( ) ≥ 1 −̂︀( ) or 0 otherwise. By rearranging, we obtain the new decision rule where we select class 1 if̂︀( ) ≥ 1/2 and 0 otherwise.
The modification for thresholding is immediate: instead of selecting class 1 for̂︀( ) ≥ 1/2, we can select 1 for̂︀( ) ≥ , where is a threshold in [0, 1]. The modification for weighting requires slightly more work. Given non-negative weights 0 and 1 , we revise the original decision rule; so we predict class 1 when Rearranging, this is equivalent to Thus, picking a set of non-negative weights is equivalent to choosing a different threshold in binary classification. For our binary classification results, we consider thresholding because we find it is more intuitive, but we note that weighting extends more cleanly to the multiclass case considered in the rest of the paper.

C.1.2 Confusion Matrix Quantities
In binary classification, the confusion matrix is generally only computed with respect to the class = 1. Thus, the empirical confusion matrix quantities arê︂ The Bayes confusion matrix is a result of evaluating the confusion matrix quantities on the true distribution, which gives We would like to maximize TN and TP and minimize FP and FN. Or, alternatively, we would like to maximize or minimize some function of these quantities. These quantities are not computable because we do not know the underlying data-generating distribution, but we may estimate these quantities through their empirical counterparts. Thus, the goal is to show that the empirical confusion matrix converges to the Bayes confusion matrix. Further, since we generally pick the thresholds after examining the empirical confusion matrix, we would like the convergence to be uniform over the choice of threshold.

C.2 Uniform Convergence of the Confusion Matrix
In this section, we present our uniform convergence result for the empirical confusion matrix to the Bayes confusion matrix. We start with a "uniform convergence" assumption for the regression estimator.
Assumption 4. We assume the regression function estimate converges uniformly. More precisely, for every > 0, and for all sufficiently large, we have with probability at least 1 − /2 ‖ −̂︀‖ ,∞ ≤ . Now, we state the main result for this appendix.

Proposition 3. Suppose that Assumption 4 holds. Let
Then with probability at least 1 − , we have the bounds In the bounds, the first term should decrease with for sufficiently nice distributions, and the second term increases in . Additionally, since is only used in the analysis, we may optimize the choice of cover, although the optimal cover depends on the unknown data distribution. We additionally note that this is a stronger result than the multiclass result of Theorem 5 because the set may include 0 and 1. In contrast, Theorem 5 become vacuous when for weights that approach 0 in a coordinate. Our analysis shows that this arises since in binary classification, the probability of class ( ) specifies the conditional probability of both = 0 and = 1.

C.3 Precision, Recall, and F1 Score
In this section, we consider three general classification metrics commonly considered in imbalanced classification: precision, recall, and F1 score. Similar bounds can be obtained for other general classification metrics that are sufficiently nice functions of the confusion matrix.
We Suppose that Assumption 4 holds. Then, with probability at least 1 − , we have for every in [0, 1] for which prec ≥ 0.
We make the assumption that prec ≥ 0 to simplify the algebra and presentation; a more carefully stated bound could likely relax or modify this assumption.
Next, we turn to recall. Recall and empirical recall are defined as We now state a similar convergence result.

Corollary 9. Define the error bound
Suppose that Assumption 4 holds. Then with probability at least 1 − , we have for all such that F1 ( ) ≥ 0.

C.4 Proofs
In this section, we prove Proposition 3 and the ensuing corollaries. For the former, we rely on decomposing the difference between the confusion matrix and its empirical counterpart via a discretization and an intermediate confusion matrix. We define the intermediate confusion matrix to bẽ︂ These terms are just what the true regression function would obtain on the observed data under plug-in estimation.
For the remainder of the proof of Proposition 3, we only consider the true negatives entry of the confusion matrix; the proofs for the other three entries are analogous. So, we consider our decomposition lemma.
Lemma 17. Let and ′ be any elements of [0,1]. We have the inequality .
The benefits of this decomposition are as follows. First, ′ should be an element of a finite cover of ′ . Then, on the right hand side, and may be bounded by Hoeffding's inequality. Importantly, since we are choosing a finite cover, we can use a union bound to guarantee this is small for all ′ in the cover. Next, and on the right hand side are approximation terms. These rely on a distributional assumption that a fine enough partition of the interval [0, 1] leads to small approximation errors, which is reasonable in most circumstances.
Before continuing on to the estimation and approximation errors, we define an event that simplifies the exposition. Let unif be the event We shall use this frequently.

C.4.1 Estimation Errors
In this section, we bound and of Lemma 17. We state the following bound for true negatives.

Define the event
where is a binomial random variable that we specify in the proof. Suppose that and unif hold. Then, we have the bound Moreover, we have P( ) ≥ 1 − .
Proof. First, we note that and so it suffices to analyze each of these terms separately. Under unif , we havê︂ The other bound is nearly identical. We have Under , , we have the desired bound on ( ). Additionally, the sum is a Binomial( , ( , )) random variable; so applying Hoeffding's inequality shows that P ( , ) ≥ 1 − . Now, we turn to of Lemma 17. Applying Hoeffding's inequality completes the proof.

C.4.2 Approximation Errors
In this section, we bound and of Lemma 17.
Lemma 20. Let ′ and ′′ be cover elements such that ′ ≤ ≤ ′′ . Then, we have Proof. The proof consists of straightforward manipulations. First, we note that Thus, it suffices to analyze TN( ′′ ) − TN( ′ ). We have which completes the proof.
The next lemma concerns the approximation error for the empirical quantities. The only trick here is that we need to use Assumption 3 to convert the empirical regression function back to the true regression function.

and the random variable
If event unif and ′ , ′′ hold. then, we havê︂ Additionally, we have P Proof. We start by performing simple manipulations and using event unif to obtain︂ We observe that is a binomial random variable with trials and success probability ( ′ , ′′ , ). Thus, Hoeffding's inequality completes the proof.

C.5 Proof of Proposition 3
We apply Lemma 17 to obtain Thus, we turn to using our lemmas. By assumption, we have P ( unif ) ≥ 1 − /2; so we need to set our error probabilities for the events ′ , ′ , and ′ , ′′ accordingly. We pick ′′ = /(24 ) because we need to bound the error probabilities for the prior three events for each ′ in , since ′′ in ′ , ′′ is fixed given ′ , and each of the four quantities of the confusion matrix.
Applying Lemma 18 for ′ for each ′ in , Lemma 19 for ′ for each ′ in , Lemma 20, and Lemma 21 for ′ , ′′ each pair of consecutive elements ( ′ , ′′ ) in with error probability ′′ in every case, we have Note that each term of the infimum is less than or equal to This result holds with probability at least 1 − , and moreover the analogous statements hold for all other confusion matrix quantities and all in [0,1]. This completes the proof.
If prec ( ) ≥ 1, then since empirical precision is bounded by 1, the previous inequality is also true, which proves the upper bound. Then, on the event rec , we have Since the proof is entirely analogous to that of Lemma 22, we omit it and skip straight to the proof of Corollary 8.
Proof of Corollary 8. By Proposition 3, the event rec occurs with probability at least 1 − . The inequality of Lemma 23 completes the proof.
Next, we prove our corollary for F1 score. The proof only differs modestly from the proofs for precision and recall. As before, we start with an approximation lemma.

Lemma 24. Define the event
Then, on the event F1 , we have Proof. We upper bound and lower bound the empirical F1 score under F1 . Starting with the former, we havê︁ This completes the proof of the lemma.
Proof of Corollary 9. By Proposition 3, event F1 occurs with probability at least 1 − . Thus, applying Lemma 24 completes the proof.

D Proofs for Multiclass Confusion Matrix Quantities
The main goal of this section is to prove Theorem 5. Since all confusion matrix entries behave similarly, we only prove the results for true negatives; the results for the other entries are proved nearly identically. Our goal is to use a decomposition of the difference between the empirical true negatives and the actual true negatives, along with our discretization of the space of weights. We start with the decomposition; for brevity, we define Next, we define the intermediate confusion matrix quantities︂ In what follows, we frequently use the event

D.1 A Decomposition Lemma
Now, we can state our decomposition lemma.
Lemma 25. Let and ′ be any elements of . We have the inequality .
The proof is a straightforward application of the triangle inequality.

D.2 Estimation Errors
In this section, we consider bounds on ( ) and ( ). The results are similar to those in the case of binary classification.

Define the event
where is a binomial random variable that we specify in the proof. If unif and , hold, then, we have Moreover, we have P ( , ) ≥ 1 − .
Proof. We note that by separately. We start with the former and obtain︂ Under event unif , we havê︂ We now consider the second term in the maximum defining ( ). The analysis is essentially unchanged; we have Under event unif , we obtain Thus, we see that ( ) ≤ / ; so it suffices to bound . Under , we have the desired bound Additionally, since is a Binomial random variable with trials and parameter ( , ), applying Hoeffding's inequality proves P ( ) ≥ 1 − .
Applying Hoeffding's inequality completes the proof.

D.3 Approximation Error
Recall that we define ′ ( ) and ′′ ( ) by Furthermore, we have Proof. Since ( ′ , ′′ ) is a class -cover of , we have for all in . Consequently, we obtain A similar proof holds for |TN ( ′′ ) − TN ( )|, which proves the lemma.
Lemma 29. Define the probability , and the event where is a binomial random variable that we define in the proof of the lemma. We have the following results.

D.4 Proof of Theorem 5
We apply Lemma 25 to obtain Subsequently, we examine each of these terms individually. We apply Lemma 26, Lemma 27, Lemma 28, and Lemma 29. For the events ′ , ′ , and ′ , ′′ , we need to specify the error probabilities.
For ′ , we specify an error probability of ′′ = /(24 ), since we need to use the lemma for each ′ in , each in [ ], and each entry of the confusion matrix. Thus by Assumption 3 and Lemma 26, we have for all and ′ with probability at least 1 − 2 /3. For ′ , we specify an error probability of ′′ = /(24 ), as well, since again we need to apply this lemma and its analogue for each ′ in , each in [ ], and each entry of the confusion matrix. Thus, by Assumption 3 and Lemma 27, we obtain for all and ′ with probability at least 1 − 2 /3. The term ( , ′ ) is the easiest since it is an almost-sure bound. By Lemma 28, we can bound ( , ′ ) by Finally, we turn to the event ′ , ′′ . Here we use the error probability ′′′ = /(24 2 ) because we have to apply Lemma 29 for each element ′ of , each in [ ], a different ′′ in for each ′ and , and each of the confusion matrix quantities. By Lemma 29, we have the following bound for ( , ′ ): ( , ′ ) ≤ ( ′ , ′′ , ) + √︃ log 24 2 2 with probability at least 1 − 2 /3 Putting everything together, we have with probability 1 − because we only need to count P ( unif ) ≤ /2 once in the final union bound. Furthermore, this result holds simultaneously for all other confusion matrix quantities, which completes the proof.

D.5 Lower Bound Proof
Proof of Proposition 2. We need to find two distributions + and − that are sufficiently close. To this end, we use the canonical "bump" function We then define the recentered version where in this case we use 1 to denote the all ones vector (1, . . . , 1) and the constant is = 1/(2 + ) . Now, we define the regression functions. First, on ′ , we set + ( ′ ) = − ( ′ ) = 1. Next, we define the positive and negative regression functions on [0, 1] by where we recall that ‖ · ‖ Σ is the -Hölder semi-norm as defined in equation (17). The purpose of is to ensure the proper values of TN(1/2). Otherwise, > 0 is a small constant that satisfies Finally, we define the distribution + such that is uniformly distributed on [0, 1] with probability , takes the value ′ with probability 1 − , and the distribution of given is determined by the regression function + . Similarly, − is defined such that is uniformly distributed on [0, 1] with probability , takes the value ′ with probability 1 − , and the distribution of given is given by the regression function − . Now, we have two things to prove: (1) that both + and − are actually in Σ ( ) for some and (2) that any estimator must err with the specified probability one of these distributions. For (1), we follow the same argument as in the proof of Theorem 4. Specifically, we see that Thus, + is an element of Σ ( ), and one can show identically that − is an element of Σ ( ). So, we continue to step (2) Thus, it suffices to bound the Kullback-Leibler divergence between + and − . To do this, we make use of the elementary fact that for ≥ −2/3, we have − log(1 + ) ≤ 2 − . Then, we have Now, we need to determine the maximum error that is implied by this bound. Denote the maximum error by . We have = min  (27) and setting to be equal to the right hand side of equation (27), we obtain for constants and ′ . Thus, in summary, we have shown that with probability at least , we make an error of size at least /4 in estimating TN(1/2); has the form = P ( − ≤ ( ) ≤ + ); and may be of size at least Ω( − /(2 + ) ). This establishes the proposition.
If prec, ( ) ≥ 1, then since empirical precision is bounded by 1, the previous inequality is also true, which proves the upper bound.  Proof of Corollary 6. By Corollary 5, we see that F1 has probability at least 1− . Thus, Lemma 31 completes the proof.

F Additional Optimization Details
In this section, we provide additional details for optimization results of section 6. First, we provide the explicit algorithm for grid search in Algorithm 3. Second, we provide additional comparisons between the greedy algorithm and grid search in Figure 4. In particular, we examine the difference between the population F1 score for grid search and the greedy algorithm in Figure 4a. This shows that the difference is quite small. Second, we examine the ℓ 2 distance between the learned weights in Figure 4b as a function of . Although there is no clear pattern, the distance between the weights is small. (a) Absolute value of difference between F1( ( ) ) and F1( grids ) for different training sizes . This difference decreases as increases.

(b)
The ℓ 2 distance between ( ) and grids for different training sizes . This difference decreases as increases as well.