Title: Variance Reduced Stochastic Proximal Algorithm for AUC Maximization Show Chinese title

Title: 方差减少的随机近似算法用于AUC最大化

Abstract: Stochastic Gradient Descent has been widely studied with classification accuracy as a performance measure. However, these stochastic algorithms cannot be directly used when non-decomposable pairwise performance measures are used such as Area under the ROC curve (AUC) which is a common performance metric when the classes are imbalanced. There have been several algorithms proposed for optimizing AUC as a performance metric, and one of the recent being a stochastic proximal gradient algorithm (SPAM). But the downside of the stochastic methods is that they suffer from high variance leading to slower convergence. To combat this issue, several variance reduced methods have been proposed with faster convergence guarantees than vanilla stochastic gradient descent. Again, these variance reduced methods are not directly applicable when non-decomposable performance measures are used. In this paper, we develop a Variance Reduced Stochastic Proximal algorithm for AUC Maximization (\textsc{VRSPAM}) and perform a theoretical analysis as well as empirical analysis to show that our algorithm converges faster than SPAM which is the previous state-of-the-art for the AUC maximization problem. Show Chinese abstract

Abstract: 随机梯度下降已被广泛研究，以分类准确率为性能指标。 然而，当使用不可分解的成对性能指标时，如受试者工作特征曲线下的面积（AUC），这在类别不平衡时是一个常见的性能指标，这些随机算法不能直接使用。 已经提出了几种优化AUC作为性能指标的算法，其中最近的一个是随机近似梯度算法（SPAM）。 但随机方法的缺点是它们由于高方差而导致收敛速度较慢。 为了解决这个问题，已经提出了几种方差减少方法，其收敛保证比原始随机梯度下降更快。 同样，当使用不可分解的性能指标时，这些方差减少方法也不直接适用。 在本文中，我们开发了一种用于AUC最大化的方差减少随机近似算法（\textsc{VRSPAM}），并进行了理论分析和实证分析，以证明我们的算法在AUC最大化问题上比之前的最先进算法SPAM收敛得更快。