论文标题
有限和耦合组成随机优化：理论和应用
Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications
论文作者
论文摘要
本文研究了对组成函数总和的随机优化，其中每个求和的内部函数与相应的求和指数耦合。我们将这个问题家族称为有限和耦合的组成优化（FCCO）。它在机器学习中具有广泛的应用，用于优化非凸或凸组成措施/目标，例如平均精度（AP），p-norm推动，列表等级损失，邻居成分分析（NCA），深度存活分析，深层可变模型等，这是值得进行分析的。但是，现有的算法和分析在一个或其他方面受到限制。本文的贡献是为非凸和凸目标的简单随机算法提供全面的收敛分析。我们的关键结果是通过使用带有微型批次的基于移动平均的估计器，通过并行加速提高了Oracle的复杂性。我们的理论分析还展示了通过对外部和内部水平相等大小的批量来改善实际实现的新见解。关于AP最大化，NCA和P-norm的数值实验证实了该理论的某些方面。
This paper studies stochastic optimization for a sum of compositional functions, where the inner-level function of each summand is coupled with the corresponding summation index. We refer to this family of problems as finite-sum coupled compositional optimization (FCCO). It has broad applications in machine learning for optimizing non-convex or convex compositional measures/objectives such as average precision (AP), p-norm push, listwise ranking losses, neighborhood component analysis (NCA), deep survival analysis, deep latent variable models, etc., which deserves finer analysis. Yet, existing algorithms and analyses are restricted in one or other aspects. The contribution of this paper is to provide a comprehensive convergence analysis of a simple stochastic algorithm for both non-convex and convex objectives. Our key result is the improved oracle complexity with the parallel speed-up by using the moving-average based estimator with mini-batching. Our theoretical analysis also exhibits new insights for improving the practical implementation by sampling the batches of equal size for the outer and inner levels. Numerical experiments on AP maximization, NCA, and p-norm push corroborate some aspects of the theory.
