  A zeroth-order Hessian estimator aims to recover the Hessian matrix of an
objective function at any given point, using minimal finite-difference
computations. This paper studies zeroth-order Hessian estimation for low-rank
Hessians, from a matrix recovery perspective. Our challenge lies in the fact
that traditional matrix recovery techniques are not directly suitable for our
scenario. They either demand incoherence assumptions (or its variants), or
require an impractical number of finite-difference computations in our setting.
To overcome these hurdles, we employ zeroth-order Hessian estimations aligned
with proper matrix measurements, and prove new recovery guarantees for these
estimators. More specifically, we prove that for a Hessian matrix $H \in
\mathbb{R}^{n \times n}$ of rank $r$, $ \mathcal{O}(nr^2 \log^2 n ) $ proper
zeroth-order finite-difference computations ensures a highly probable exact
recovery of $H$. Compared to existing methods, our method can greatly reduce
the number of finite-difference computations, and does not require any
incoherence assumptions.
