Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization

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\ge 3$, finding an $\text{eps}$-stationary point requires ${\mathrm{\Omega }}_p({\text{eps}}^{-5\mathrm{/}3})$ exact value-and-gradient queries, even for $C^{\mathrm{\infty }}$ objectives with initial gap at most one and simultaneous global Lipschitz budgets of one for derivatives of orders $1,\dots ,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({\text{eps}}^{-47\mathrm{/}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\mathrm{/}3$ randomized accuracy barrier under every prescribed finite smoothness order, extending the previously matched third-order case.