# Momentum Accelerates the Convergence of Stochastic AUPRC Maximization arXiv: https://arxiv.org/abs/2107.01173 · HTML: https://mlsanity.com/paper/2107.01173/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 57 references that are in the map. - First posted on arXiv 2 Jul 2021. ## Builds on (most cited first, 27 of 27) - [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015) - [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014) - [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019) - [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019) - [Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval](https://mlsanity.com/paper/2007.12163/) (2020) - [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014) - [Optimizing Rank-based Metrics with Blackbox Differentiation](https://mlsanity.com/paper/1912.03500/) (2019) - [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018) - [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020) - [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020) - [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016) - [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013) - [Scalable Learning of Non-Decomposable Objectives](https://mlsanity.com/paper/1608.04802/) (2016) - [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016) - [Towards Accurate One-Stage Object Detection with AP-Loss](https://mlsanity.com/paper/1904.06373/) (2019) - [End-to-end training of object class detectors for mean average precision](https://mlsanity.com/paper/1607.03476/) (2016) - [Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/2005.02426/) (2020) - [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019) - [Training Deep Neural Networks via Direct Loss Minimization](https://mlsanity.com/paper/1511.06411/) (2015) - [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020) - [A Ranking-based, Balanced Loss Function Unifying Classification and Localisation in Object Detection](https://mlsanity.com/paper/2009.13592/) (2020) - [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018) - [Efficient Optimization for Rank-based Loss Functions](https://mlsanity.com/paper/1604.08269/) (2016) - [Finite-sum Composition Optimization via Variance Reduced Gradient Descent](https://mlsanity.com/paper/1610.04674/) (2016) - [Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization](https://mlsanity.com/paper/1711.03937/) (2017) - [Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient](https://mlsanity.com/paper/1806.00458/) (2018) - [Duality-free Methods for Stochastic Composition Optimization](https://mlsanity.com/paper/1710.09554/) (2017) ## Built on by (most cited first, 14 of 14) - [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022) - [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022) - [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023) - [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022) - [Benchmarking Deep AUROC Optimization: Loss Functions and Algorithmic Choices](https://mlsanity.com/paper/2203.14177/) (2022) - [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022) - [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022) - [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022) - [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023) - [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022) - [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023) - [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023) - [Fairness via Adversarial Attribute Neighbourhood Robust Learning](https://mlsanity.com/paper/2210.06630/) (2022) - [ADMM for Structured Fractional Minimization](https://mlsanity.com/paper/2411.07496/) (2024) ## Abstract (arXiv) In this paper, we study stochastic optimization of areas under precision-recall curves (AUPRC), which is widely used for combating imbalanced classification tasks. Although a few methods have been proposed for maximizing AUPRC, stochastic optimization of AUPRC with convergence guarantee remains an undeveloped territory. A state-of-the-art complexity is O(1/ε5) for finding an ε-stationary solution. In this paper, we further improve the stochastic optimization of AURPC by (i) developing novel stochastic momentum methods with a better iteration complexity of O(1/ε4) for finding an ε-stationary solution; and (ii) designing a novel family of stochastic adaptive methods with the same iteration complexity, which enjoy faster convergence in practice. To this end, we propose two innovative techniques that are critical for improving the convergence: (i) the biased estimators for tracking individual ranking scores are updated in a randomized coordinate-wise manner; and (ii) a momentum update is used on top of the stochastic gradient estimator for tracking the gradient of the objective. The novel analysis of Adam-style updates is also one main contribution. Extensive experiments on various data sets demonstrate the effectiveness of the proposed algorithms. Of independent interest, the proposed stochastic momentum and adaptive algorithms are also applicable to a class of two-level stochastic dependent compositional optimization problems.