Romberg-Extrapolated Zeroth-Order Gradient Estimator: Higher-Order Bias Reduction with Preserved Leading Directional Variance

Zeroth-order optimization is widely used when gradients are unavailable, but the standard two-point estimator suffers from $\mathcal{O}(r^2)$ truncation bias at smoothing radius $r$. Existing bias-reduction schemes typically increase the leading directional variance under a fixed number of function evaluations per gradient estimate, while variance-reduction schemes generally do not improve the bias order. We propose Romberg-ZOGE, which forms a Romberg-extrapolated linear combination of two-point differences evaluated at radii $\{r/2^k\}_{k=0}^R$ while reusing the same perturbation direction across all radii. With appropriately chosen weights, Romberg-ZOGE cancels the first $R$ even-order truncation terms and achieves $\mathcal{O}(r^{2R+2})$ bias under $(2R{+}2)$-order smoothness, while preserving the leading directional variance constant of the two-point estimator up to higher-order residual terms. We further characterize the stochastic-oracle setting by deriving an explicit noise-amplification factor and corresponding bias and variance bounds. Experiments on synthetic benchmarks, simulator-based wireless optimization, and black-box prompt tuning of OPT-1.3B demonstrate faster and more stable zeroth-order SGD when the number of function evaluations per gradient estimate is fixed.

Many machine learning and engineering problems require optimizing an objective function when gradients are unavailable, expensive, or impossible to compute. In such cases, one can estimate a gradient only by querying the function value at carefully chosen nearby points. However, existing zeroth-order gradient estimators usually improve only one side of the problem: some methods reduce finite-difference bias but increase directional variance, while others reduce variance but keep the same bias order. This paper proposes Romberg-ZOGE, a new zeroth-order gradient estimator that uses Romberg extrapolation to combine several finite-difference estimates at different smoothing radii. By reusing the same random direction across these radii, the method cancels low-order finite-difference bias while preserving the leading directional variance of the standard two-point estimator. In simple terms, the estimator obtains a more accurate gradient approximation without increasing the main source of randomness caused by the search direction. We provide theoretical guarantees showing that Romberg-ZOGE achieves higher-order bias reduction and characterize its behavior under both exact and noisy function evaluations. We also demonstrate its effectiveness on synthetic optimization problems, wireless-network optimization, and black-box prompt tuning for large language models. These results suggest that higher-order zeroth-order gradient estimation can improve optimization efficiency in black-box settings where gradients are not directly accessible.