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 second-order 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 modelfree non-convex optimization algorithm returns an epsilon-second-order stationary point with (O) over tilde (d(2+theta/2)/epsilon(8+theta)) queries of the function for any arbitrary theta > 0.