  AUC (area under ROC curve) is an important evaluation criterion, which has
been popularly used in many learning tasks such as class-imbalance learning,
cost-sensitive learning, learning to rank, etc. Many learning approaches try to
optimize AUC, while owing to the non-convexity and discontinuousness of AUC,
almost all approaches work with surrogate loss functions. Thus, the consistency
of AUC is crucial; however, it has been almost untouched before. In this paper,
we provide a sufficient condition for the asymptotic consistency of learning
approaches based on surrogate loss functions. Based on this result, we prove
that exponential loss and logistic loss are consistent with AUC, but hinge loss
is inconsistent. Then, we derive the $q$-norm hinge loss and general hinge loss
that are consistent with AUC. We also derive the consistent bounds for
exponential loss and logistic loss, and obtain the consistent bounds for many
surrogate loss functions under the non-noise setting. Further, we disclose an
equivalence between the exponential surrogate loss of AUC and exponential
surrogate loss of accuracy, and one straightforward consequence of such finding
is that AdaBoost and RankBoost are equivalent.
