# Hessian Estimation via Stein's Identity in Black-Box Problems

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2021.

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

- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [SmoothHess: ReLU Network Feature Interactions via Stein's Lemma](https://mlsanity.com/paper/2311.00858/) (2023)
- [Shortcuts for causal discovery of nonlinear models by score matching](https://mlsanity.com/paper/2310.14246/) (2023)
- [Score-matching-based Structure Learning for Temporal Data on Networks](https://mlsanity.com/paper/2412.07469/) (2024)
- [A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization](https://mlsanity.com/paper/2208.00290/) (2022)
- [Optimal estimators of cross-partial derivatives and surrogates of functions](https://mlsanity.com/paper/2407.11035/) (2024)
- [Estimating Multi-chirp Parameters using Curvature-guided Langevin Monte Carlo](https://mlsanity.com/paper/2501.18178/) (2025)
- [Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens](https://mlsanity.com/paper/2605.30960/) (2026)

## Abstract (arXiv)

When the available information is noisy zeroth-order (ZO) oracle, stochastic approximation methods are popular for estimating the root of the multivariate gradient equation. Inspired by the Stein's identity, this work establishes a novel Hessian approximation scheme. We compare it alongside with second-order simultaneous perturbation stochastic approximation (2SPSA). On the basis of the almost sure convergence and the same convergence rate, 2SPSA requires four ZO queries, while ours requires three ZO queries. Moreover, 2SPSA requires two statistically independent perturbations and two differencing stepsizes, while ours requires generating one perturbation vector only and tuning one differencing stepsize only. Besides, the weighting mechanism for the Hessian estimate is generalized and the smoothness restriction on the loss function is relaxed compared to 2SPSA. Finally, we present numerical support for the reduced per-iteration ZO query complexity.