Quantum Algorithm for Finding the Negative Curvature Direction

Abstract

Non-convex optimization is an essential problem in the field of machine learning. Optimization methods for non-convex problems can be roughly di- vided into first-order methods and second-order methods, depending on the or- der of the derivative to the objective function they used. Generally, to find the local minima, the second-order methods are applied to find the effective direction to escape the saddle point. Specifically, finding the Negative Curvature is considered as the subroutine to analyze the characteristic of the saddle point. However, the calculation of the Negative Curvature is expensive, which prevents the practical usage of second-order algorithms. In this thesis, we present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity O ̃(polylog(d) ε^(-1)), where d is the dimension of the optimization function. The quantum negative curvature finding algorithm is exponentially faster than any known classical method, which takes time at least O(dε^(-1/2)). Moreover, we propose an efficient quantum algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.