Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth
  Convex Stochastic Composition Optimization
  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.
