Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization

Abstract

We consider the nonsmooth convex composition optimization problem where the objective is a composition of two finite-sum functions and analyze stochastic compositional variance reduced gradient (SCVRG) methods for them. SCVRG and its variants have recently drawn much attention given their edge over stochastic compositional gradient descent (SCGD); but the theoretical analysis exclusively assumes strong convexity of the objective, which excludes several important examples such as Lasso, logistic regression, principle component analysis and deep neural nets. In contrast, we prove non-asymptotic incremental first-order oracle (IFO) complexity of SCVRG or its novel variants for nonsmooth convex composition optimization and show that they are provably faster than SCGD and gradient descent. More specifically, our method achieves the total IFO complexity of $O\left((m+n)\log \left(1/\epsilon \right)+1/{\epsilon }^3\right)$ which improves that of $O\left(1/{\epsilon }^{3.5}\right)$ and $O\left((m+n)/\sqrt{\epsilon }\right)$ obtained by SCGD and accelerated gradient descent (AGD) respectively. Experimental results confirm that our methods outperform several existing methods, e.g., SCGD and AGD, on sparse mean-variance optimization problem.

arXiv commentWe improve the current result and have a new version arXiv:1806.00458

References in corpus (11)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Variable selection in nonparametric additive models
• Stochastic Variance Reduction for Nonconvex Optimization
• Variance Reduction for Faster Non-Convex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Tight Complexity Bounds for Optimizing Composite Objectives
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Multi-Level Stochastic Gradient Methods for Nested Composition Optimization