Abstract
Optimizing the Area Under the ROC Curve (AUC) is a critical task in binary classification, especially for imbalanced datasets. However, traditional AUC optimization relies on pairwise surrogate losses, leading to $O(N^2)$ computational complexity. This paper introduces a univariate reformulation of the AUC objective that reduces complexity to linear $O(N)$. By treating the classification threshold as a learnable auxiliary variable, the proposed Univariate Bound of AUC (UBAUC) enables efficient batch and online learning. Experimental results across 12 benchmark datasets demonstrate that UBAUC achieves state-of-the-art performance while being significantly faster and more memory-efficient than previous methods.
Introduction
In binary classification, accuracy often fails to capture model performance on imbalanced data. The Area Under the ROC Curve (AUC) is a preferred metric as it evaluates the probability that a randomly chosen positive instance is ranked higher than a randomly chosen negative instance. Despite its utility, direct AUC optimization is hindered by the non-differentiable nature of the ranking function and the "pairwise bottleneck"—the requirement to compare all pairs of positive and negative examples, resulting in quadratic complexity.
Methodology
The authors propose a univariate bound for AUC risk to bypass the pairwise comparison requirement. The core innovation lies in utilizing a mathematical identity for the sum of top-$k$ elements to reformulate the ranking problem into a minimization task involving an auxiliary variable, $\lambda$.
In this framework, $\lambda$ serves as a dynamic threshold. The loss function is designed to penalize positive examples falling below $\lambda$ and negative examples rising above it. This approach effectively decouples the pairwise relationships, allowing the model to process individual data points independently relative to the threshold. Consequently, the computational complexity is reduced to $O(N)$.
Algorithms
Two primary algorithms are introduced:
- ba-UBAUC (Batch): An offline training method utilizing block coordinate descent.
- ol-UBAUC (Online): A stochastic gradient descent (SGD) based approach designed for streaming data. Notably,
ol-UBAUCmaintains constant $O(1)$ space complexity, as it does not require a buffer to store past examples for pairwise comparisons.
Experimental Results
The UBAUC framework was evaluated on 12 standard benchmark datasets, ranging from small-scale (e.g., Diabetes, German) to large-scale, high-dimensional tasks (e.g., MNIST, Sector, News20).
Classification Performance
UBAUC consistently achieved AUC scores comparable to or exceeding current state-of-the-art methods, including SOLAM, OPAUC, and OAM. The results indicate that the univariate approximation serves as a highly effective surrogate for the true AUC.
Computational Efficiency
The transition from quadratic to linear complexity yields dramatic speedups. On high-dimensional datasets like sector, the online ol-UBAUC algorithm demonstrated convergence speeds significantly faster than traditional online AUC optimizers. Furthermore, the $O(1)$ space complexity makes it uniquely suited for large-scale streaming applications where memory is a constraint.
Discussion and Conclusion
The paper demonstrates that pairwise comparisons are not strictly necessary for optimizing ranking metrics. By introducing a learnable threshold, the UBAUC method captures the essential ranking information with linear complexity. The authors also establish a theoretical link to Support Vector Machines (SVMs), showing that the standard SVM objective is a looser upper bound of the proposed univariate loss.
While the empirical results are robust, future work remains to establish formal Fisher consistency and generalization error bounds for this univariate form. Additionally, extending this logic to multi-class AUC and non-convex models like deep neural networks presents a promising avenue for research.
Summary updated