# Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 87 references that are in the map.
- First posted on arXiv 27 Sep 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [Deep metric learning using Triplet network](https://mlsanity.com/paper/1412.6622/) (2014)
- [Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning](https://mlsanity.com/paper/1904.06627/) (2019)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Learning with Average Precision: Training Image Retrieval with a Listwise Loss](https://mlsanity.com/paper/1906.07589/) (2019)
- [Cross-Batch Memory for Embedding Learning](https://mlsanity.com/paper/1912.06798/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval](https://mlsanity.com/paper/2007.12163/) (2020)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [On Sampling Strategies for Neural Network-based Collaborative Filtering](https://mlsanity.com/paper/1706.07881/) (2017)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Learning Deep Embeddings with Histogram Loss](https://mlsanity.com/paper/1611.00822/) (2016)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Towards Accurate One-Stage Object Detection with AP-Loss](https://mlsanity.com/paper/1904.06373/) (2019)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [End-to-end training of object class detectors for mean average precision](https://mlsanity.com/paper/1607.03476/) (2016)
- [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)
- [SoDeep: a Sorting Deep net to learn ranking loss surrogates](https://mlsanity.com/paper/1904.04272/) (2019)
- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [Training Deep Neural Networks via Direct Loss Minimization](https://mlsanity.com/paper/1511.06411/) (2015)
- [A Ranking-based, Balanced Loss Function Unifying Classification and Localisation in Object Detection](https://mlsanity.com/paper/2009.13592/) (2020)

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

- [Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval](https://mlsanity.com/paper/2407.15566/) (2024)
- [DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework](https://mlsanity.com/paper/2311.03055/) (2023)
- [Semantic Concentration for Self-Supervised Dense Representations Learning](https://mlsanity.com/paper/2509.09429/) (2025)
- [Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification](https://mlsanity.com/paper/2507.15240/) (2025)
- [U-Trustworthy Models.Reliability, Competence, and Confidence in Decision-Making](https://mlsanity.com/paper/2401.02062/) (2024)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [Enhancing Sample Utilization in Noise-Robust Deep Metric Learning With Subgroup-Based Positive-Pair Selection](https://mlsanity.com/paper/2501.11063/) (2025)
- [When Measures are Unreliable: Imperceptible Adversarial Perturbations toward Top-k Multi-Label Learning](https://mlsanity.com/paper/2309.00007/) (2023)

## Abstract (arXiv)

Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. Although various algorithms have been extensively studied for AUPRC optimization, the generalization is only guaranteed in the multi-query case. In this work, we present the first trial in the single-query generalization of stochastic AUPRC optimization. For sharper generalization bounds, we focus on algorithm-dependent generalization. There are both algorithmic and theoretical obstacles to our destination. From an algorithmic perspective, we notice that the majority of existing stochastic estimators are biased only when the sampling strategy is biased, and is leave-one-out unstable due to the non-decomposability. To address these issues, we propose a sampling-rate-invariant unbiased stochastic estimator with superior stability. On top of this, the AUPRC optimization is formulated as a composition optimization problem, and a stochastic algorithm is proposed to solve this problem. From a theoretical perspective, standard techniques of the algorithm-dependent generalization analysis cannot be directly applied to such a listwise compositional optimization problem. To fill this gap, we extend the model stability from instancewise losses to listwise losses and bridge the corresponding generalization and stability. Additionally, we construct state transition matrices to describe the recurrence of the stability, and simplify calculations by matrix spectrum. Practically, experimental results on three image retrieval datasets on speak to the effectiveness and soundness of our framework.