A Univariate Bound of Area Under ROC

Siwei Lyu, Yiming Ying
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:42-51, 2018.

Abstract

Area under ROC (AUC) is an important met- ric for binary classification and bipartite rank- ing problems. However, it is difficult to di- rectly optimize AUC as a learning objective, so most existing algorithms are based on optimiz- ing a surrogate loss to AUC. One significant drawback of these surrogate losses is that they require pairwise comparisons among training data, which leads to slow running time and in- creasing local storage for online learning. In this work, we describe a new surrogate loss based on a reformulation of AUC risk, which does not require pairwise comparison but rank- ings of the predictions. We further show that the ranking operation can be avoided, and the learning objective obtained based on this sur- rogate enjoys linear complexity in time and storage. We perform experiments to demon- strate the effectiveness of the online and batch algorithms for AUC optimization based on the proposed surrogate loss.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-lyu18a, title = {A Univariate Bound of Area Under {ROC}}, author = {Lyu, Siwei and Ying, Yiming}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {42--51}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/lyu18a/lyu18a.pdf}, url = {https://proceedings.mlr.press/r16/lyu18a.html}, abstract = {Area under ROC (AUC) is an important met- ric for binary classification and bipartite rank- ing problems. However, it is difficult to di- rectly optimize AUC as a learning objective, so most existing algorithms are based on optimiz- ing a surrogate loss to AUC. One significant drawback of these surrogate losses is that they require pairwise comparisons among training data, which leads to slow running time and in- creasing local storage for online learning. In this work, we describe a new surrogate loss based on a reformulation of AUC risk, which does not require pairwise comparison but rank- ings of the predictions. We further show that the ranking operation can be avoided, and the learning objective obtained based on this sur- rogate enjoys linear complexity in time and storage. We perform experiments to demon- strate the effectiveness of the online and batch algorithms for AUC optimization based on the proposed surrogate loss.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Univariate Bound of Area Under ROC %A Siwei Lyu %A Yiming Ying %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-lyu18a %I PMLR %P 42--51 %U https://proceedings.mlr.press/r16/lyu18a.html %V R16 %X Area under ROC (AUC) is an important met- ric for binary classification and bipartite rank- ing problems. However, it is difficult to di- rectly optimize AUC as a learning objective, so most existing algorithms are based on optimiz- ing a surrogate loss to AUC. One significant drawback of these surrogate losses is that they require pairwise comparisons among training data, which leads to slow running time and in- creasing local storage for online learning. In this work, we describe a new surrogate loss based on a reformulation of AUC risk, which does not require pairwise comparison but rank- ings of the predictions. We further show that the ranking operation can be avoided, and the learning objective obtained based on this sur- rogate enjoys linear complexity in time and storage. We perform experiments to demon- strate the effectiveness of the online and batch algorithms for AUC optimization based on the proposed surrogate loss. %Z Reissued by PMLR on 04 October 2026.
APA
Lyu, S. & Ying, Y.. (2018). A Univariate Bound of Area Under ROC. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:42-51 Available from https://proceedings.mlr.press/r16/lyu18a.html. Reissued by PMLR on 04 October 2026.

Related Material