# Online AUC Optimization Based on Second-order Surrogate Loss

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 54 references that are in the map.
- First posted on arXiv 24 Oct 2025.

## Builds on (most cited first, 11 of 11)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [A Generalized Online Mirror Descent with Applications to Classification and Regression](https://mlsanity.com/paper/1304.2994/) (2013)
- [Stochastic Proximal AUC Maximization](https://mlsanity.com/paper/1906.06053/) (2019)
- [Weakly Supervised AUC Optimization: A Unified Partial AUC Approach](https://mlsanity.com/paper/2305.14258/) (2023)
- [Learning with Smooth Hinge Losses](https://mlsanity.com/paper/2103.00233/) (2021)
- [Federated Compositional Deep AUC Maximization](https://mlsanity.com/paper/2304.10101/) (2023)
- [A Univariate Bound of Area Under ROC](https://mlsanity.com/paper/1804.05981/) (2018)
- [A Minimax Probability Machine for Non-Decomposable Performance Measures](https://mlsanity.com/paper/2103.00396/) (2021)
- [Online AUC Optimization for Sparse High-Dimensional Datasets](https://mlsanity.com/paper/2009.10867/) (2020)

## Abstract (arXiv)

The Area Under the Curve (AUC) is an important performance metric for classification tasks, particularly in class-imbalanced scenarios. However, minimizing the AUC presents significant challenges due to the non-convex and discontinuous nature of pairwise 0/1 losses, which are difficult to optimize, as well as the substantial memory cost of instance-wise storage, which creates bottlenecks in large-scale applications. To overcome these challenges, we propose a novel second-order surrogate loss based on the pairwise hinge loss, and develop an efficient online algorithm. Unlike conventional approaches that approximate each individual pairwise 0/1 loss term with an instance-wise surrogate function, our approach introduces a new paradigm that directly substitutes the entire aggregated pairwise loss with a surrogate loss function constructed from the first- and second-order statistics of the training data. Theoretically, while existing online AUC optimization algorithms typically achieve an O(√T) regret bound, our method attains a tighter O(ln T) bound. Furthermore, we extend the proposed framework to nonlinear settings through a kernel-based formulation. Extensive experiments on multiple benchmark datasets demonstrate the superior efficiency and effectiveness of the proposed second-order surrogate loss in optimizing online AUC performance.