On the Consistency of AUC Pairwise Optimization

Abstract

AUC (Area Under ROC Curve) has been an important critrion widely used in diversity learning tasks. To optimize AUC, many learning approaches have been developed, most working with pairwise surrogate losses. Thus, it is important to study the AUC consistency based on minimizing pairwise surrogate losses. In this paper, we introduce the generalized calibration for AUC optimization, and prove that it is a necessary condition for AUC consistency. We then provide a new sufficient condition for AUC consistency, and show its usefulness in studying the consistency of various surrogate losses, as well as the invetion of new consistent losses. Further, we derive regret bounds for exponential and logistic losses, and present regret bounds for more general surrogate losses in realizable setting. Finally, we prove regret bounds that disclose the equivalence between the pairwise exponential loss of AUC and the univariate exponential loss of accuracy.