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

DOI10.1007/S10107-019-01431-XMaRDI QIDQ2220663zbMATH OpenOpenAlexFDO

Authors Yair Carmon, Oliver Hinder, Aaron Sidford, 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

accelerated gradient descentdimension-free ratesgradient methodsinformation-based complexitynon-convex optimization

Mathematics Subject Classification ID

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

Abstract: We establish lower bounds on the complexity of finding $epsilon$-stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic first-order methods, even applied to arbitrarily smooth functions, cannot achieve convergence rates in $epsilon$ better than $epsilo{n}^{-8/5}$, which is within $epsilo{n}^{-1/15}logfrac1epsilon$ of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove no deterministic first-order method can achieve convergence rates better than $epsilo{n}^{-12/7}$, while $epsilo{n}^{-2}$ is a lower bound for functions with only Lipschitz gradient. For convex functions with Lipschitz gradient, accelerated gradient descent achieves the rate $epsilo{n}^{-1}logfrac1epsilon$, showing that finding stationary points is easier given convexity.

Recommendations

• Lower bounds for finding stationary points I
• A lower bound of stable stationary trajectories
• Finding second-order stationary points in constrained minimization: a feasible direction approach
• scientific article; zbMATH DE number 736944
• On the computation of linearly constrained stationary points
• Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
• Punti inferiormente stazionari ed equazioni di evoluzione con vincoli unilaterali non convessi
• Convergence to second-order stationary points in inequality constrained optimization
• scientific article; zbMATH DE number 4119955
• On the existence of stationary points for the Steiglitz-McBride algorithm

Cites work

• Accelerated methods for nonconvex optimization
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• Black-Box Complexity of Local Minimization
• Complexity bounds for second-order optimality in unconstrained optimization
• Cubic regularization of Newton method and its global performance
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Finding approximate local minima faster than gradient descent
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Lower bounds for finding stationary points I
• On Nesterov's smooth Chebyshev-Rosenbrock function
• On Recursions Connected With Symmetric Groups I
• On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
• Oracle complexity of second-order methods for smooth convex optimization
• The best rank-1 approximation of a symmetric tensor and related spherical optimization problems
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization
• Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Cited in

(25)

• On lower iteration complexity bounds for the convex concave saddle point problems
• Lower bounds for finding stationary points I
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Accelerated methods for nonconvex optimization
• Tensor methods for finding approximate stationary points of convex functions
• 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
• How to trap a gradient flow
• Complexity-optimal and parameter-free first-order methods for finding stationary points of composite optimization problems
• Efficient first order method for saddle point problems with higher order smoothness
• No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
• Hessian barrier algorithms for non-convex conic optimization
• Optimization on a finer scale: bounded local subgradient variation perspective
• Efficient optimal control of open quantum systems
• Beyond nonconvexity: a universal trust-region method with new analyses
• Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles
• Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
• Fisher information lower bounds for sampling
• On the complexity of finding stationary points of smooth functions in one dimension
• Nesterov's acceleration at the limit: first-order schemes
• A Homogeneous Tensor Framework for High-Order Trust-Region and Spherical Polynomial Optimization
• Complexity bounds for smooth multiobjective optimization
• Optimal complexity in Byzantine-robust distributed stochastic optimization with data heterogeneity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220663)