A Stochastic Composite Gradient Method with Incremental Variance Reduction

Abstract

We consider the problem of minimizing the composition of a smooth (nonconvex) function and a smooth vector mapping, where the inner mapping is in the form of an expectation over some random variable or a finite sum. We propose a stochastic composite gradient method that employs an incremental variance-reduced estimator for both the inner vector mapping and its Jacobian. We show that this method achieves the same orders of complexity as the best known first-order methods for minimizing expected-value and finite-sum nonconvex functions, despite the additional outer composition which renders the composite gradient estimator biased. This finding enables a much broader range of applications in machine learning to benefit from the low complexity of incremental variance-reduction methods.

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• On Graduated Optimization for Stochastic Non-Convex Problems
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization

Cited by in corpus (3)

• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization