# Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 8 Oct 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Large-scale Robust Deep AUC Maximization: A New Surrogate Loss and Empirical Studies on Medical Image Classification](https://mlsanity.com/paper/2012.03173/) (2020)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [Learning with Average Top-k Loss](https://mlsanity.com/paper/1705.08826/) (2017)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/2005.02426/) (2020)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Support Vector Algorithms for Optimizing the Partial Area Under the ROC Curve](https://mlsanity.com/paper/1605.04337/) (2016)
- [Two-Way Partial AUC and Its Properties](https://mlsanity.com/paper/1508.00298/) (2015)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods](https://mlsanity.com/paper/2110.11210/) (2021)

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

- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation](https://mlsanity.com/paper/2403.00844/) (2024)
- [Improved Diversity-Promoting Collaborative Metric Learning for Recommendation](https://mlsanity.com/paper/2409.01012/) (2024)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)

## Abstract (arXiv)

The Partial Area Under the ROC Curve (PAUC), typically including One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC), measures the average performance of a binary classifier within a specific false positive rate and/or true positive rate interval, which is a widely adopted measure when decision constraints must be considered. Consequently, PAUC optimization has naturally attracted increasing attention in the machine learning community within the last few years. Nonetheless, most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. Fortunately, a recent work presents an unbiased formulation of the PAUC optimization problem via distributional robust optimization. However, it is based on the pair-wise formulation of AUC, which suffers from the limited scalability w.r.t. sample size and a slow convergence rate, especially for TPAUC. To address this issue, we present a simpler reformulation of the problem in an asymptotically unbiased and instance-wise manner. For both OPAUC and TPAUC, we come to a nonconvex strongly concave minimax regularized problem of instance-wise functions. On top of this, we employ an efficient solver enjoys a linear per-iteration computational complexity w.r.t. the sample size and a time-complexity of O(ε-1/3) to reach a ε stationary point. Furthermore, we find that the minimax reformulation also facilitates the theoretical analysis of generalization error as a byproduct. Compared with the existing results, we present new error bounds that are much easier to prove and could deal with hypotheses with real-valued outputs. Finally, extensive experiments on several benchmark datasets demonstrate the effectiveness of our method.