Abstract
This paper establishes fundamental limits on the rate at which queries can converge to an optimum in gradient-free optimization with noisy feedback. We prove that for locally quadratic functions, the expected squared error of queries is lower bounded by $O(t^{-1/2})$, a significantly slower rate than the $O(t^{-1})$ possible with gradient information. This limitation arises from a "leverage" trade-off: rapid convergence reduces the spatial spread of data points, thereby degrading the precision of the optimum's estimate. We demonstrate that a greedy approach fails to converge, while an optimal strategy injecting noise proportional to the estimation error variance achieves the theoretical bound.
Introduction
In many real-world optimization scenarios, such as determining optimal drug dosages or setting business prices, we lack direct gradient information. Instead, we must rely on noisy evaluations of a function $f(x)$. The objective is not merely to identify the optimum $x^*$ eventually, but to ensure that the sequence of queries $x_t$ converges to $x^*$ as rapidly as possible to minimize cumulative loss, or "regret."
Barak Pearlmutter addresses a fundamental question in this domain: What is the maximum achievable rate of convergence for these queries? The findings suggest that the cost of certainty is higher than intuition might suggest, with a hard physical limit imposed by the statistical nature of the feedback.
Theoretical Framework
The analysis assumes a locally quadratic objective function, $f(x) \approx a(x-x^*)^2 + b(x-x^*) + c$, which is a standard approximation for smooth functions near their peak. The feedback received is $y_t = f(x_t) + \epsilon_t$, where $\epsilon_t$ is zero-mean noise with variance $\sigma^2$.
The core of the proof utilizes the Cramér-Rao bound, which relates the variance of an estimator to the Fisher information. In this context, "leverage"—the spatial spread of the queries $x_t$—is the primary driver of information gain. If queries converge too quickly to a single point, the leverage vanishes, and the ability to accurately estimate the location of the optimum $x^*$ is compromised. This creates a fundamental "catch-22": to know where the optimum is, you must sample away from it; but to minimize regret, you want to sample at it.
The Fundamental Bound on Convergence
The paper derives a lower bound on the expected squared distance of the query from the optimum:
$$E[(x_t - x^*)^2] \geq O(t^{-1/2})$$
This implies that the total regret $R_t$, representing the cumulative loss over time, grows at least as $O(t^{1/2})$. This $t^{-1/2}$ wall is significantly more restrictive than the $t^{-1}$ rates often seen in deterministic or gradient-based optimization. Practically, this means that achieving a tenfold increase in precision requires a hundredfold increase in the number of samples.
Simulation and Strategy Validation
To validate these theoretical bounds, the author simulated various query strategies with different levels of "aggression" in convergence. These strategies are characterized by a parameter $p$, where noise is injected into the query based on the current estimate's standard error: $x_t = \hat{x}_t^* + \mathcal{N}((\text{stderr } \hat{x}_t^*)^p)$.
As shown in the simulations, a greedy strategy ($x_t = \hat{x}_t^*$) is catastrophic. Because it stops exploring, it quickly loses the leverage needed to correct initial estimation errors, leading to linear regret growth as it converges to a non-optimal point with probability one. Conversely, the strategy with $p=2$—where query variance scales with the square of the estimation error—is shown to be optimal, meeting the derived theoretical bounds.
Discussion and Implications
A surprising result of this work is that the bound on total regret is independent of the curvature ($a$) of the peak. Whether the function is a sharp spike or a broad dome, the fundamental difficulty of the noisy search remains identical.
These findings have broad implications across fields. In biology, the necessity of maintaining query variance might explain the persistence of high variability in systems like sexual selection. In economics, it suggests that a certain level of "noise" or experimentation is not just a byproduct of imperfection but a requirement for long-term optimization. Future work may explore how Bayesian priors or non-quadratic function shapes alter these asymptotic rates, though the fundamental leverage constraint is expected to persist.
Summary updated