We consider the case of derivative-free algorithms for non-convex
optimization, also known as zero order algorithms, that use only function
evaluations rather than gradients. For a wide variety of gradient approximators
based on finite differences, we establish asymptotic convergence to second
order stationary points using a carefully tailored application of the Stable
Manifold Theorem. Regarding efficiency, we introduce a noisy zero-order method
that converges to second order stationary points, i.e avoids saddle points. Our
algorithm uses only $\tilde{\mathcal{O}}(1 / \epsilon^2)$ approximate gradient
calculations and, thus, it matches the converge rate guarantees of their exact
gradient counterparts up to constants. In contrast to previous work, our
convergence rate analysis avoids imposing additional dimension dependent
slowdowns in the number of iterations required for non-convex zero order
optimization.

本文研究了非凸优化中的无导数算法，利用有限差分器进行梯度逼近，最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法，并在收敛速度上达到了与精确梯度接近的性能。