Zeroth-order methods, which refer to algorithms that optimize a function using only function evaluations, are an important tool in solving black-box optimization tasks and reinforcement learning problems in unknown environments. While zeroth-order optimization takes many forms [1]}, [2]}, a common approach is to utilize function values to build stochastic estimates of the gradients [3]}, [4]}, [5]}, [6]}, which is also the approach we will study. In many applications of zeroth-order optimization, the underlying function may be nonconvex. For nonconvex functions, under various smoothness and Lipschitz assumptions on the function, existing works have studied the convergence of zeroth-order methods to first-order stationary points [5]}. Since finding globally optimal solutions in non-convex optimization is NP-hard, seeking first-order stationary points is a reasonable starting point for theoretical analysis. However, the presence of possible saddle points for nonconvex functions means that merely converging to first-order stationary points is insufficient. Ideally, we would like that zeroth-order methods can evade such saddle points, and instead find second-order stationary points.
