Exact Values Still Require Square-Root Query Complexity

Exact function values appear unusually informative: in an idealized real-number oracle model, one response can in principle carry unlimited information. That creates a technical obstacle for lower bounds in derivative-free optimization, since a deterministic adaptive algorithm might try to encode and recover far more from values than conventional resisting-oracle arguments permit. This paper studies that issue for globally $\beta$-smooth convex objectives over a radius-$R$ Euclidean ball, assuming the unique minimizer lies within radius $R/2$.

The central conclusion is that exact values do not eliminate the familiar square-root dependence on target accuracy. In the moderate-accuracy regime, the paper characterizes deterministic exact-value complexity as $\Theta\!\left(d\sqrt{\beta R^2/\epsilon}\right)$. The result is a clean answer for bounded-query algorithms: the cost of recovering enough directional information remains proportional to dimension, even when oracle responses have infinite numerical precision.

Core Contribution

The paper pairs a direct upper bound with a lower-bound construction designed for exact real-valued transcripts. On the algorithmic side, coordinate finite differences estimate gradients from function evaluations, and an error-tolerant accelerated projected method uses those estimates to optimize the smooth convex objective. This gives an upper bound of $O\!\left(d\sqrt{\beta R^2/\epsilon}\right)$ queries.

The more consequential contribution is the matching lower bound, subject to a high-accuracy saturation term. For every deterministic adaptive value-oracle algorithm, the authors show a requirement of

queries. The square-root branch matches the upper bound over the stated moderate-accuracy interval, rather than merely supplying a dimension-dependent obstruction. That distinction matters: a lower bound that ignored exact-value information could fail because its hard instances might be distinguishable from a single carefully chosen oracle response.

Technical Approach

The hard instance is one fixed smooth convex function rather than an oracle that changes adversarially after each query. The construction starts from a biased max chain and applies Moreau smoothing, preserving convexity and controlled smoothness while making the objective compatible with the value-oracle setting. Its purpose is to reveal progress through a sequence of hidden directions only gradually.

Two mechanisms address adaptivity. Exact prefix shielding keeps the function-value transcript consistent with the portions of the construction that have not yet been revealed. Batched delayed rotations then defer the relevant geometry: queries made before a batch becomes exposed cannot reliably identify the directions that govern later progress. Together, these devices prevent an algorithm from exploiting arbitrary precision to shortcut the chain through encoded information in the scalar values.

This is more specific than a standard zero-chain argument. The proof must establish that one globally defined function remains compatible with the entire adaptive transcript, not just with a finite sequence of locally chosen answers. The construction is therefore aimed at the information-model issue itself, while the finite-difference upper bound shows that no more exotic value-only method is needed to meet the rate.

Results and Analysis

The main quantitative statement holds when $\beta R^2(\log(ed)/d)^{2/3}\leq\epsilon\leq c\beta R^2$ for a universal constant $c>0$. In that interval, the lower bound's square-root term is active and matches the $O\!\left(d\sqrt{\beta R^2/\epsilon}\right)$ upper bound. The paper thus identifies the minimax deterministic complexity, up to constants, rather than only proving that finite differences are sufficient.

Outside that regime, the lower-bound construction saturates at $d(d/\log(ed))^{1/3}$ through its minimum term. This is an explicit boundary on what the presented hard instance establishes at very high accuracy; it should not be read as a full exact characterization there. The result is theoretical, but it sharpens the interpretation of zeroth-order smooth convex optimization: exact arithmetic changes proof techniques, not the moderate-accuracy query rate.

Practitioners designing deterministic derivative-free routines benefit mainly from the negative result. Under these geometric assumptions, efforts to extract substantially more optimization progress from exact scalar evaluations alone face a proved information barrier. Researchers in oracle complexity gain a construction that handles the part conventional adaptive lower-bound templates leave exposed.