Due to these difficulties, previous works on escaping saddle points in zeroth-order optimization have exclusively focused on approaches requiring \(\Omega (d)\)  function evaluations per iteration to accurately estimate the gradient [1]}, [2]} or in some cases also the Hessian [3]}, reducing in a sense the zeroth-order problem back to a first-order one. However, from existing works [4]}, for smooth nonconvex functions, we know that two-point zeroth-order estimators suffice to find first-order \(\epsilon \) -stationary points at a rate of \(\tilde{O}(\frac{d}{\epsilon ^2})\) . This raises an important question:
