Compositional Stochastic Average Gradient for Machine Learning and Related Applications

Abstract

Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG) methods that combine stochastic compositional gradient descent (SCGD) and stochastic variance reduced gradient descent (SVRG) methods are the state-of-the-art methods for FS-CEVF problems. We introduce compositional stochastic average gradient descent (C-SAG) a novel extension of the stochastic average gradient method (SAG) to minimize composition of finite-sum functions. C-SAG, like SAG, estimates gradient by incorporating memory of previous gradient information. We present theoretical analyses of C-SAG which show that C-SAG, like SAG, and C-SVRG, achieves a linear convergence rate when the objective function is strongly convex; However, C-CAG achieves lower oracle query complexity per iteration than C-SVRG. Finally, we present results of experiments showing that C-SAG converges substantially faster than full gradient (FG), as well as C-SVRG.

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Learning from Conditional Distributions via Dual Embeddings
• Variance Reduced methods for Non-convex Composition Optimization
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Unbiased scalable softmax optimization
• Fast Stochastic Variance Reduced ADMM for Stochastic Composition Optimization