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

Abstract:We study the deterministic first-order oracle complexity of finding \(\epsilon\)-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical \(\epsilon^{-2}\) rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the \(\epsilon^{-7/4}\) rate under Lipschitz Hessians and the \(\epsilon^{-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(\epsilon^{-7/4})\) lower bound in the Hessian-Lipschitz case and a matching \(\Omega(\epsilon^{-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.

24 pages, 1 table. Version 2 adds explicit numerical constants to all theorems

Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2606.05438 [cs.LG]

(or arXiv:2606.05438v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.05438 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.