Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls

@misc{zhang2026joint,
  title = {{Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls}},
  author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00275},
  eprint = {2610.00275},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00275},
}

TY  - UNPB
TI  - Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
AU  - Haihan Zhang
AU  - Wendao Wu
AU  - Chenheng Zhang
AU  - Yanyi Li
AU  - Chunyuan Zheng
AU  - Cong Fang
AU  - Haoxuan Li
AU  - Zhouchen Lin
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.00275
UR  - https://arxiv.org/abs/2610.00275
AB  - 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=𝔼[F(·;ξ)], assume 𝔼[Lip(F(·;ξ))^2]≤ L_0^2, and bound the initial objective gap over the ball by Δ. For neighborhood radius δ>0 and residual tolerance ε>0, our smooth hard family requires Ω(dL_0^2Δ/(δε^3)) scalar evaluations for success probability 1/2, against randomized adaptive algorithms that may retain and repeatedly query each sampled function. The result holds for ε≤ cL_0, Δ≥ Cδε, and d≥ C[1+log(2+ΔL_0^2/(δε^3))], on a constructed ball of radius Θ(Δ/ε). A sequence of localized regions forces repeated direction estimation, and an adaptive Gaussian posterior argument controls sample reuse. The result establishes a joint dimension and accuracy obstruction on solvable bounded-domain instances. The gap is local to the query ball; a matching minimax characterization at a common radius and the corresponding unrestricted global-gap lower bound remain open here.
ER  -