# Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds

arXiv: https://arxiv.org/abs/2205.14737 · HTML: https://mlsanity.com/paper/2205.14737/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 29 May 2022.

## Builds on (most cited first, 7 of 7)

- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A One-bit, Comparison-Based Gradient Estimator](https://mlsanity.com/paper/2010.02479/) (2020)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [On Sharp Stochastic Zeroth Order Hessian Estimators over Riemannian Manifolds](https://mlsanity.com/paper/2201.10780/) (2022)

## Built on by (most cited first, 7 of 7)

- [FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimation](https://mlsanity.com/paper/2309.17174/) (2023)
- [Convergence Rates of Stochastic Zeroth-order Gradient Descent for L ojasiewicz Functions](https://mlsanity.com/paper/2210.16997/) (2022)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)
- [Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulation](https://mlsanity.com/paper/2602.00075/) (2026)
- [Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling](https://mlsanity.com/paper/2602.13659/) (2026)
- [Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization](https://mlsanity.com/paper/2605.10673/) (2026)
- [Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens](https://mlsanity.com/paper/2605.30960/) (2026)

## Abstract (arXiv)

We study stochastic zeroth order gradient and Hessian estimators for real-valued functions in ℝn. We show that, via taking finite difference along random orthogonal directions, the variance of the stochastic finite difference estimators can be significantly reduced. In particular, we design estimators for smooth functions such that, if one uses  Theta left( k right)  random directions sampled from the Stiefel's manifold  St (n,k)  and finite-difference granularity δ, the variance of the gradient estimator is bounded by  O left( left( fracnk - 1 right) + left( fracn2k - n right) δ2 + frac n2 δ4  k  right) , and the variance of the Hessian estimator is bounded by O left( left( fracn2k2 - 1 right) + left( fracn4k2 - n2 right) δ2 + fracn4 δ4 k2 right) . When k = n, the variances become negligibly small. In addition, we provide improved bias bounds for the estimators. The bias of both gradient and Hessian estimators for smooth function f is of order O left( δ2 Gamma right), where δ is the finite-difference granularity, and  Gamma  depends on high order derivatives of f. Our results are evidenced by empirical observations.