Fetching the paper…

Reading the bibliography…

2020

Optimal Algorithms for Convex Nested Stochastic Composite Optimization

Zhang, Zhe, Lan, Guanghui

Original
PDF
Post on X

Understand

Recently, convex nested stochastic composite optimization (NSCO) has received considerable attention for its applications in reinforcement learning and risk-averse optimization.

The current NSCO algorithms have worse stochastic oracle complexities, by orders of magnitude, than those for simpler stochastic composite optimization problems (e.g., sum of smooth and nonsmooth functions) without the nested structure.
Moreover, they require all outer-layer functions to be smooth, which is not satisfied by some important applications.
These discrepancies prompt us to ask: ``does the nested composition make stochastic optimization more difficult in terms of the order of oracle complexity?" In this paper, we answer the question by developing order-optimal algorithms for the convex NSCO problem constructed from an arbitrary composition of smooth, structured non-smooth and general non-smooth layer functions.

Optimal Algorithms for Convex Nested Stochastic Composite Optimization · Around

Built on

A. S. Nemirovsky and D. B. Yudin
1983
Earlier work this paper cites.
Y. Nesterov
2003
Earlier work this paper cites.
Y. Nesterov
2005
Earlier work this paper cites.
Y. Nesterov
2007
Earlier work this paper cites.
P. Tseng
2008
Earlier work this paper cites.
A. Beck and M. Teboulle
2009
Earlier work this paper cites.
S. Ghadimi and G. Lan
2012
Earlier work this paper cites.
S. Ghadimi and G. Lan
2013
Earlier work this paper cites.

Similar

Y. Chen, G. Lan, and Y. Ouyang
2014
Cited alongside, same era.
A. Shapiro, D. Dentcheva, and A. Ruszczyński
2014
Cited alongside, same era.
A. S. Lewis and S. J. Wright
2016
Cited alongside, same era.
M. Wang, E. X. Fang, and H. Liu
2017
Cited alongside, same era.
M. Wang, J. Liu, and E. X. Fang
2017
Cited alongside, same era.
G. Lan and Y. Zhou
2018
Cited alongside, same era.
S. Yang, M. Wang, and E. X. Fang
2019
Cited alongside, same era.

Then

Z. Zhang, S. Ahmed, and G. Lan
Original
2019
Later among the works it cites.
T. Chen, Y. Sun, and W. Yin
Original
2020
Closest in time.
S. Ghadimi, A. Ruszczynski, and M. Wang
2020
Closest in time.
under revision
G. Lan and Y. Ouyang · 2020
Closest in time.
A. Ruszczynski
Original
2020
Closest in time.
K. Balasubramanian, S. Ghadimi, and A. Nguyen
2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

J. Zhang and L. Xiao

2019

Cited alongside, same era.

G. Lan and Z. Zhang

2022

Closest in time.

S. Ghadimi and G. Lan

2089

Closest in time.