# Optimal Binary Classification Beyond Accuracy

arXiv: https://arxiv.org/abs/2107.01777 · HTML: https://mlsanity.com/paper/2107.01777/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 77 references that are in the map.
- First posted on arXiv 5 Jul 2021.

## Builds on (most cited first, 15 of 15)

- [BAGAN: Data Augmentation with Balancing GAN](https://mlsanity.com/paper/1803.09655/) (2018)
- [Two-Player Games for Efficient Non-Convex Constrained Optimization](https://mlsanity.com/paper/1804.06500/) (2018)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [Machine learning for protein folding and dynamics](https://mlsanity.com/paper/1911.09811/) (2019)
- [Local case-control sampling: Efficient subsampling in imbalanced data sets](https://mlsanity.com/paper/1306.3706/) (2013)
- [Binary Classification with Karmic, Threshold-Quasi-Concave Metrics](https://mlsanity.com/paper/1806.00640/) (2018)
- [Efficient Classification for Metric Data](https://mlsanity.com/paper/1306.2547/) (2013)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)
- [Logistic Regression for Massive Data with Rare Events](https://mlsanity.com/paper/2006.00683/) (2020)
- [On the robustness of randomized classifiers to adversarial examples](https://mlsanity.com/paper/2102.10875/) (2021)
- [AP-Perf: Incorporating Generic Performance Metrics in Differentiable Learning](https://mlsanity.com/paper/1912.00965/) (2019)
- [A Bayes consistent 1-NN classifier](https://mlsanity.com/paper/1407.0208/) (2014)
- [Consistent Classification with Generalized Metrics](https://mlsanity.com/paper/1908.09057/) (2019)

## Built on by (most cited first, 5 of 5)

- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [On Optimal Steering to Achieve Exact Fairness](https://mlsanity.com/paper/2509.15759/) (2025)
- [Robust performance metrics for imbalanced classification problems](https://mlsanity.com/paper/2404.07661/) (2024)
- [Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2508.14071/) (2025)

## Abstract (arXiv)

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