A Univariate Bound of Area Under ROC

Siwei Lyu, Yiming Ying

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:

  1. ba-UBAUC (Batch): An offline training method utilizing block coordinate descent.
  2. ol-UBAUC (Online): A stochastic gradient descent (SGD) based approach designed for streaming data. Notably, ol-UBAUC maintains 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.

AUC performance comparison across 12 benchmark datasets.

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.

Training time (seconds) comparison highlighting the efficiency of UBAUC methods on selected datasets.

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

Abstract

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.
BibTeX
@inproceedings{lyu2018univariate,
  author = {Siwei Lyu and Yiming Ying},
  title = {{A Univariate Bound of Area Under ROC}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=lZafoqjsWb},
}
Figure