Accelerating Stochastic Composition Optimization
Mengdi Wang, Ji Liu, Ethan Fang
Abstract
Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic first-order method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method, which updates based on queries to the sampling oracle using two different timescales. The ASC-PG is the first proximal gradient method for the stochastic composition problem that can deal with nonsmooth regularization penalty. We show that the ASC-PG exhibits faster convergence than the best known algorithms, and that it achieves the optimal sample-error complexity in several important special cases. We further demonstrate the application of ASC-PG to reinforcement learning and conduct numerical experiments.
BibTeX
@inproceedings{NIPS2016_92262bf9,
author = {Wang, Mengdi and Liu, Ji and Fang, Ethan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Accelerating Stochastic Composition Optimization},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/92262bf907af914b95a0fc33c3f33bf6-Paper.pdf},
volume = {29},
year = {2016}
}