2022/10/04 by Hualin Zhang, Huan Xiong, Zhang, Hualin +3 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2210.01496
openalex publication_date 2022/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.