# Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

arXiv: https://arxiv.org/abs/2606.05438 · HTML: https://mlsanity.com/paper/2606.05438/

## Key facts

- Cited by 1 papers 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 (most cited first, 27 of 27)

- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Stochastic Recursive Variance-Reduced Cubic Regularization Methods](https://mlsanity.com/paper/1901.11518/) (2019)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Stochastic Variance-Reduced Cubic Regularized Newton Method](https://mlsanity.com/paper/1802.04796/) (2018)
- [NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization](https://mlsanity.com/paper/1712.01033/) (2017)
- [Finding Local Minima via Stochastic Nested Variance Reduction](https://mlsanity.com/paper/1806.08782/) (2018)
- [Parameter-free accelerated gradient descent for nonconvex minimization](https://mlsanity.com/paper/2212.06410/) (2022)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization](https://mlsanity.com/paper/1709.07180/) (2017)
- [Balancing Gradient and Hessian Queries in Non-Convex Optimization](https://mlsanity.com/paper/2510.20786/) (2025)
- [On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization](https://mlsanity.com/paper/2103.05138/) (2021)

## Built on by (most cited first, 1 of 1)

- [Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness](https://mlsanity.com/paper/2609.00045/) (2026)

## 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.