Fetching the paper…
Reading the bibliography…
We lower bound the complexity of finding $\epsilon$-stationary points (with gradient norm at most $\epsilon$) using stochastic first-order methods.
Convergence of estimates under dimensionality restrictions
L. LeCam · 1973
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
A. C.-C. Yao · 1977
Earlier work this paper cites.
Problem Complexity and Method Efficiency in Optimization
A. Nemirovski and D. B. Yudin · 1983
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate o ( 1 / k 2 ) o(1/k^{2})
Y. E. Nesterov · 1983
Earlier work this paper cites.
Some np-complete problems in quadratic and nonlinear programming
K. G. Murty and S. N. Kabadi · 1987
Earlier work this paper cites.
Information-based complexity
J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski · 1988
Earlier work this paper cites.
Black-box complexity of local minimization
S. A. Vavasis · 1993
Earlier work this paper cites.
On parallel complexity of nonsmooth convex optimization
A. Nemirovski · 1994
Earlier work this paper cites.
An elementary introduction to modern convex geometry
K. Ball · 1997
Earlier work this paper cites.
Assouad, Fano, and Le Cam
B. Yu · 1997
Earlier work this paper cites.
Introductory lectures of convex optimization
Y. Nesterov · 2004
Earlier work this paper cites.
Cubic regularization of newton method and its global performance
Y. Nesterov and B. T. Polyak · 2006
Earlier work this paper cites.
Numerical optimization
J. Nocedal and S. Wright · 2006
Earlier work this paper cites.
The tradeoffs of large scale learning
L. Bottou and O. Bousquet · 2008
Earlier work this paper cites.
On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization problems
C. Cartis, N. I. Gould, and P. L. Toint · 2010
Earlier work this paper cites.
Information-based complexity, feedback and dynamics in convex programming
M. Raginsky and A. Rakhlin · 2011
Earlier work this paper cites.
Convergence rates of inexact proximal-gradient methods for convex optimization
M. Schmidt, N. L. Roux, and F. Bach · 2011
Cited alongside, same era.
Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization
A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright · 2012
Cited alongside, same era.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
S. Ghadimi and G. Lan · 2013
Cited alongside, same era.
Stochastic dual coordinate ascent methods for regularized loss minimization
S. Shalev-Shwartz and T. Zhang · 2013
Cited alongside, same era.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
A. Defazio, F. Bach, and S. Lacoste-Julien · 2014
Cited alongside, same era.
Escaping from saddle points: online stochastic gradient for tensor decomposition
Lower bound for randomized first order convex optimization
B. Woodworth and N. Srebro · 2017
Later among the works it cites.
Neon2: Finding local minima via first-order oracles
Z. Allen-Zhu and Y. Li · 2018
Later among the works it cites.
Optimization methods for large-scale learning
L. Bottou, F. Curtis, and J. Nocedal · 2018
Later among the works it cites.
Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
C. Fang, C. J. Li, Z. Lin, and T. Zhang · 2018
Later among the works it cites.
A geometric analysis of phase retrieval
J. Sun, Q. Qu, and J. Wright · 2018
Later among the works it cites.
Stochastic cubic regularization for fast nonconvex optimization
N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M. I. Jordan · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
R. Ge, F. Huang, C. Jin, and Y. Yuan · 2015
Cited alongside, same era.
Variance reduction for faster non-convex optimization
Z. Allen-Zhu and E. Hazan · 2016
Cited alongside, same era.
Dimension-free iteration complexity of finite sum optimization problems
Y. Arjevani and O. Shamir · 2016
Cited alongside, same era.
Matrix completion has no spurious local minimum
R. Ge, J. D. Lee, and T. Ma · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
B. Woodworth and N. Srebro · 2016
Cited alongside, same era.
Limitations on variance-reduction and acceleration schemes for finite sums optimization
Y. Arjevani · 2017
Cited alongside, same era.
Later among the works it cites.
Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization
Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh · 2018
Later among the works it cites.
First-order stochastic algorithms for escaping from saddle points in almost linear time
Y. Xu, J. Rong, and T. Yang · 2018
Later among the works it cites.
Momentum-based variance reduction in non-convex SGD
A. Cutkosky and F. Orabona · 2019
Closest in time.
The complexity of finding stationary points with stochastic gradient descent
Y. Drori and O. Shamir · 2019
Closest in time.
Sharp analysis for nonconvex SGD escaping from saddle points
C. Fang, Z. Lin, and T. Zhang · 2019
Closest in time.
The complexity of making the gradient small in stochastic convex optimization
D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. Woodworth · 2019
Closest in time.
Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution
C. Ma, K. Wang, Y. Chi, and Y. Chen · 2019
Closest in time.
Lower bounds for smooth nonconvex finite-sum optimization
D. Zhou and Q. Gu · 2019
Closest in time.
Stochastic nested variance reduction for nonconvex optimization
D. Zhou, P. Xu, and Q. Gu · 2020
Closest in time.