Improved Sample Complexity for Stochastic Compositional Variance Reduced
  Gradient
  Convex composition optimization is an emerging topic that covers a wide range
of applications arising from stochastic optimal control, reinforcement learning
and multi-stage stochastic programming. Existing algorithms suffer from
unsatisfactory sample complexity and practical issues since they ignore the
convexity structure in the algorithmic design. In this paper, we develop a new
stochastic compositional variance-reduced gradient algorithm with the sample
complexity of $O((m+n)\log(1/\epsilon)+1/\epsilon^3)$ where $m+n$ is the total
number of samples. Our algorithm is near-optimal as the dependence on $m+n$ is
optimal up to a logarithmic factor. Experimental results on real-world datasets
demonstrate the effectiveness and efficiency of the new algorithm.
