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 $\mathbb{R}^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 $ \text{St}
(n,k) $ and finite-difference granularity $\delta$, the variance of the
gradient estimator is bounded by $ \mathcal{O} \left( \left( \frac{n}{k} - 1
\right) + \left( \frac{n^2}{k} - n \right) \delta^2 + \frac{ n^2 \delta^4 }{ k
} \right) $, and the variance of the Hessian estimator is bounded by
$\mathcal{O} \left( \left( \frac{n^2}{k^2} - 1 \right) + \left( \frac{n^4}{k^2}
- n^2 \right) \delta^2 + \frac{n^4 \delta^4 }{k^2} \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 $\mathcal{O} \left( \delta^2 \Gamma \right)$, where
$\delta$ is the finite-difference granularity, and $ \Gamma $ depends on high
order derivatives of $f$. Our results are evidenced by empirical observations.