Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
Abstract
Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer p≥3, finding an eps-stationary point requires Ωp(eps−5/3) exact value-and-gradient queries, even for C∞ objectives with initial gap at most one and simultaneous global Lipschitz budgets of one for derivatives of orders 1,…,p. Together with the known deterministic upper bound, this determines the accuracy exponent up to a single logarithmic factor. The lower bound holds for unrestricted adaptive randomized algorithms, unbounded query locations, and outputs that need not have been queried. One algorithm-independent hard distribution suffices in dimension Op(eps−47/3). The construction combines a block-chain potential with an exact quartic core, repeated quadratic spectra, and two static Gaussian tensor perturbations. A scheduled Haar argument controls the entire adaptive query span. An innovation-only Gaussian comparison then bounds exact transcript information without assuming finite precision or a minimum query separation. This establishes the 5/3 randomized accuracy barrier under every prescribed finite smoothness order, extending the previously matched third-order case.
Related
- Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
- Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{zhang2026matching,
title = {{Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization}},
author = {Haihan Zhang and Wendao Wu and Fangqing Zhang and Chenheng Zhang and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17074},
eprint = {2610.17074},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17074},
}
RIS
TY - UNPB
TI - Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
AU - Haihan Zhang
AU - Wendao Wu
AU - Fangqing Zhang
AU - Chenheng Zhang
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.17074
UR - https://arxiv.org/abs/2610.17074
AB - Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer p≥3, finding an eps-stationary point requires Ω_p(eps^−5/3) exact value-and-gradient queries, even for C^∞ objectives with initial gap at most one and simultaneous global Lipschitz budgets of one for derivatives of orders 1,…,p. Together with the known deterministic upper bound, this determines the accuracy exponent up to a single logarithmic factor. The lower bound holds for unrestricted adaptive randomized algorithms, unbounded query locations, and outputs that need not have been queried. One algorithm-independent hard distribution suffices in dimension O_p(eps^−47/3). The construction combines a block-chain potential with an exact quartic core, repeated quadratic spectra, and two static Gaussian tensor perturbations. A scheduled Haar argument controls the entire adaptive query span. An innovation-only Gaussian comparison then bounds exact transcript information without assuming finite precision or a minimum query separation. This establishes the 5/3 randomized accuracy barrier under every prescribed finite smoothness order, extending the previously matched third-order case.
ER -