Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization

Abstract

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.

AAAI 2018

Cited by in corpus (14)

• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Privacy-Preserving Asynchronous Federated Learning Algorithms for Multi-Party Vertically Collaborative Learning
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Compositional federated learning: Applications in distributionally robust averaging and meta learning