Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Not on the map. Why?
Abstract (arXiv)
We study the deterministic first-order oracle complexity of finding (ε)-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical (ε-2) rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the (ε-7/4) rate under Lipschitz Hessians and the (ε-5/3) rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching (Omega(ε-7/4)) lower bound in the Hessian-Lipschitz case and a matching (Omega(ε-5/3)) lower bound in the third-order-smooth regime. The hard instance is based on a block-chain mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 27 of its 39 references that are in the map. First posted on arXiv 3 Jun 2026.
Builds on
27 of 39 references.
References · 27
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
- 2017How to Escape Saddle Points Efficientlycited by 285
- 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
- 2017Lower Bounds for Finding Stationary Points Icited by 126
- 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
- 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
- 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
- 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
- 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
- 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
- 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
15 more
- 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
- 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
- 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
- 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
- 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
- 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
- 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
- 2018Stochastic Variance-Reduced Cubic Regularized Newton Methodcited by 10
- 2017NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimizationcited by 9
- 2018Finding Local Minima via Stochastic Nested Variance Reductioncited by 9
- 2022Parameter-free accelerated gradient descent for nonconvex minimizationcited by 7
- 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
- 2017Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimizationcited by 6
- 2025Balancing Gradient and Hessian Queries in Non-Convex Optimizationcited by 3
- 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.