Fetching the paper…
Reading the bibliography…
We establish lower bounds on the complexity of finding $\epsilon$-stationary points of smooth, non-convex high-dimensional functions using first-order methods.
On recursions connected with symmetric groups I
S. Chowla, I. N. Herstein, and W. K. Moore · 1951
Earlier work this paper cites.
Problem Complexity and Method Efficiency in Optimization
A. Nemirovski and D. Yudin · 1983
Earlier work this paper cites.
Spectral Graph Theory
F. R. K. Chung · 1998
Earlier work this paper cites.
Convex Optimization
S. Boyd and L. Vandenberghe · 2004
Earlier work this paper cites.
Introductory Lectures on Convex Optimization
Y. Nesterov · 2004
Earlier work this paper cites.
Cubic regularization of Newton method and its global performance
Y. Nesterov and B. Polyak · 2006
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.
Distributed optimization and statistical learning via the alternating direction method of multipliers
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein · 2011
Earlier work this paper cites.
How to make the gradients small
Y. Nesterov · 2012
Cited alongside, same era.
The best rank-1 approximation of a symmetric tensor and related spherical optimization problems
X. Zhang, C. Ling, and L. Qi · 2012
Cited alongside, same era.
An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
R. D. Monteiro and B. F. Svaiter · 2013
Cited alongside, same era.
Variance reduction for faster non-convex optimization
Z. Allen-Zhu and E. Hazan · 2016
Cited alongside, same era.
Accelerated methods for non-convex optimization
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
Finding approximate local minima faster than gradient descent
N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma · 2017
Closest in time.
Natasha 2: Faster non-convex optimization than SGD
Z. Allen-Zhu · 2017
Closest in time.
Oracle complexity of second-order methods for smooth convex optimization
Y. Arjevani, O. Shamir, and R. Shiff · 2017
Closest in time.
Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and P. L. Toint · 2017
Closest in time.
How to escape saddle points efficiently
C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan · 2017
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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. E. Woodworth and N. Srebro · 2016
Cited alongside, same era.
Convex until proven guilty: dimension-free acceleration of gradient descent on non-convex functions
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford
Cited in the paper.
Lower bounds for finding stationary points I
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford
Cited in the paper.
Nonconvex finite-sum optimization via SCSG methods
L. Lei, C. Ju, J. Chen, and M. I. Jordan · 2017
Closest in time.
M. Simchowitz, A. E. Alaoui, and B. Recht · 2017
Closest in time.