# Does it pay to optimize AUC?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 71 references that are in the map.
- First posted on arXiv 2 Jun 2023.

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

- [Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning](https://mlsanity.com/paper/1609.06570/) (2016)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Scalable Learning of Non-Decomposable Objectives](https://mlsanity.com/paper/1608.04802/) (2016)
- [The Fairness of Risk Scores Beyond Classification: Bipartite Ranking and the xAUC Metric](https://mlsanity.com/paper/1902.05826/) (2019)
- [To tune or not to tune the number of trees in random forest?](https://mlsanity.com/paper/1705.05654/) (2017)
- [Stochastic Proximal AUC Maximization](https://mlsanity.com/paper/1906.06053/) (2019)
- [MBA: Mini-Batch AUC Optimization](https://mlsanity.com/paper/1805.11221/) (2018)
- [Direct Learning to Rank and Rerank](https://mlsanity.com/paper/1802.07400/) (2018)

## Abstract (arXiv)

The Area Under the ROC Curve (AUC) is an important model metric for evaluating binary classifiers, and many algorithms have been proposed to optimize AUC approximately. It raises the question of whether the generally insignificant gains observed by previous studies are due to inherent limitations of the metric or the inadequate quality of optimization. To better understand the value of optimizing for AUC, we present an efficient algorithm, namely AUC-opt, to find the provably optimal AUC linear classifier in ℝ2, which runs in O(n_+ n_- log (n_+ n_-)) where n_+ and n_- are the number of positive and negative samples respectively. Furthermore, it can be naturally extended to ℝd in O((n_+n_-)d-1log (n_+n_-)) by calling AUC-opt in lower-dimensional spaces recursively. We prove the problem is NP-complete when d is not fixed, reducing from the textitopen hemisphere problem. Experiments show that compared with other methods, AUC-opt achieves statistically significant improvements on between 17 to 40 in ℝ2 and between 4 to 42 in ℝ3 of 50 t-SNE training datasets. However, generally the gain proves insignificant on most testing datasets compared to the best standard classifiers. Similar observations are found for nonlinear AUC methods under real-world datasets.