Global Joint Lower Bounds for Zeroth-Order Nonconvex Optimization: Closing an Open Problem

Why Zeroth-Order Optimization Needs a "Tight" Lower Bound

Zeroth-order optimization forces algorithms to find minima using only function values—not gradients—which is extremely common in black-box parameter tuning, reinforcement learning policy search, and simulation optimization where gradients are unavailable. A natural approach is to turn function values into gradient estimates using finite differences or Gaussian smoothing, then apply the convergence guarantees of first-order methods. But this "transplant" usually comes at a cost that scales linearly with the dimension d.

The question then arises: is this d cost intrinsic, or just an artifact of loose analysis? More sharply: when the objective is nonconvex, only a Goldstein stationary point is sought, and high accuracy is required, can the complexity simultaneously achieve optimal dependence on dimension d, stationarity precision δ, and error ε? Prior work has separately shown that the dependence on d and the first-order dependence on (δ, ε) are each unavoidable, but a "joint" lower bound tying the three together has been missing.

A Goldstein stationary point is a notion of approximate optimality in nonconvex optimization. For a smooth function (f), a point (x) is called a (\delta)-stationary point (also known as a first-order stationary point) if (|\nabla f(x)| \le \delta). But in nonsmooth settings the gradient may not exist, and the Goldstein stationary point is defined via the norm of the gradient mapping: the supremum of (|\nabla f(x)| = |x - \text{prox}_{\eta f}(x)|/\eta) does not exceed (\delta). It is more robust than a simple subgradient bound and provides a computable stopping criterion for nonsmooth, nonconvex problems. Therefore, when the paper discusses "finding a Goldstein stationary point," it is in fact providing a unified notion of approximate solution for a large class of nonsmooth nonconvex problems, and using this as the target metric for complexity—which is also why the lower bound can involve both (\delta) and (\varepsilon).

The Gap Left by Prior Work

According to the Kornowski (2024) result cited in the paper, nonsmooth nonconvex optimization can be solved within a zeroth-order oracle complexity of (\mathcal{O}(d\delta^{-1}\varepsilon^{-3})), and the authors at the time raised the question: is this complexity jointly optimal in its dependence on (d, δ, ε)?

Broken down, two parts are already clear: the dimension dependence is unavoidable; and the first-order dependence on (δ, ε) is also unavoidable. What is missing is a zeroth-order lower bound that simultaneously matches all three. The difficulty in filling this gap lies in the fact that zeroth-order algorithms have too much "freedom"—they can query at arbitrary points, adaptively select samples, reuse the same sampling function at multiple locations, and impose no spatial restriction on the output point. Lower bounds derived under assumptions such as "restricting the query region" or "each evaluation uses fresh noise" simply cannot cover this fully adaptive, reusable scalar oracle.

Zeroth-order oracle complexity measures the minimum number of queries an algorithm needs to reach a given accuracy when it can only query function values. A zeroth-order oracle receives a point (x) and a random seed, and returns a noisy function value (f(x) + \xi). The algorithm's query strategy can be adaptive: it decides the next query point based on all previous query results, and can even reuse the same random sampling function (such as a Gaussian vector) at multiple points to construct finite-difference gradient estimates. This full adaptivity renders traditional lower-bound techniques (such as restricting the query region or assuming each query is independent and identically distributed) ineffective. Therefore, a lower bound established under this model must account for the preservation of information under adaptive reuse—which is precisely the most challenging part of the paper's proof.

What This Paper Does

The paper answers this open question in an unrestricted, full-space setting, with two core conclusions.

Smooth Stochastic Nonconvex: A Scalar Oracle Lower Bound

Under the assumptions that the objective function is smooth, the population objective has a global lower bound, and the sample Lipschitz constant has a bounded second moment, the paper gives the following scalar oracle lower bound:

[ \Omega!\left(\frac{dL_0^2\min{\Delta H,,L_0^2}}{\varepsilon^4}\right) ]

This bound is linear in (d) and scales as (\varepsilon^{-4}) in accuracy.

