Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients
This addresses a gap in zeroth-order optimization for nonconvex problems, offering incremental improvements in efficiency for applications where gradient information is unavailable.
The paper tackles the problem of escaping saddle points in nonconvex optimization using only function evaluations, proposing two zeroth-order negative curvature finding frameworks that reduce query complexity for convergence to approximate second-order stationary points.
We consider escaping saddle points of nonconvex problems where only the function evaluations can be accessed. Although a variety of works have been proposed, the majority of them require either second or first-order information, and only a few of them have exploited zeroth-order methods, particularly the technique of negative curvature finding with zeroth-order methods which has been proven to be the most efficient method for escaping saddle points. To fill this gap, in this paper, we propose two zeroth-order negative curvature finding frameworks that can replace Hessian-vector product computations without increasing the iteration complexity. We apply the proposed frameworks to ZO-GD, ZO-SGD, ZO-SCSG, ZO-SPIDER and prove that these ZO algorithms can converge to $(ε,δ)$-approximate second-order stationary points with less query complexity compared with prior zeroth-order works for finding local minima.