Stochastic Proximal AUC Maximization

Abstract

In this paper we consider the problem of maximizing the Area under the ROC curve (AUC) which is a widely used performance metric in imbalanced classification and anomaly detection. Due to the pairwise nonlinearity of the objective function, classical SGD algorithms do not apply to the task of AUC maximization. We propose a novel stochastic proximal algorithm for AUC maximization which is scalable to large scale streaming data. Our algorithm can accommodate general penalty terms and is easy to implement with favorable $O(d)$ space and per-iteration time complexities. We establish a high-probability convergence rate $O(1/\sqrt{T})$ for the general convex setting, and improve it to a fast convergence rate $O(1/T)$ for the cases of strongly convex regularizers and no regularization term (without strong convexity). Our proof does not need the uniform boundedness assumption on the loss function or the iterates which is more fidelity to the practice. Finally, we perform extensive experiments over various benchmark data sets from real-world application domains which show the superior performance of our algorithm over the existing AUC maximization algorithms.

References in corpus (7)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Smoothing Multivariate Performance Measures
• On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
• Stochastic Optimization for Machine Learning
• Accelerating Stochastic Composition Optimization

Cited by in corpus (1)

• Stochastic Hard Thresholding Algorithms for AUC Maximization