{"id":"arxiv/2610.00245","url":"https://arxiv.org/abs/2610.00245","tags":["math.OC"],"score":0,"title":"Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization","domain":"math.OC","source":"arxiv","authors":["Haihan Zhang","Wendao Wu","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We establish a randomized first-order lower bound for finding an $ε$-stationary point, $\\|\\nabla f(x)\\|\\le ε$, of a nonconvex function with initial gap at most $Δ$, $L_1$-Lipschitz gradient, and $L_2$-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let $Q_{\\mathrm{rand},\\mathrm{FO}}^{\\infty}(ε;Δ,L_1,L_2)$ denote the minimax number of calls, maximized over finite dimensions, for arbitrary adaptive randomized algorithms with per-instance success probability at least $2/3$. In the regime $ε\\lesssim L_1^2/L_2$ and $ΔL_2^{1/2}ε^{-3/2}\\gtrsim 1$, we prove $…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}