OpenAlex ·
Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.00275
- Original
- Read it at the publisher
- Topics
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.
More in Artificial Intelligence
Claim-Gated Source-Risk Auditing for Generative Search
Quantum interaction can superactivate cheating under parallel repetition
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Complexity Barriers to State Preparation in Quantum Approximate Optimization
On Kernels and Leaves: Searching for Bare and Lush Trees
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.