Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
This addresses a computational bottleneck in machine learning, statistical analysis, and reinforcement learning applications, offering incremental improvements in convergence rates.
The paper tackles the problem of stochastic composition optimization with nonsmooth regularization, which has slow convergence or incomplete analysis in prior work, and proposes a method that achieves linear convergence for strongly convex cases and improves the state-of-the-art rate from O(T^{-1/2}) to O((n_1+n_2)^{2/3}T^{-1}) for general cases.
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.