Fetching the paper…
Reading the bibliography…
We prove lower bounds on the complexity of finding $\epsilon$-stationary points (points $x$ such that $\|\nabla f(x)\| \le \epsilon$) of smooth, high-dimensional, and potentially non-convex functions $f$.
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.
A method of solving a convex programming problem with convergence rate O ( 1 / k 2 ) {O}(1/k^{2})
Y. Nesterov · 1983
Earlier work this paper cites.
Some NP-complete problems in quadratic and nonlinear programming
K. Murty and S. Kabadi · 1987
Earlier work this paper cites.
Information-Based Complexity
J. Traub, H. Wasilkowski, and H. Wozniakowski · 1988
Earlier work this paper cites.
On the limited memory BFGS method for large scale optimization
D. Liu and J. Nocedal · 1989
Earlier work this paper cites.
Black-box complexity of local minimization
S. A. Vavasis · 1993
Earlier work this paper cites.
Efficient methods in convex programming
A. Nemirovski · 1994
Earlier work this paper cites.
An elementary introduction to modern convex geometry
K. Ball · 1997
Earlier work this paper cites.
Trust Region Methods
A. R. Conn, N. I. M. Gould, and P. L. Toint · 2000
Earlier work this paper cites.
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
S. Burer and R. D. Monteiro · 2003
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.
A survey of nonlinear conjugate gradient methods
W. W. Hager and H. Zhang · 2006
Earlier work this paper cites.
Cubic regularization of Newton method and its global performance
Y. Nesterov and B. Polyak · 2006
Cited alongside, same era.
Numerical Optimization
J. Nocedal and S. J. Wright · 2006
Cited alongside, same era.
Improved bounds on Bell numbers and on moments of sums of random variables
D. Berend and T. Tassa · 2010
Cited alongside, same era.
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
Cited alongside, same era.
Matrix completion from noisy entries
R. H. Keshavan, A. Montanari, and S. Oh · 2010
Cited alongside, same era.
Information-theoretic lower bounds on the oracle complexity of convex optimization
A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright · 2012
On lower and upper bounds in smooth and strongly convex optimization
Y. Arjevani, S. Shalev-Shwartz, and O. Shamir · 2016
Later among the works it cites.
The non-convex Burer-Monteiro approach works on smooth semidefinite programs
N. Boumal, V. Voroninski, and A. Bandeira · 2016
Later among the works it cites.
Tight complexity bounds for optimizing composite objectives
B. E. Woodworth and N. Srebro · 2016
Later among the works it cites.
Finding approximate local minima faster than gradient descent
N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma · 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
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
P.-L. Loh and M. J. Wainwright · 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.
A note about the complexity of minimizing nesterov’s smooth chebyshev-rosenbrock function
C. Cartis, N. I. Gould, and P. L Toint · 2013
Cited alongside, same era.
On Nesterov’s smooth Chebyshev-Rosenbrock function
F. Jarre · 2013
Cited alongside, same era.
Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
P.-L. Loh and M. J. Wainwright · 2013
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.
E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and P. L. Toint · 2017
Closest in time.
Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory
G. Braun, C. Guzmán, and S. Pokutta · 2017
Closest in time.
C. Cartis, N. I. M. Gould, 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.
Lower bound for randomized first order convex optimization
B. E. Woodworth and N. Srebro · 2017
Closest in time.
Accelerated methods for non-convex optimization
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford · 2018
Closest in time.
Cutting plane methods can be extended into nonconvex optimization
O. Hinder · 2018
Closest in time.
A geometric analysis of phase retrieval
J. Sun, Q. Qu, and J. Wright · 2018
Closest in time.