Lower bounds for finding stationary points I

2017/10/31 by Yair Carmon, Carmon, Yair, John C. Duchi +5 · 47 citations
Computer Science · Engineering · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Convex function #Discrete mathematics #Function (biology) #Geometry #Lipschitz continuity #Mathematical analysis #Mathematics #Nabla symbol #Oracle #Order (exchange) #Physics #Regular polygon #Regularization (linguistics) #Sparse and Compressive Sensing Techniques #Stationary point #Stochastic Gradient Optimization Techniques #Upper and lower bounds #math.OC

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

published in Mathematical Programming 184(1-2), 71-120 (Springer Science+Business Media)

openalex publication_date 2019/06/07 · arxiv created 2019/08/15 · arxiv updated 2019/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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 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
• Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion
• Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks
• A Fast Newton Method Under Local Lipschitz Smoothness
• Some Worst-Case Datasets of Deterministic First-Order Methods for Solving Binary Logistic Regression
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Adaptive Complexity of Finding a Stationary Point
• Min-Max Optimization Requires Exponentially Many Queries
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Optimal Deterministic Oracle Complexity for Weakly Convex Optimization
• Observability conditions for neural state-space models with eigenvalues and their roots of unity

Related

• On the complexity of finding stationary points of smooth functions in one dimension
• Lower Bounds for Finding Stationary Points II: First-Order Methods
• The Adaptive Complexity of Finding a Stationary Point
• On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization