Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem

Abstract

In this paper, we consider the convex and non-convex composition problem with the structure $\frac{1}{n}{\sum }_{i=1}^n{F}_i(G(x))$, where $G(x)=\frac{1}{n}{\sum }_{j=1}^n{G}_j(x)$ is the inner function, and $F_i(\cdot )$ is the outer function. We explore the variance reduction based method to solve the composition optimization. Due to the fact that when the number of inner function and outer function are large, it is not reasonable to estimate them directly, thus we apply the stochastically controlled stochastic gradient (SCSG) method to estimate the gradient of the composition function and the value of the inner function. The query complexity of our proposed method for the convex and non-convex problem is equal to or better than the current method for the composition problem. Furthermore, we also present the mini-batch version of the proposed method, which has the improved the query complexity with related to the size of the mini-batch.

References in corpus (5)

• Stochastic Variance Reduction for Nonconvex Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Variance Reduced methods for Non-convex Composition Optimization

Cited by in corpus (5)

• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Efficient Semi-Implicit Variational Inference