Managing Bias in Zeroth Order Optimization

This direction is merged into another direction: black-box optimization. Its last version stays readable and citable here.

Version 1 of 117 papers21 conceptsfrozen 2026-10-04

In many real-world scenarios, we are tasked with optimizing a "black box" function—a system where we can observe the output for a given input, but we have no access to the underlying analytical formula or its gradients. This is the domain of Zeroth-Order (ZO) Optimization. While first-order methods like Gradient Descent use a "compass" (the gradient) to find the steepest descent, ZO methods must construct an artificial compass by probing the function at nearby points.

The fundamental challenge in this field is that these artificial compasses are almost always slightly "off." This systematic error, known as bias, is the primary hurdle to achieving the speed and accuracy of traditional gradient-based methods.

The Origin of Bias

In first-order optimization, we assume we have access to an unbiased stochastic gradient. Even if it's noisy, it points in the correct direction on average. In contrast, Sijia Liu and Pin-Yu Chen explain in Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization that ZO gradient estimates are derived from finite differences. Because these differences only approximate the derivative over a non-zero distance (the perturbation step size), they introduce a persistent bias.

This bias creates a tension:

  1. Numerical Stability: If the perturbation step is too small, computer rounding errors (noise) overwhelm the signal.
  2. Accuracy: If the step is too large, the approximation deviates significantly from the true gradient, as noted by Shaocong Ma and Heng Huang in On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization.

The Convergence Floor

The most visible consequence of bias is the "error floor." In standard gradient descent, you can theoretically reach the exact minimum. In ZO optimization, the bias often prevents the algorithm from ever reaching the true optimum. Instead, the optimizer gets "stuck" in a neighborhood around the solution.

Aleksandr Lobanov and Alexander Gasnikov demonstrate that this floor is determined by the smoothness of the function and the noise in the evaluations. Their work on Highly Smoothness Zero-Order Methods suggests that by using kernel-based estimators that exploit higher-order smoothness, we can push this floor much lower, allowing for more precise solutions.

Bridging the Gap with Variance Reduction

To make ZO methods as fast as first-order methods, researchers have attempted to adapt Variance Reduction (like SVRG or SAGA). These techniques are designed to "cancel out" the noise of stochastic sampling to accelerate convergence.

However, Feihu Huang and Bin Gu highlight a critical problem: variance reduction algorithms typically assume the gradient estimates are unbiased. When applied to biased ZO estimates, the "correction" step can actually amplify errors. In Faster Gradient-Free Proximal Stochastic Methods, they show that achieving a fast $O(1/T)$ convergence rate requires carefully managing this bias, often by using larger mini-batches or more random directions than would be necessary in the first-order world.

Beyond Optimization: The Inference Problem

Bias doesn't just slow down optimization; it also breaks our ability to perform statistical inference. If you want to know the "confidence interval" of your result—how sure you are that you've found the best setting—bias is your enemy.

Zeyu Zheng and Yingfei Wang point out in Joint Optimization and Statistical Inference for Zero-th Order Simulation Optimization that standard ZO algorithms produce estimators that do not follow a normal distribution. Without specific mechanisms to cancel out lower-order bias terms (such as their proposed four-point sampling), any confidence intervals calculated from the results are mathematically invalid.

New Frontiers: Unbiased Estimators and Sample Reuse

The field is currently moving toward two extremes to solve the bias problem:

  • Eliminating Bias: Shaocong Ma has proposed using telescoping series tricks to create truly unbiased ZO estimators, potentially removing the "error floor" entirely.
  • Efficiency through Interpolation: Xiaoxing Wang and Junchi Yan introduced ReLIZO, which uses linear interpolation and sample reuse. By treating gradient estimation as a geometric problem rather than a simple difference, they can achieve high accuracy with far fewer function queries.

By understanding and mitigating the inherent bias of finite-difference approximations, these researchers are turning "black-box" optimization from a slow, approximate tool into a rigorous and efficient framework for modern machine learning.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_managing_bias_in_zeroth_order_optimizati_d4c514bc,
  title = {Managing Bias in Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/managing-bias-in-zeroth-order-optimization/rdr_d4c514bc80c2430ca2e4cd1a9452437f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_managing_bias_in_zeroth_order_optimizati_d4c514bc_v1,
  title = {Managing Bias in Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/managing-bias-in-zeroth-order-optimization/rdr_d4c514bc80c2430ca2e4cd1a9452437f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}