Variance Reduced methods for Non-convex Composition Optimization

Abstract

This paper explores the non-convex composition optimization in the form including inner and outer finite-sum functions with a large number of component functions. This problem arises in some important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexity tends to be high, especially when the number of inner component functions is large. In this paper, we apply the variance-reduced technique to derive two variance reduced algorithms that significantly improve the query complexity if the number of inner component functions is large. To the best of our knowledge, this is the first work that establishes the query complexity analysis for non-convex stochastic composition. Experiments validate the proposed algorithms and theoretical analysis.

References in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Accelerated Methods for Non-Convex Optimization
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Accelerating Stochastic Composition Optimization
• Learning from Conditional Distributions via Dual Embeddings

Cited by in corpus (10)

• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Compositional ADAM: An Adaptive Compositional Solver
• Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem
• Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications