In this paper, we proved that it is possible to use fewer than \(\Omega (d)\)  function evaluations per iteration to escape saddle points and reach approximate second order stationary points efficiently in zeroth-order optimization; in fact, using just two function evaluations per iteration suffices. Along the way, we gave the first analysis of high-probability function change using two(or more)-point zeroth-order gradient estimators, as well as a novel concentration bound for sums of subExponential (but not subGaussian) vectors which are each the products of Gaussian vectors. These technical contributions may be of independent interest to researchers working in zeroth-order optimization as well as general stochastic optimization. There are a few limits of the current results which lead to several interesting future directions, such as extension to noisy function evaluations, as well as studying if some zeroth-order estimators such as asymmetric two-point estimators [1]} or single-point estimators [2]} could actually escape saddle points without additional perturbation noise.
