Lower bounds for finding stationary points II: first-order methods

DOI10.1007/s10107-019-01431-xzbMath1458.90520arXiv1711.00841OpenAlexW2974641549MaRDI QIDQ2220663

Aaron Sidford, Yair Carmon, Oliver Hinder, John C. Duchi

Publication date: 25 January 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.00841

zbMATH Keywords

gradient methodsnon-convex optimizationinformation-based complexityaccelerated gradient descentdimension-free rates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Large-scale problems in mathematical programming (90C06) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Related Items (6)

Tensor methods for finding approximate stationary points of convex functions ⋮ On lower iteration complexity bounds for the convex concave saddle point problems ⋮ Lower bounds for non-convex stochastic optimization ⋮ An accelerated first-order method for non-convex optimization on manifolds ⋮ A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression ⋮ Recent Theoretical Advances in Non-Convex Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
• Complexity bounds for second-order optimality in unconstrained optimization
• Introductory lectures on convex optimization. A basic course.
• Lower bounds for finding stationary points I
• Oracle complexity of second-order methods for smooth convex optimization
• Cubic regularization of Newton method and its global performance
• An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods
• On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
• Accelerated Methods for NonConvex Optimization
• Black-Box Complexity of Local Minimization
• The Best Rank-1 Approximation of a Symmetric Tensor and Related Spherical Optimization Problems
• Finding approximate local minima faster than gradient descent
• WORST-CASE EVALUATION COMPLEXITY AND OPTIMALITY OF SECOND-ORDER METHODS FOR NONCONVEX SMOOTH OPTIMIZATION
• Tight query complexity lower bounds for PCA via finite sample deformed wigner law
• On Nesterov's smooth Chebyshev–Rosenbrock function
• On Recursions Connected With Symmetric Groups I

This page was built for publication: Lower bounds for finding stationary points II: first-order methods