Quantum algorithm for finding the negative curvature direction in non-convex optimization
arXiv:1909.07622
Abstract
We present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is the 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) /ε), 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 /\sqrtε). 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.
arXiv comment29 pages, 2 figures
References in corpus (9)
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- Quantum fingerprinting
- The Loss Surfaces of Multilayer Networks
- Quantum singular value decomposition of non-sparse low-rank matrices
- Gradient Descent Happens in a Tiny Subspace
- Quantum Recommendation Systems
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- From linear combination of quantum states to Grover's searching algorithm