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

Hongcheng Dong, Wenqiang Pu, Licheng Zhao, Rui Zhou, Feng Yin
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:25980-26006, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-dong26j, title = {Romberg-Extrapolated Zeroth-Order Gradient Estimator: Higher-Order Bias Reduction with Preserved Leading Directional Variance}, author = {Dong, Hongcheng and Pu, Wenqiang and Zhao, Licheng and Zhou, Rui and Yin, Feng}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {25980--26006}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/dong26j/dong26j.pdf}, url = {https://proceedings.mlr.press/v306/dong26j.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Romberg-Extrapolated Zeroth-Order Gradient Estimator: Higher-Order Bias Reduction with Preserved Leading Directional Variance %A Hongcheng Dong %A Wenqiang Pu %A Licheng Zhao %A Rui Zhou %A Feng Yin %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-dong26j %I PMLR %P 25980--26006 %U https://proceedings.mlr.press/v306/dong26j.html %V 306 %X 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.
APA
Dong, H., Pu, W., Zhao, L., Zhou, R. & Yin, F.. (2026). Romberg-Extrapolated Zeroth-Order Gradient Estimator: Higher-Order Bias Reduction with Preserved Leading Directional Variance. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:25980-26006 Available from https://proceedings.mlr.press/v306/dong26j.html.

Related Material