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.

翻译：随机零阶梯度和Hessian估计器：方差降低和精炼偏差边界 我们研究了$\mathbb{R}^n$中实值函数的随机零阶梯度和Hessian估计器。我们表明，通过沿随机正交方向进行有限差分，可以显著减少随机有限差分估计器的方差。特别地，我们设计了平稳函数的估计器，这样，如果使用从Stiefel流形$\text{St}(n,k)$中抽样的$ \Theta \left(k \right) $个随机方向和有限的差分粒度$\delta$，则梯度估计器的方差被界定为$ \mathcal{O}\left(\left(\dfrac{n}{k} - 1\right) + \left(\dfrac{n^2}{k} - n\right)\delta^2 + \dfrac{n^2 \delta^4}{k} \right) $，而Hessian估计器的方差被界定为$\mathcal{O}\left(\left(\dfrac{n^2}{k^2} - 1\right) + \left(\dfrac{n^4}{k^2} - n^2\right)\delta^2 + \dfrac{n^4 \delta^4}{k^2} \right)$。当$k = n$时，方差变得微不足道。此外，我们提供了改进的偏差边界的估计器。平滑函数$f$的梯度和Hessian估计器的偏差是$\mathcal{O}\left(\delta^2 \Gamma\right)$的阶数，其中$\delta$是有限差异的粒度，$\Gamma$取决于$f$的高阶导数。我们的结果通过经验观察得到了证明。