Optimization Under Stochastic Evaluation Noise

512 concepts394 papers2 proposals

Classical optimization theory is built on a polite fiction: the existence of an exact oracle. Whether minimizing a loss function or tuning a hyperparameter, we traditionally assume that when we query a point $x$, the environment returns the exact function value $f(x)$ or the exact gradient $\nabla f(x)$.

In the real world, this fiction quickly unravels. When evaluating a machine learning model, we rarely compute the true loss over the entire data distribution; instead, we estimate it using a mini-batch, introducing sampling noise. In self-driving laboratories or physical experiments, evaluations are corrupted by measurement error and environmental variance.

When we replace an exact oracle with a stochastic oracle—where we only observe a noise-corrupted estimate $\hat{f}(x) = f(x) + \epsilon$ or $\hat{g}(x) = \nabla f(x) + \xi$—classical optimization algorithms do not just slow down; they frequently fail entirely. Understanding why this failure occurs, and how we can redesign algorithms to natively tolerate evaluation noise, is a central challenge in modern optimization.

Why Noise Breaks Classical Optimization

To understand why stochastic noise is so destructive, we can look at two pillars of deterministic optimization: line search and acceleration.

In deterministic optimization, line search is used to adaptively choose step sizes. At each iteration, the algorithm proposes a step and checks a descent condition (such as the Armijo rule) to ensure the function value has sufficiently decreased.

When function evaluations are noisy, this comparison becomes a gamble. As noted by Billy Jin et al., mini-batch noise can cause standard step-size selection criteria to fluctuate wildly. If the noise $\epsilon$ is large and positive at the starting point but negative at the proposed destination, the algorithm might accept a step that actually increases the true objective function. Conversely, it might reject perfectly valid descent steps. This insight led Billy Jin et al. to develop ALOE, an adaptive line-search algorithm that replaces deterministic checks with high-probability complexity bounds, ensuring statistical descent even when oracles are biased or noisy. Similarly, El Houcine Bergou et al. demonstrated that using subsampled, noisy data for step-size selection requires careful variance management to prevent the acceptance of destructive updates.

The "Acceleration Tax"

Nesterov’s accelerated gradient methods are famous for achieving the theoretically optimal convergence rate in noiseless environments. They achieve this by maintaining a momentum term that remembers past gradients, allowing the optimizer to slide swiftly through flat regions.

However, momentum is a double-edged sword. If a gradient evaluation is corrupted by noise, that error is not isolated to a single step; it is baked into the momentum term and propagated across subsequent iterations.

Deterministic Gradient Descent:  [Step 1: Exact] -> [Step 2: Exact] -> [Step 3: Exact]
Accelerated Method (Noisy):     [Step 1: Error] -\
                                                 +-> [Step 2: Amplified Error] -> Catastrophic Divergence
                                [Past Momentum] -/

Hesameddin Mohammadi et al. proved that for strongly convex problems, acceleration inherently amplifies stochastic gradient noise by a factor of $\sqrt{\kappa}$, where $\kappa$ is the condition number of the function. This creates a fundamental trade-off between convergence speed and robustness. To counteract this fragility, Jelena Diakonikolas et al. designed AGD+, an accelerated framework that introduces a "restart and slow down" heuristic. By dynamically dumping the accumulated momentum when noise is suspected to dominate the signal, they prevent catastrophic error accumulation while preserving acceleration benefits where possible.

The challenge intensifies in zeroth-order (black-box) optimization, where we cannot compute gradients at all and must rely solely on function value comparisons.

Spurious Peaks in Bayesian Optimization

Bayesian Optimization (BO) navigates black-box landscapes by building a probabilistic surrogate model (like a Gaussian Process) of the objective function. An acquisition function then uses this model to decide where to sample next.

Standard acquisition functions, such as Expected Improvement, are highly vulnerable to observation noise. If the oracle returns a massive, positive noise spike at a suboptimal point, a naive acquisition function might conclude that a hidden peak has been discovered. The algorithm will then repeatedly sample around this spurious peak, wasting expensive evaluations.

To solve this, José Miguel Hernández-Lobato introduced Predictive Entropy Search (PES). Instead of looking for points that maximize the expected value, PES leverages information theory to select points that maximize the expected information gain about the location of the global maximum. Because the location of the optimum is a global property of the distribution, it is inherently more robust to localized vertical noise spikes.

Building on this information-theoretic foundation, Henry B. Moss et al. developed GIBBON, an acquisition function that natively accounts for observation noise by deriving a principled lower bound for information gain, making it both computationally lightweight and resilient to experimental variance.

The Power of Two-Point Estimators

In zeroth-order gradient-free optimization, gradients are typically approximated by sampling the function at multiple nearby points. However, if each function evaluation is itself noisy, how can we reliably estimate a directional derivative?

Zhaolin Ren et al. explored this by analyzing the power of two-point estimators. By injecting isotropic (uniform) random perturbations at each step, the authors demonstrated that zeroth-order algorithms can efficiently escape saddle points using only two function evaluations per iteration, provided the noise budget is tightly bounded. When noise exceeds this budget, ranking-based approaches offer an alternative. As explored by Cedric Malherbe et al., reframing global optimization as a sequence of level-set ranking problems can bypass the need for exact values, though stochastic noise can still flip rankings and require statistical corrections.

The Universal Fix: Transfer Theorems

Given that noise breaks so many classical algorithms, do we need to reinvent every optimization method from scratch?

Phillip A. Kerger et al. answered this with a resounding "no" by proving a Universal Transfer Theorem. They designed a black-box wrapper that sits between a noisy environment and a deterministic optimization algorithm.

+-----------------------------------------------------------------------+
|                       Universal Transfer Wrapper                      |
|                                                                       |
|  [Deterministic Algorithm] <--- Cleaned Signal --- [Noise Filter]     |
|                                                          ^            |
|                                                          |            |
+----------------------------------------------------------|------------+
                                                           |
                                                Noisy Oracle Queries
                                                           |
                                                   [Stochastic World]

By dynamically controlling the accuracy of an inexact first-order oracle—often through adaptive sampling or variance reduction—this wrapper guarantees that any convex optimization algorithm designed for exact data can maintain its convergence guarantees in a stochastic environment. This allows practitioners to deploy highly sophisticated cutting-plane methods or mixed-integer solvers in noisy, real-world settings without altering their underlying mechanics.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 384 papers
  2. Version 1 · 2026-10-04 · 388 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_noisy_objective_functions_5ebb7d5f,
  title = {noisy objective functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/noisy-objective-functions/rdr_5ebb7d5ff28f43cd8c45f83d530cf570},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_noisy_objective_functions_5ebb7d5f_v2,
  title = {noisy objective functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/noisy-objective-functions/rdr_5ebb7d5ff28f43cd8c45f83d530cf570/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake