{"id":"arxiv/2610.22208","url":"https://arxiv.org/abs/2610.22208","tags":["math.OC"],"score":0,"title":"Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We establish matching lower bounds for the tradeoff between gradient and Hessian queries in nonconvex optimization with Lipschitz Hessian. In normalized units, the initial objective gap is at most $T$, the Hessian Lipschitz constant is at most one, and the target gradient norm is one. For sufficiently large $T$, dimension $d \\ge C\\log(2+T)$, and a prescribed Hessian budget $h \\ge 1$ with $h+1 \\le aT$, every randomized algorithm requires $Ω(\\min\\{Td^{1/3}, T^{3/2}/\\sqrt{h+1}\\})$ ordinary queries. An ordinary query returns the value and gradient; a Hessian query returns the complete second jet…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}