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/\epsilon^5)$ for
finding an $\epsilon$-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/\epsilon^4)$ for
finding an $\epsilon$-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.

本文研究随机优化下精度 - 召回曲线（AUPRC）的最优化问题，通过开发随机动量方法和随机自适应方法，分别提升算法的收敛速度和迭代次数复杂度；通过实验验证效果。