# Efficiently avoiding saddle points with zero order methods: No gradients required

arXiv: https://arxiv.org/abs/1910.13021 · HTML: https://mlsanity.com/paper/1910.13021/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2019.

## Built on by (most cited first, 10 of 10)

- [Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification](https://mlsanity.com/paper/2111.11188/) (2021)
- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption](https://mlsanity.com/paper/2302.07862/) (2023)
- [Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning](https://mlsanity.com/paper/2209.00361/) (2022)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity](https://mlsanity.com/paper/2609.30501/) (2026)

## Abstract (arXiv)

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 tildeO(1 / ε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.