Comparison to gradient-based methods. For first-order escape saddle point algorithms, standard perturbation-based methods (without acceleration) can find a \(\epsilon \) -second-order stationary point using \(\tilde{O}(1/\epsilon ^2)\)  iterations for deterministic GD [1]}, while for standard SGD the best-known rates are slower at \(\tilde{O}(1/\epsilon ^{3.5})\)  [2]}. In contrast, our sample complexity (as measured by the total number of function evaluations) is \(\tilde{O}\left(\frac{d}{\epsilon ^{2.5}} \right)\) . The extra dependence on \(d\)  is typical for zeroth-order algorithms (see e.g. [3]}); intuitively, gradient calculation for \(d\) -dimensional functions requires \(O(d)\)  calculations agnostically, so it makes sense that zeroth-order algorithms requires \(d\)  times more iterations. Our dependence on \(\epsilon \)  sits between that of the deterministic methods and SGD methods, and suggests the benefit of a specialized treatment of zeroth-order methods over considering them simply as a subclass of SGD methods.
