Accelerated Method for Stochastic Composition Optimization With Nonsmooth Regularization

Authors

  • Zhouyuan Huo University of Pittsburgh
  • Bin Gu University of Pittsburgh
  • Ji Liu University of Rochester
  • Heng Huang University of Pittsburgh

Keywords:

Stochastic Composition Optimization, Variance Reduction, Large-Scale Optimization

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((n1+n2)2/3T-1). Finally, we apply our proposed algorithm to portfolio management and policy evaluation in reinforcement learning. Experimental results verify our theoretical analysis.

Downloads

Published

2018-04-29

How to Cite

Huo, Z., Gu, B., Liu, J., & Huang, H. (2018). Accelerated Method for Stochastic Composition Optimization With Nonsmooth Regularization. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11795