Skip to main content
Article
Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients
Advances in Neural Information Processing Systems
  • Hualin Zhang, Nanjing University of Information Science & Technology
  • Huan Xiong, Harbin Institute of Technology & Mohamed bin Zayed University of Artificial Intelligence
  • Bin Gu, Nanjing University of Information Science & Technology & Mohamed bin Zayed University of Artificial Intelligence
Document Type
Conference Proceeding
Abstract

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.

Publication Date
11-1-2022
Comments

Available in NeurIPS Proceedings site

Citation Information
H. Zhang, H. Xiong, and B. Gu, "Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients", in 36th Conference on Neural Information Processing Systems, NeurIPS 2022, Advances in Neural Information Processing Systems, vol 35, Nov 2022. https://proceedings.neurips.cc/paper_files/paper/2022/file/fa5ddd6bac0d665c72969d79221b680a-Paper-Conference.pdf