Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

Tianyi Lin, Chengyou Fan, Mengdi Wang, Michael I. Jordan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Convex composition optimization is an emerging topic that covers a wide range of applications arising from stochastic optimal control, reinforcement learning and multistage 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/ϵ3) 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.

Original languageEnglish (US)
Title of host publication2020 American Control Conference, ACC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538682661
StatePublished - Jul 2020
Event2020 American Control Conference, ACC 2020 - Denver, United States
Duration: Jul 1 2020Jul 3 2020

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Conference2020 American Control Conference, ACC 2020
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient'. Together they form a unique fingerprint.

Cite this