Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications

  • 2022-09-21 18:25:18
  • Bokun Wang, Tianbao Yang
  • 0

Abstract

This paper studies stochastic optimization for a sum of compositionalfunctions, where the inner-level function of each summand is coupled with thecorresponding summation index. We refer to this family of problems asfinite-sum coupled compositional optimization (FCCO). It has broad applicationsin machine learning for optimizing non-convex or convex compositionalmeasures/objectives such as average precision (AP), p-norm push, listwiseranking losses, neighborhood component analysis (NCA), deep survival analysis,deep latent variable models, etc., which deserves finer analysis. Yet, existingalgorithms and analyses are restricted in one or other aspects. Thecontribution of this paper is to provide a comprehensive convergence analysisof a simple stochastic algorithm for both non-convex and convex objectives. Ourkey result is the improved oracle complexity with the parallel speed-up byusing the moving-average based estimator with mini-batching. Our theoreticalanalysis also exhibits new insights for improving the practical implementationby sampling the batches of equal size for the outer and inner levels. Numericalexperiments on AP maximization, NCA, and p-norm push corroborate some aspectsof the theory.

 

Quick Read (beta)

loading the full paper ...