  Area under ROC (AUC) is an important metric for binary classification and
bipartite ranking problems. However, it is difficult to directly optimizing AUC
as a learning objective, so most existing algorithms are based on optimizing 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 increasing local storage for online learning. In this work, we
describe a new surrogate loss based on a reformulation of the AUC risk, which
does not require pairwise comparison but rankings of the predictions. We
further show that the ranking operation can be avoided, and the learning
objective obtained based on this surrogate enjoys linear complexity in time and
storage. We perform experiments to demonstrate the effectiveness of the online
and batch algorithms for AUC optimization based on the proposed surrogate loss.
