  Two-point zeroth order methods are important in many applications of
zeroth-order optimization, such as robotics, wind farms, power systems, online
optimization, and adversarial robustness to black-box attacks in deep neural
networks, where the problem may be high-dimensional and/or time-varying. Most
problems in these applications are nonconvex and contain saddle points. While
existing works have shown that zeroth-order methods utilizing $\Omega(d)$
function valuations per iteration (with $d$ denoting the problem dimension) can
escape saddle points efficiently, it remains an open question if zeroth-order
methods based on two-point estimators can escape saddle points. In this paper,
we show that by adding an appropriate isotropic perturbation at each iteration,
a zeroth-order algorithm based on $2m$ (for any $1 \leq m \leq d$) function
evaluations per iteration can not only find $\epsilon$-second order stationary
points polynomially fast, but do so using only
$\tilde{O}\left(\frac{d}{m\epsilon^{2}\bar{\psi}}\right)$ function evaluations,
where $\bar{\psi} \geq \tilde{\Omega}\left(\sqrt{\epsilon}\right)$ is a
parameter capturing the extent to which the function of interest exhibits the
strict saddle property.
