The zeroth-order optimization has been widely used in machine learning
applications. However, the theoretical study of the zeroth-order optimization
focus on the algorithms which approximate (first-order) gradients using
(zeroth-order) function value difference at a random direction. The theory of
algorithms which approximate the gradient and Hessian information by
zeroth-order queries is much less studied. In this paper, we focus on the
theory of zeroth-order optimization which utilizes both the first-order and
second-order information approximated by the zeroth-order queries. We first
propose a novel reparameterized objective function with parameters $(\mu,
\Sigma)$. This reparameterized objective function achieves its optimum at the
minimizer and the Hessian inverse of the original objective function
respectively, but with small perturbations. Accordingly, we propose a new
algorithm to minimize our proposed reparameterized objective, which we call
\texttt{MiNES} (mirror descent natural evolution strategy). We show that the
estimated covariance matrix of \texttt{MiNES} converges to the inverse of
Hessian matrix of the objective function with a convergence rate
$\widetilde{\mathcal{O}}(1/k)$, where $k$ is the iteration number and
$\widetilde{\mathcal{O}}(\cdot)$ hides the constant and $\log$ terms. We also
provide the explicit convergence rate of \texttt{MiNES} and how the covariance
matrix promotes the convergence rate.

零阶优化利用零阶查询近似一阶和二阶信息的理论研究较少，本文提出了一种重新参数化的目标函数，通过小干扰在极小值点和原始目标函数的 Hessian 逆之间达到极值，并提出了 MiNES 算法来最小化该目标函数，证明了该算法的协方差矩阵估计收敛至目标函数的 Hessian 矩阵的逆，并给出了收敛速率和协方差矩阵如何促进收敛速率。