Zeroth-OrderNegativeCurvatureFinding: Escaping SaddlePointswithoutGradients

Several classical results have shown that, forρ-Hessian Lipschitz functions (see Definition 1), using the second-order information like computing the Hessian [33] or Hessian-vector products [1, 9, 2], one can find anϵ-approximate second-order stationary point (SOSP, f(x) ϵ and 2f(x) ρϵI).