{"id":"arxiv/2610.00275","url":"https://arxiv.org/abs/2610.00275","tags":["math.OC"],"score":0,"title":"Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls","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 prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\\mathbb{E}[F(\\cdot;ξ)]$, assume $\\mathbb{E}[\\operatorname{Lip}(F(\\cdot;ξ))^2]\\le L_0^2$, and bound the initial objective gap over the ball by $Δ$. For neighborhood radius $δ>0$ and residual tolerance $\\varepsilon>0$, our smooth hard family requires $Ω(dL_0^2Δ/(δ\\varepsilon^3))$ scalar evaluations for success probability $1/2$, against randomized adaptive algorithms that may retain and repeatedly…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}