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.
翻译:本文研究组合函数之和的随机优化, 每一个总和的内值功能与相应的总和指数相伴。 我们将此组问题称为有限和交配的合成优化( FCCO) 。 它在机器学习中具有广泛的应用性, 以优化非convex 或convex 构成措施/目标, 如平均精确度( AP)、 p- 中枢推力、 列表排序损失、 邻里部件分析( NCA)、 深度生存分析、 深潜变量模型等, 值得更精确的分析。 然而, 现有的算法和分析在一个或多个方面受到限制 。 本文的贡献是对非convex 和 convex 目标的简单随机算法进行全面的趋同分析。 我们的关键结果是, 使用移动平均的迷你比标提高了与平行速度的复杂度。 我们的理论分析还展示了通过抽样外部和内层同等尺寸的批量来改进实际执行的新见解。 关于AP 最大化、 NCA 和 理论 和 pentron 的某种数值实验。