# Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 39 references that are in the map.
- First posted on arXiv 28 May 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity](https://mlsanity.com/paper/2102.04635/) (2021)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Two-Way Partial AUC and Its Properties](https://mlsanity.com/paper/1508.00298/) (2015)
- [Weakly Supervised AUC Optimization: A Unified Partial AUC Approach](https://mlsanity.com/paper/2305.14258/) (2023)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Federated Compositional Deep AUC Maximization](https://mlsanity.com/paper/2304.10101/) (2023)
- [Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization](https://mlsanity.com/paper/2004.04357/) (2020)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)
- [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Randomized Primal-Dual Methods with Adaptive Step Sizes](https://mlsanity.com/paper/1806.04118/) (2018)

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

- [Partial AUC Maximization from Positive-unlabeled Data](https://mlsanity.com/paper/2610.00284/) (2026)

## Abstract (arXiv)

Two-way partial AUC (TPAUC) is a critical performance metric for binary classification with imbalanced data, as it focuses on specific ranges of the true positive rate (TPR) and false positive rate (FPR). However, stochastic algorithms for TPAUC optimization remain under-explored, with existing methods either limited to approximated TPAUC loss functions or burdened by sub-optimal complexities. To overcome these limitations, we introduce two innovative stochastic primal-dual double block-coordinate algorithms for TPAUC maximization. These algorithms utilize stochastic block-coordinate updates for both the primal and dual variables, catering to both convex and non-convex settings. We provide theoretical convergence rate analyses, demonstrating significant improvements over prior approaches. Our experimental results, based on multiple benchmark datasets, validate the superior performance of our algorithms, showcasing faster convergence and better generalization. This work advances the state of the art in TPAUC optimization and offers practical tools for real-world machine learning applications.