# Online AUC Optimization for Sparse High-Dimensional Datasets

arXiv: https://arxiv.org/abs/2009.10867 · HTML: https://mlsanity.com/paper/2009.10867/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2020.

## Built on by (most cited first, 3 of 3)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling](https://mlsanity.com/paper/2206.11549/) (2022)
- [Online AUC Optimization Based on Second-order Surrogate Loss](https://mlsanity.com/paper/2510.21202/) (2025)

## Abstract (arXiv)

The Area Under the ROC Curve (AUC) is a widely used performance measure for imbalanced classification arising from many application domains where high-dimensional sparse data is abundant. In such cases, each d dimensional sample has only k non-zero features with k ll d, and data arrives sequentially in a streaming form. Current online AUC optimization algorithms have high per-iteration cost O(d) and usually produce non-sparse solutions in general, and hence are not suitable for handling the data challenge mentioned above. In this paper, we aim to directly optimize the AUC score for high-dimensional sparse datasets under online learning setting and propose a new algorithm, textscFTRL-AUC. Our proposed algorithm can process data in an online fashion with a much cheaper per-iteration cost O(k), making it amenable for high-dimensional sparse streaming data analysis. Our new algorithmic design critically depends on a novel reformulation of the U-statistics AUC objective function as the empirical saddle point reformulation, and the innovative introduction of the "lazy update" rule so that the per-iteration complexity is dramatically reduced from O(d) to O(k). Furthermore, textscFTRL-AUC can inherently capture sparsity more effectively by applying a generalized Follow-The-Regularized-Leader (FTRL) framework. Experiments on real-world datasets demonstrate that textscFTRL-AUC significantly improves both run time and model sparsity while achieving competitive AUC scores compared with the state-of-the-art methods. Comparison with the online learning method for logistic loss demonstrates that textscFTRL-AUC achieves higher AUC scores especially when datasets are imbalanced.