OpenAlex ·

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

Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li and Zhouchen Lin

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.00275
Original
Read it at the publisher
Topics
Artificial IntelligenceComputational ComplexityNumerical Analysis

Abstract

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 query each sampled function. The result holds for $\varepsilon\le cL_0$, $Δ\ge Cδ\varepsilon$, and $d\ge C[1+\log(2+ΔL_0^2/(δ\varepsilon^3))]$, on a constructed ball of radius $Θ(Δ/\varepsilon)$. 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics