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

Abstract

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.
Pages126-131
Number of pages6
ISBN (Electronic)9781538682661
DOIs
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
Volume2020-July
ISSN (Print)0743-1619

Conference

Conference2020 American Control Conference, ACC 2020
CountryUnited States
CityDenver
Period7/1/207/3/20

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

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

  • Cite this

    Lin, T., Fan, C., Wang, M., & Jordan, M. I. (2020). Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient. In 2020 American Control Conference, ACC 2020 (pp. 126-131). [9147515] (Proceedings of the American Control Conference; Vol. 2020-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/ACC45564.2020.9147515