Minimax optimality is a theoretical benchmark for measuring algorithm performance: for a given problem class, an algorithm is said to be minimax optimal if its worst-case complexity matches the lower bound achievable by any algorithm (up to constant factors). The paper proves joint minimax optimality in (d, δ, ε), meaning that no zeroth-order algorithm can improve the worst-case dependence on dimension (d), stationarity precision (\delta), and error (\varepsilon) simultaneously. In other words, (\Omega(dL_0^2\min{\Delta H, L_0^2}/\varepsilon^4)) and the corresponding Goldstein stationary point lower bound are tight, delineating an insurmountable complexity boundary for this class of problems.

A Smooth Reduction to Goldstein Stationary Points

The authors use a smooth reduction to convert the above result into a lower bound for Goldstein stationary points, thereby proving joint minimax optimality in (d, δ, ε) under explicit high-dimensional, small-precision conditions. This is precisely the gap left by prior work.

It is worth emphasizing the algorithm model to which the lower bound applies: the algorithm can query arbitrary points in (\mathbb{R}^d), adaptively choose sample functions, reuse the same sampling function at arbitrarily many locations, and the output point is also not spatially constrained. In other words, it covers a fully adaptive, reusable-sample scalar oracle, which is strictly stronger than lower bounds that rely on a bounded query region or fresh noise. The paper also separately provides a noiseless, exact-value lower bound that holds for randomized algorithms, and therefore also for deterministic methods.

The Proof Route: Why "Full Adaptivity" Makes Lower Bounds Harder

To prove such a lower bound, one needs the information-theoretic hardness to persist under adaptive reuse. The paper's proof combines several tools: a globally defined sequential nonconvex construction, an exact Gaussian scalar channel, multi-stage random field estimation, and a dual finite-sample implementation—the latter ensures that information hardness does not decay when samples are adaptively reused.

This also explains why the result is meaningful: many lower bounds simplify the analysis by restricting the query region or requiring independent fresh noise, yet real-world zeroth-order methods precisely fail to satisfy these conditions. This paper relaxes the assumptions to nearly no restrictions, and the conclusion still holds, meaning that the linear-in-(d) cost is not an analytical defect but a structural cost of the problem itself.

What This Means for Practitioners

If you are designing zeroth-order methods, the direct implication of this result is: do not expect to eliminate the linear dependence on dimension d through cleverer query strategies or sample reuse; in the nonconvex, high-dimensional, small-precision regime, the goal is to find an algorithm that is linear in (d) and close to (\varepsilon^{-4}) in accuracy—not to dream of sublinear dimension.

A secondary implication lies in the coupling between δ and ε: since the joint lower bound shows that the dependences of the three cannot be optimized in a decomposable manner, algorithmic design trade-offs should focus on how to improve constants and practical sample-reuse efficiency, rather than trying to break through the product structure of the three in worst-case guarantees. For scenarios such as black-box parameter tuning and simulation optimization that rely on zeroth-order optimization, this provides a clear reference for the performance ceiling.

One-line Summary

The paper establishes a joint lower bound for zeroth-order nonconvex optimization over dimension, accuracy, and stationarity, and proves its minimax optimality.

Paragraph Summary

Addressing the open joint lower bound problem in zeroth-order nonconvex optimization, this paper proves a complexity lower bound of Ω(dL₀²min{ΔH,L₀²}/ε⁴) for smooth stochastic nonconvex objectives under a scalar oracle model that allows fully adaptive queries and sample reuse, and obtains a lower bound for Goldstein stationary points via a smooth reduction—thereby for the first time simultaneously matching the dependence on dimension d, stationarity precision δ, and error ε, confirming the (d, δ, ε) joint minimax optimality proposed by Kornowski (2024). The proof combines a global sequential construction, an exact Gaussian scalar channel, multi-stage random field estimation, and a dual finite-sample implementation to ensure that information hardness does not decay under adaptive reuse. The conclusion shows that the linear dependence of zeroth-order optimization on dimension is structural and cannot be eliminated by cleverer query strategies.