Bounds on Query Convergence

Barak A. PearlmutterarXiv 2005 · arXiv

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)$.

Comparison of different query strategies and their cumulative regret over time. The greedy strategy (top right) fails to converge, while the p=2 strategy (bottom left) achieves the optimal sublinear regret growth.

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

Abstract

The problem of finding an optimum using noisy evaluations of a smooth cost function arises in many contexts, including economics, business, medicine, experiment design, and foraging theory. We derive an asymptotic bound E[ (x_t - x*)^2 ] >= O(1/sqrt(t)) on the rate of convergence of a sequence (x_0, x_1, >...) generated by an unbiased feedback process observing noisy evaluations of an unknown quadratic function maximised at x*. The bound is tight, as the proof leads to a simple algorithm which meets it. We further establish a bound on the total regret, E[ sum_{i=1..t} (x_i - x*)^2 ] >= O(sqrt(t)) These bounds may impose practical limitations on an agent's performance, as O(eps^-4) queries are made before the queries converge to x* with eps accuracy.
BibTeX
@misc{pearlmutter2005bounds,
  author = {Barak A. Pearlmutter},
  title = {{Bounds on Query Convergence}},
  year = {2005},
  eprint = {cs/0511088},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0511088},
}
Figure