Finite-sum Composition Optimization via Variance Reduced Gradient Descent

Abstract

The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: ${\min }_x({\mathbb{E}}_i{F}_i\circ {\mathbb{E}}_j{G}_j)(x).$ It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: \[\min_x f (x) := \frac{1}{n} \sum_{i = 1}^n F_i \left(\frac{1}{m} \sum_{j = 1}^m G_j (x) \right). \] We propose two algorithms to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique. A constant linear convergence rate is proved for strongly convex optimization, which substantially improves the sublinear rate $O(K^{-0.8})$ of the best known algorithm.

Cited by in corpus (24)

• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Variance Reduced methods for Non-convex Composition Optimization
• Compositional ADAM: An Adaptive Compositional Solver
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications