Accelerating stochastic composition optimization

Mengdi Wang, Ji Liu, Ethan X. Fang

Research output: Contribution to journalConference article

11 Citations (Scopus)

Abstract

Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic firstorder 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.

Original languageEnglish (US)
Pages (from-to)1722-1730
Number of pages9
JournalAdvances in Neural Information Processing Systems
StatePublished - Jan 1 2016
Event30th Annual Conference on Neural Information Processing Systems, NIPS 2016 - Barcelona, Spain
Duration: Dec 5 2016Dec 10 2016

Fingerprint

Gradient methods
Chemical analysis
Reinforcement learning
Sampling
Experiments

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Signal Processing
  • Computer Networks and Communications

Cite this

@article{fd3e274cba7f4ba7841a71930ea2a387,
title = "Accelerating stochastic composition optimization",
abstract = "Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic firstorder 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.",
author = "Mengdi Wang and Ji Liu and Fang, {Ethan X.}",
year = "2016",
month = "1",
day = "1",
language = "English (US)",
pages = "1722--1730",
journal = "Advances in Neural Information Processing Systems",
issn = "1049-5258",

}

Accelerating stochastic composition optimization. / Wang, Mengdi; Liu, Ji; Fang, Ethan X.

In: Advances in Neural Information Processing Systems, 01.01.2016, p. 1722-1730.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Accelerating stochastic composition optimization

AU - Wang, Mengdi

AU - Liu, Ji

AU - Fang, Ethan X.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic firstorder 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.

AB - Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic firstorder 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.

UR - http://www.scopus.com/inward/record.url?scp=85018920499&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018920499&partnerID=8YFLogxK

M3 - Conference article

SP - 1722

EP - 1730

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

ER -