Abstract
Area under the receiver operating characteristics curve (AUC) is an important metric for a wide range of signal processing and machine learning problems, and scalable methods for optimizing AUC have recently been proposed. However, handling very large datasets remains an open challenge for this problem. This paper proposes a novel approach to AUC maximization, based on sampling mini-batches of positive/negative instance pairs and computing U-statistics to approximate a global risk minimization problem. The resulting algorithm is simple, fast, and learning-rate free. We show that the number of samples required for good performance is independent of the number of pairs available, which is a quadratic function of the positive and negative instances. Extensive experiments show the practical utility of the proposed method.
Introduction
In many real-world scenarios—such as fraud detection, medical diagnosis, or ad-click prediction—datasets are heavily imbalanced. In these cases, standard accuracy is a deceptive metric; a model that predicts "no fraud" 99.9% of the time might be 99.9% accurate but entirely useless. The Area Under the ROC Curve (AUC) is the gold standard for these applications because it measures how well a model ranks positive instances above negative ones.
However, optimizing AUC is computationally expensive. Because it is defined over pairs of positive and negative samples, a dataset with $N$ samples can have up to $O(N^2)$ pairs. For "big data," this quadratic growth makes standard optimization intractable. Existing online methods attempt to solve this by processing one sample at a time, but they are often sensitive to learning rate selection and can suffer from slow convergence.
Methodology
The authors propose Mini-Batch AUC Optimization (MBA), a novel approach that combines convex relaxation with efficient mini-batch processing. The method relies on several key components:
- Surrogate Loss: The non-differentiable AUC indicator function is replaced with the Pairwise Squared Loss (PSL), transforming the problem into a convex optimization task.
- U-Statistics for Moment Estimation: Instead of using stochastic gradient descent (SGD), which requires careful tuning of a learning rate, MBA estimates the first and second moments (mean and covariance) of the differences between positive and negative samples. It utilizes U-statistics—a class of unbiased estimators—to build these global estimates from small, randomly sampled mini-batches.
- Global Optimization: Once the moments are estimated, the algorithm solves a global risk minimization problem using Elastic Net regularization (a combination of L1 and L2 penalties).
- Learning-Rate Free: Because MBA constructs a global approximation of the objective function rather than taking incremental steps based on local gradients, it does not require a learning rate parameter.
Experimental Evaluation
The authors evaluated MBA across three distinct environments:
- Simulated Data: Gaussian mixtures with varying components were used to test the algorithm against the theoretically optimal Neyman-Pearson detector.
- Benchmark Datasets: 15 datasets from the UCI and LIBSVM repositories, ranging from 500 to 60,000 samples, covering fields like biology, finance, and image recognition.
- Large-Scale Web Data: Three massive commercial datasets for click-through rate (CTR) prediction: Avazu (App & Site) and Criteo, the latter containing over 45 million samples.
Key Results
On the 15 benchmark datasets, MBA outperformed or tied with leading algorithms like AdaAUC and OAM in almost every case, particularly on highly imbalanced data. In simulated Gaussian mixture tests, MBA demonstrated rapid convergence toward the theoretical Neyman-Pearson limit as the sampling rate increased.
On the Criteo dataset (45.8M samples), MBA reached a solution in under an hour on a standard setup, performing roughly 10 times faster than sequential logistic regression implementations. Unlike SGD-based methods that fluctuate based on the learning rate, MBA showed steady performance gains as the sample size grew.
Key Insights and Discussion
A major theoretical contribution of this work is the proof that the number of samples required for MBA to reach a good solution is independent of the total number of pairs in the dataset. Instead, it depends primarily on the dimensionality of the features. While most AUC optimizers are "local" (nudging weights based on a few pairs), MBA is "global," using mini-batches to build a statistical map of the entire dataset's pairwise relationships.
Limitations
- Linear Assumption: The core efficiency gains are most evident in linear ranking functions. While nonlinear kernels can be used via feature mapping, they were not the primary focus.
- Memory Overhead: Storing the second-moment matrix requires $O(d^2)$ space, which could become a bottleneck for extremely high-dimensional data, though regularization helps mitigate this.
Conclusion
MBA provides a scalable, stable, and learning-rate free framework for AUC optimization. Its ability to process tens of millions of samples in under an hour while maintaining superior ranking performance makes it a powerful tool for modern large-scale imbalanced classification tasks.
Summary updated