# Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 39 of its 94 references that are in the map.
- First posted on arXiv 1 Dec 2025.

## Builds on (most cited first, 30 of 39)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Causal Intervention for Weakly-Supervised Semantic Segmentation](https://mlsanity.com/paper/2009.12547/) (2020)
- [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)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [Learning with Average Top-k Loss](https://mlsanity.com/paper/1705.08826/) (2017)
- [ProposalCLIP: Unsupervised Open-Category Object Proposal Generation via Exploiting CLIP Cues](https://mlsanity.com/paper/2201.06696/) (2022)
- [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)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [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)
- [SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2205.15084/) (2022)
- [Linear Attention Modeling for Learned Image Compression](https://mlsanity.com/paper/2502.05741/) (2025)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [A Dynamic Kernel Prior Model for Unsupervised Blind Image Super-Resolution](https://mlsanity.com/paper/2404.15620/) (2024)
- [Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling](https://mlsanity.com/paper/2206.11549/) (2022)
- [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)
- [Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization](https://mlsanity.com/paper/2206.00260/) (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)
- [Local Rademacher Complexity Bounds based on Covering Numbers](https://mlsanity.com/paper/1510.01463/) (2015)
- [Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization](https://mlsanity.com/paper/2009.04899/) (2020)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)

## Abstract (arXiv)

As a variant of the Area Under the ROC Curve (AUC), the partial AUC (PAUC) focuses on a specific range of false positive rate (FPR) and/or true positive rate (TPR) in the ROC curve. It is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints. However, selecting instances within these constrained intervals during its calculation is NP-hard, and thus typically requires approximation techniques for practical resolution. Despite the progress made in PAUC optimization over the last few years, most existing methods still suffer from uncontrollable approximation errors or a limited scalability when optimizing the approximate PAUC objectives. In this paper, we close the approximation gap of PAUC optimization by presenting two simple instance-wise minimax reformulations: one with an asymptotically vanishing gap, the other with the unbiasedness at the cost of more variables. Our key idea is to first establish an equivalent instance-wise problem to lower the time complexity, simplify the complicated sample selection procedure by threshold learning, and then apply different smoothing techniques. Equipped with an efficient solver, the resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of O(ε-1/3) for typical one-way and two-way PAUCs. Moreover, we provide a tight generalization bound of our minimax reformulations. The result explicitly demonstrates the impact of the TPR/FPR constraints α/β on the generalization and exhibits a sharp order of tildeO(α-1n_+-1 + β-1n_--1). Finally, extensive experiments on several benchmark datasets validate the strength of our proposed methods.