# Escaping saddle points in zeroth-order optimization: the power of two-point estimators

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2022.

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

- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Stochastic Two Points Method for Deep Model Zeroth-order Optimization](https://mlsanity.com/paper/2402.01621/) (2024)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [D-IMPL: A Diffusion-based Solver for Parameterized BBOs](https://mlsanity.com/paper/2609.22752/) (2026)
- [To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity](https://mlsanity.com/paper/2609.30501/) (2026)

## Abstract (arXiv)

Two-point zeroth order methods are important in many applications of zeroth-order optimization, such as robotics, wind farms, power systems, online optimization, and adversarial robustness to black-box attacks in deep neural networks, where the problem may be high-dimensional and/or time-varying. Most problems in these applications are nonconvex and contain saddle points. While existing works have shown that zeroth-order methods utilizing Omega(d) function valuations per iteration (with d denoting the problem dimension) can escape saddle points efficiently, it remains an open question if zeroth-order methods based on two-point estimators can escape saddle points. In this paper, we show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based on 2m (for any 1 ≤ m ≤ d) function evaluations per iteration can not only find ε-second order stationary points polynomially fast, but do so using only tildeOleft(fracdmε2barpsiright) function evaluations, where barpsi ≥ tildeOmegaleft(√εright) is a parameter capturing the extent to which the function of interest exhibits the strict saddle property.