# One-Pass AUC Optimization

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2013.

## Built on by (most cited first, 30 of 42)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Embedding in Recommender Systems: A Survey](https://mlsanity.com/paper/2310.18608/) (2023)
- [Constrained Optimization to Train Neural Networks on Critical and Under-Represented Classes](https://mlsanity.com/paper/2102.12894/) (2021)
- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Minimax AUC Fairness: Efficient Algorithm with Provable Convergence](https://mlsanity.com/paper/2208.10451/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling](https://mlsanity.com/paper/2206.11549/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [ORFit: One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares](https://mlsanity.com/paper/2207.13853/) (2022)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Weakly Supervised AUC Optimization: A Unified Partial AUC Approach](https://mlsanity.com/paper/2305.14258/) (2023)
- [Benchmarking Deep AUROC Optimization: Loss Functions and Algorithmic Choices](https://mlsanity.com/paper/2203.14177/) (2022)
- [Optimizing Partial Area Under the Top-k Curve: Theory and Practice](https://mlsanity.com/paper/2209.01398/) (2022)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [AUC Maximization for Low-Resource Named Entity Recognition](https://mlsanity.com/paper/2212.04800/) (2022)
- [AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems](https://mlsanity.com/paper/2206.12169/) (2022)
- [Provable Multi-instance Deep AUC Maximization with Stochastic Pooling](https://mlsanity.com/paper/2305.08040/) (2023)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Pairwise Learning via Stagewise Training in Proximal Setting](https://mlsanity.com/paper/2208.04075/) (2022)
- [Enhancing Personalized Ranking With Differentiable Group AUC Optimization](https://mlsanity.com/paper/2304.09176/) (2023)
- [Low-Resource Named Entity Recognition: Can One-vs-All AUC Maximization Help?](https://mlsanity.com/paper/2311.04918/) (2023)
- [Evolutionary Multitasking AUC Optimization](https://mlsanity.com/paper/2201.01145/) (2022)

## Abstract (arXiv)

AUC is an important performance measure and many algorithms have been devoted to AUC optimization, mostly by minimizing a surrogate convex loss on a training data set. In this work, we focus on one-pass AUC optimization that requires only going through the training data once without storing the entire training dataset, where conventional online learning algorithms cannot be applied directly because AUC is measured by a sum of losses defined over pairs of instances from different classes. We develop a regression-based algorithm which only needs to maintain the first and second order statistics of training data in memory, resulting a storage requirement independent from the size of training data. To efficiently handle high dimensional data, we develop a randomized algorithm that approximates the covariance matrices by low rank matrices. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.