A Univariate Bound of Area Under ROC

Siwei Lyu

Abstract

Area under ROC (AUC) is an important metric for binary classification and bipartite ranking problems. However, it is difficult to directly optimize 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.

Introduction

In binary classification tasks, particularly those involving highly imbalanced datasets, the Area Under the ROC Curve (AUC) is a more robust performance metric than standard accuracy. Despite its utility, direct optimization of AUC is computationally challenging. The standard AUC definition relies on an indicator function that counts correctly ranked pairs of positive and negative examples. This leads to two primary issues: the discontinuity of the indicator function makes it NP-hard to minimize, and the pairwise nature of the calculation results in $O(N^2)$ complexity for $N$ samples.

For online learning scenarios, where data is processed sequentially, this quadratic complexity necessitates storing all previous examples to compare against new arrivals—a requirement that is infeasible for large-scale streaming data. This paper introduces a "univariate" surrogate loss that transforms the pairwise comparison problem into a linear optimization task, achieving constant memory requirements and linear time complexity.

Methodology: The UBAUC Framework

The proposed method, Univariate Bound of AUC (UBAUC), circumvents the pairwise bottleneck through a mathematical reformulation of the ranking problem.

From Pairs to Ranks

The authors first demonstrate that the AUC risk can be expressed in terms of the ranks of prediction scores rather than explicit pairwise comparisons. While ranking itself still introduces complexity, it provides a pathway to a more efficient surrogate.

The Sum-of-Top-K Optimization

To avoid explicit ranking operations, the authors utilize an optimization identity where the sum of the $k$ largest elements in a set is equivalent to a minimization problem involving an auxiliary variable, $\lambda$. By applying this "Sum-of-Top-K" trick, the pairwise AUC surrogate is transformed into a univariate loss function. In this new form, each data point is evaluated against a single global threshold ($\lambda$) that acts as a learned separator between classes.

Optimization Algorithms

Two variants of the algorithm were developed:

  • ba-UBAUC: A batch processing version utilizing block coordinate descent.
  • ol-UBAUC: An online learning version using stochastic sub-gradient descent.

A key theoretical insight is the connection to Support Vector Machines (SVMs). The authors prove that the standard SVM objective serves as a loose upper bound for the UBAUC loss, explaining the historical effectiveness of SVMs on AUC-related tasks.

Experimental Evaluation

The UBAUC framework was tested against state-of-the-art pairwise methods (e.g., SOLAM, OPAUC) across 12 benchmark datasets. These ranged from small datasets like Diabetes and USPS to massive, high-dimensional sets such as Sector and News20.

Accuracy and Performance

The experimental results demonstrate that UBAUC maintains competitive accuracy while offering significant computational advantages.

Table 1: Comparison of AUC performance across various datasets and algorithms. UBAUC variants achieve results comparable to or better than traditional pairwise methods.

As shown in the performance table, UBAUC variants consistently match the AUC scores of leading pairwise methods like OPAUC and SOLAM. On the USPS dataset, for instance, ol-UBAUC achieved an AUC of 0.9728, nearly identical to ba-UBAUC (0.9730) and slightly better than OPAUC (0.9620).

Computational Efficiency

The most dramatic improvements were observed in training time and memory usage, particularly on large-scale datasets.

Table 2: Running time (in seconds) comparison on large-scale datasets. UBAUC demonstrates massive speedups over pairwise alternatives.

On the Sector dataset, ol-UBAUC converged in approximately 276 seconds, whereas OPAUC required over 5,540 seconds—a nearly 20x speedup. Furthermore, on high-dimensional datasets like News20, traditional batch pairwise methods often failed due to memory constraints, while the univariate approach remained efficient.

Conclusion

The UBAUC framework represents a significant step forward in AUC optimization. By breaking the pairwise paradigm, it enables the training of AUC-sensitive models on massive datasets that were previously computationally prohibitive. Future work will focus on proving the theoretical consistency of the surrogate loss and extending the univariate approach to multi-class classification and deep learning architectures.

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},
  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