{"id":"arxiv/2610.17074","url":"https://arxiv.org/abs/2610.17074","tags":["math.OC"],"score":0,"title":"Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization","domain":"math.OC","source":"arxiv","authors":["Haihan Zhang","Wendao Wu","Fangqing Zhang","Chenheng Zhang","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"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\\ge3$, finding an $\\eps$-stationary point requires $Ω_p(\\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\\infty$ objectives with initial gap at most one and simultaneous global Lipschitz budgets of one for derivatives of orders $1,\\ldots,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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}