Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Abstract
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 Ω(ε−7/4) lower bound in the Hessian-Lipschitz case and a matching Ω(ε−5/3) lower bound in the third-order-smooth regime. The hard instance is based on a \emph{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.
Related
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Continuized Nesterov Momentum Achieves the O(ε−7/4) Complexity in Smooth Nonconvex Optimization
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{zhou2026sharp,
title = {{Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization}},
author = {Dongruo Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.05438},
eprint = {2606.05438},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.05438},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
AU - Dongruo Zhou
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2606.05438
UR - https://arxiv.org/abs/2606.05438
AB - 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 Ω(ε^−7/4) lower bound in the Hessian-Lipschitz case and a matching Ω(ε^−5/3) lower bound in the third-order-smooth regime. The hard instance is based on a \emph{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.
ER -