Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

2018/06/01 by Lin, Tianyi, Fan, Chenyou, Wang, Mengdi +1
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1806.00458

Abstract

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/ε)+1/ε³) 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.

Related

• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization
• Variance Reduced methods for Non-convex Composition Optimization
• Stochastic Compositional Gradient Descent under Compositional Constraints