  Stochastic composition optimization draws much attention recently and has
been successful in many emerging applications of machine learning, statistical
analysis, and reinforcement learning. In this paper, we focus on the
composition problem with nonsmooth regularization penalty. Previous works
either have slow convergence rate or do not provide complete convergence
analysis for the general problem. In this paper, we tackle these two issues by
proposing a new stochastic composition optimization method for composition
problem with nonsmooth regularization penalty. In our method, we apply variance
reduction technique to accelerate the speed of convergence. To the best of our
knowledge, our method admits the fastest convergence rate for stochastic
composition optimization: for strongly convex composition problem, our
algorithm is proved to admit linear convergence; for general composition
problem, our algorithm significantly improves the state-of-the-art convergence
rate from $O(T^{-1/2})$ to $O((n_1+n_2)^{{2}/{3}}T^{-1})$. Finally, we apply
our proposed algorithm to portfolio management and policy evaluation in
reinforcement learning. Experimental results verify our theoretical analysis.
