Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent

2019/10/03 by Qinbo Bai, Bai, Qinbo, Mridul Agarwal +3
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1910.01277

openalex publication_date 2019/10/03 · openalex created_date 2019/10/10 · openalex updated_date 2026/07/28

Abstract

Gradient descent and its variants are widely used in machine learning. However, oracle access of gradient may not be available in many applications, limiting the direct use of gradient descent. This paper proposes a method of estimating gradient to perform gradient descent, that converges to a stationary point for general non-convex optimization problems. Beyond the first-order stationary properties, the second-order stationary properties are important in machine learning applications to achieve better performance. We show that the proposed model-free non-convex optimization algorithm returns an ε-second-order stationary point with \widetildeO(\fracd^2+\fracθ2ε^8+θ) queries of the function for any arbitrary θ>0.

Citations

• Evolution Strategies as a Scalable Alternative to Reinforcement Learning

Related

• Escaping Saddle Points with the Successive Convex Approximation Algorithm
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Escape saddle points by a simple gradient-descent based algorithm
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• How to Escape Saddle Points Efficiently