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

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.