@inproceedings{59d3c394b03e42dda14fda733d9c4e2a,
title = "Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient",
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.",
author = "Tianyi Lin and Chengyou Fan and Mengdi Wang and Jordan, {Michael I.}",
note = "Publisher Copyright: {\textcopyright} 2020 AACC.; 2020 American Control Conference, ACC 2020 ; Conference date: 01-07-2020 Through 03-07-2020",
year = "2020",
month = jul,
doi = "10.23919/ACC45564.2020.9147515",
language = "English (US)",
series = "Proceedings of the American Control Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "126--131",
booktitle = "2020 American Control Conference, ACC 2020",
address = "United States",
}