  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.
