Lower bounds for finding stationary points I

2017/10/31 by Yair Carmon, Carmon, Yair, John C. Duchi +5 · 37 citations
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs

paper · doi:10.1007/s10107-019-01406-y

Abstract

We prove lower bounds on the complexity of finding ε-stationary points (points x such that ‖∇ f(x)‖ ≤ ε) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm A, there exists a function f with Lipschitz pth order derivatives such that A requires at least ε^-(p+1)/p queries to find an ε-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton's method, and generalized pth order regularization are worst-case optimal within their natural function classes.

Citations

• On the limited memory BFGS method for large scale optimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms

Cited by

• Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
• Global Optimality Characterizations and Algorithms for Minimizing Quartically-Regularized Third-Order Taylor Polynomials
• The matrix-vector complexity of Ax=b
• On the hardness of deterministic second-order optimization of functions with Lipschitz gradients
• A Homogeneous Tensor Framework for High-Order Trust-Region and Spherical Polynomial Optimization
• Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity
• Continuized Nesterov Acceleration for Non-Convex Optimization
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• A Generalized Energy-Based Adaptive Gradient Method for Optimization
• Worst-case generation via minimax optimization in Wasserstein space
• On the Condition Number Dependency in Bilevel Optimization
• Worst-case iteration bounds for log barrier methods on problems with nonconvex constraints
• Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
• Subgame Perfect Methods in Nonsmooth Convex Optimization
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with\n Complexity Guarantees
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism
• Complexity of finding near-stationary points of convex functions stochastically
• Balancing Gradient and Hessian Queries in Non-Convex Optimization
• Beyond the Ideal: Analyzing the Inexact Muon Update
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
• On the Complexity of Lower-Order Implementations of Higher-Order Methods
• A Simple Adaptive Proximal Gradient Method for Nonconvex Optimization
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning
• Simple linesearch-free first-order methods for nonconvex optimization
• Complexity Bounds for Smooth Multiobjective Optimization
• Low-rank Orthogonalization for Large-scale Matrix Optimization with Applications to Foundation Model Training
• AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates
• Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
• Lower Bounds for Parallel and Randomized Convex Optimization
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Lower Bound for Randomized First Order Convex Optimization
• Faster stochastic cubic regularized Newton methods with momentum
• SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction