Zeroth-order optimization. Our work rests on a line of research in zeroth-order optimization which focuses on constructing gradient estimators using zeroth-order function values  [1]}, [2]}, [3]}, [4]}, [5]}. As we have discussed, for smooth nonconvex functions, it is known that two-point zeroth-order estimators suffice to find first-order \(\epsilon \) -stationary points using \(\tilde{O}(d/\epsilon ^2)\)  function evaluations [3]}. Our work studies the more complicated problem of reaching \(\epsilon \) -second order stationary points, attaining a rate of \(\tilde{O}(d/\epsilon ^{2.5})\) .
