证明了高阶光滑非凸优化中找驻点的最优下界，解决长期未解难题。
Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
- 构造块链机制，实现分块查询且保持光滑性。
- 在海森矩阵Lipschitz下达到Ω(ε⁻⁷/⁴)下界，第三阶光滑时为Ω(ε⁻⁵/³)。
- 首次给出高阶光滑情形下的一阶复杂度匹配下界，适合优化理论研究者。
我们研究在高阶光滑假设下，寻找平滑非凸优化中ε-驻点的确定性一阶预言机复杂度。虽然仅在梯度Lipschitz条件下经典复杂度为ε⁻²，但高阶光滑可带来加速的一阶上界，如在海森矩阵Lipschitz下为ε⁻⁷⁄⁴，三阶导数Lipschitz下为ε⁻⁵⁄³。然而，相应的匹配下界长期未解。本文通过提出一种维度无关的一阶下界，解决了该缺口，适用于任意有限光滑阶数。特别地，构造出海森矩阵光滑下的匹配Ω(ε⁻⁷⁄⁴)下界和三阶光滑下的Ω(ε⁻⁵⁄³)下界。该难例基于‘块链’机制，在保证光滑结构的同时强制分块预言机揭示。该构造由ChatGPT 5.5 Pro辅助生成，并经作者验证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。