Skip to content
Preprint

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

Sep 2026 · 3 citations · ⚡ 1 influential · 17 references
Mathematics

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;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective gap over the ball by $\Delta$. For neighborhood radius $\delta>0$ and residual tolerance $\varepsilon>0$, our smooth hard family requires $\Omega(dL_0^2\Delta/(\delta\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$, $\Delta\ge C\delta\varepsilon$, and $d\ge C[1+\log(2+\Delta L_0^2/(\delta\varepsilon^3))]$, on a constructed ball of radius $\Theta(\Delta/\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.

View source

Similar papers

Preprint Sep 2026

Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization

We establish a randomized first-order lower bound for finding an $\epsilon$-stationary point, $\|\nabla f(x)\|\le \epsilon$, of a nonconvex function with initial gap at most $\Delta$, $L_1$-Lipschitz gradient, and $L_2$-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let $Q_{\mathrm{r...

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 2 citations · ⚡1
Preprint Oct 2026

Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization

The randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain is characterized, taking the worst case over admissible known dual domains and finite dimensions.

Wen-Dao Wu, Hai-Han Zhang, Qian Chen et al. · 1 citation · ⚡1
#machine learning Preprint Oct 2026

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tilde{\Theta}(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kapp...

Qi-Hao Zhou · 3 citations · ⚡2
Preprint Sep 2026

Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems

We study the query complexity of optimization with exact scalar-value information. For globally $L$-smooth convex functions on $\mathbb R^d$ with a minimizer in a Euclidean ball of radius $R$, we prove the lower bound $\Omega(d\min\{d,\sqrt{LR^2/\varepsilon}\})$ for adaptive randomized algorithms in the stated accuracy...

Y. Dorn, D. Dvinskikh, Т. В. Логінов et al. · 0 citations
Preprint Sep 2026

Dimension-free estimates for the full discrete Euclidean ball maximal function

Let $M_t$ denote the normalized average over the lattice points in the Euclidean ball of radius $t$ in $\mathbb{Z}^d$. We prove that the full maximal operator $f\mapsto\sup_{t\geq0}\lvert M_t f\rvert$ is bounded on $\ell^p(\mathbb{Z}^d)$, for every $1<p\leq\infty$, with a constant independent of the dimension. In parti...

Sheng-Chen Mao · 0 citations
Preprint Sep 2026

Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization

We establish tight randomized higher-order oracle complexity for finding first-order stationary points of nonconvex finite sums. Let $n$ be the number of components, $\Delta>0$ the initial objective-gap bound, $L_p>0$ an individual $p$-th derivative Lipschitz bound, and $\epsilon>0$ the target gradient norm. For every...

Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al. · 2 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.