mlsanityData to 7 Oct 2026

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

arXiv 2209.13262 ↗First posted 27 Sep 2022cs.LG cs.CVcited by 8

Not on the map. Why?

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.

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

Builds on

39 of 87 references.

References · 39

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2014ImageNet Large Scale Visual Recognition Challengecited by 8,441
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  6. 2015Deep Metric Learning via Lifted Structured Feature Embeddingcited by 449
  7. 2014Deep metric learning using Triplet networkcited by 421
  8. 2019Multi-Similarity Loss with General Pair Weighting for Deep Metric Learningcited by 368
  9. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  10. 2019Differentiation of Blackbox Combinatorial Solverscited by 224
  11. 2019Learning with Average Precision: Training Image Retrieval with a Listwise Losscited by 184
  12. 2019Cross-Batch Memory for Embedding Learningcited by 130
27 more
  1. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  2. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  3. 2020Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrievalcited by 98
  4. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  5. 2017On Sampling Strategies for Neural Network-based Collaborative Filteringcited by 71
  6. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  7. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  8. 2016Learning Deep Embeddings with Histogram Losscited by 52
  9. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  10. 2019Towards Accurate One-Stage Object Detection with AP-Losscited by 36
  11. 2016End-to-end training of object class detectors for mean average precisioncited by 35
  12. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  13. 2021Learning with Multiclass AUC: Theory and Algorithmscited by 35
  14. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  15. 2019SoDeep: a Sorting Deep net to learn ranking loss surrogatescited by 28
  16. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  17. 2015Training Deep Neural Networks via Direct Loss Minimizationcited by 25
  18. 2020A Ranking-based, Balanced Loss Function Unifying Classification and Localisation in Object Detectioncited by 25
  19. 2020AP-Loss for Accurate One-Stage Object Detectioncited by 24
  20. 2019Hypothesis Set Stability and Generalizationcited by 23
  21. 2017Hashing as Tie-Aware Learning to Rankcited by 18
  22. 2016Efficient Optimization for Rank-based Loss Functionscited by 15
  23. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  24. 2022Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Samplingcited by 14
  25. 2019Improving Collaborative Metric Learning with Efficient Negative Samplingcited by 11
  26. 2020Optimizing Black-box Metrics with Adaptive Surrogatescited by 7
  27. 2021Rethinking the Optimization of Average Precision: Only Penalizing Negative Instances before Positive Ones is Enoughcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 3; 2025: 3.

8 papers.

  1. 2024Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrievalcited by 9
  2. 2023DRAUC: An Instance-wise Distributionally Robust AUC Optimization Frameworkcited by 3
  3. 2025Semantic Concentration for Self-Supervised Dense Representations Learningcited by 3
  4. 2025Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classificationcited by 2
  5. 2024U-Trustworthy Models.Reliability, Competence, and Confidence in Decision-Makingcited by 1
  6. 2024Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classificationcited by 1
  7. 2025Enhancing Sample Utilization in Noise-Robust Deep Metric Learning With Subgroup-Based Positive-Pair Selectioncited by 1
  8. 2023When Measures are Unreliable: Imperceptible Adversarial Perturbations toward Top-k Multi-Label Learningcited by 0