Fetching the paper…
Reading the bibliography…
We give nearly matching upper and lower bounds on the oracle complexity of finding $\epsilon$-stationary points ($\| \nabla F(x) \| \leq\epsilon$) in stochastic convex optimization.
Problem complexity and method efficiency in optimization
Arkadii Semenovich Nemirovski and David Borisovich Yudin · 1983
Earlier work this paper cites.
Information-based complexity
Joseph F Traub, Grzegorz W Wasilkowski, and Henryk Woźniakowski · 1988
Earlier work this paper cites.
Computing with noisy information
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal · 1994
Earlier work this paper cites.
Introductory lectures on convex optimization: a basic course
Yurii Nesterov · 2004
Earlier work this paper cites.
Noisy binary search and its applications
Richard M Karp and Robert Kleinberg · 2007
Earlier work this paper cites.
Information-theoretic lower bounds on the oracle complexity of convex optimization
Alekh Agarwal, Martin J Wainwright, Peter L Bartlett, and Pradeep K Ravikumar · 2009
Earlier work this paper cites.
Stochastic convex optimization
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan · 2009
Earlier work this paper cites.
Optimal distributed online prediction using mini-batches
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao · 2012
Earlier work this paper cites.
Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework
Saeed Ghadimi and Guanghui Lan · 2012
Cited alongside, same era.
How to make the gradients small
Yurii Nesterov · 2012
Cited alongside, same era.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
Saeed Ghadimi and Guanghui Lan · 2013
Cited alongside, same era.
Accelerated gradient methods for nonconvex nonlinear and stochastic programming
Saeed Ghadimi and Guanghui Lan · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczós, and Alex Smola · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
Blake Woodworth and Nati Srebro · 2016
How to escape saddle points efficiently
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan · 2017
Later among the works it cites.
Non-convex finite-sum optimization via scsg methods
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan · 2017
Later among the works it cites.
How to make the gradients small stochastically: Even faster convex and nonconvex sgd
Zeyuan Allen-Zhu · 2018
Later among the works it cites.
Complexity of finding near-stationary points of convex functions stochastically
Damek Davis and Dmitriy Drusvyatskiy · 2018
Later among the works it cites.
Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Katyusha: The first direct acceleration of stochastic gradient methods
Zeyuan Allen-Zhu · 2017
Cited alongside, same era.
Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory
Gábor Braun, Cristóbal Guzmán, and Sebastian Pokutta · 2017
Cited alongside, same era.
Lower bounds for finding stationary points i
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford
Cited in the paper.
Lower bounds for finding stationary points ii: First-order methods
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford
Cited in the paper.
Blake Woodworth, Jialei Wang, Brendan McMahan, and Nathan Srebro · 2018
Later among the works it cites.
Stochastic nested variance reduced gradient descent for nonconvex optimization
Dongruo Zhou, Pan Xu, and Quanquan Gu · 2018
Later among the works it cites.