Abstract

In this paper, we consider statistical learning w AUC (area under ROC curve) maximization in the classical stochastic setting where one random data drawn from an unknown distribution is revealed at each iteration for updating the model. Although consistent convex surrogate losses for AUC maximization have been proposed to make the problem tractable, it remains an challenging problem to design fast optimization algorithms in the classical stochastic setting since the convex surrogate loss depends on random pairs of examples from positive and negative classes. Building on a saddle point formulation for a consisten square loss, this paper proposes a novel stochas- tic algorithm to improve the standard convergence rate to e convergence rat without strong convexity assumption or any favorable statistical assumptions (e.g., low noise) where n is the number of random samples. To the best of our knowledge, this is the first stochastic algorithm for AUC maximization with a statistical convergence rate as fast as O(1/n) up to a logarithmic factor. Extensive experiments on eight large-scale benchmark data sets demonstrate the superior performance of the proposed algorithm comparing with existing stochastic or online algorithms for AUC maximization.