Search papers, labs, and topics across Lattice.
This paper addresses the challenge of locating stationary points of non-convex functions using a comparison oracle, which only indicates which of two points has a higher function value. The authors present an algorithm that achieves an $ε$-stationary point with $\widetilde O(n^2/ε^{1.5})$ queries, leveraging a subroutine for estimating the normalized Hessian. Additionally, they introduce a quantum comparison oracle model, yielding a quantum algorithm that finds an $ε$-stationary point with $\widetilde O(n/ε^{1.5})$ queries, marking a significant advancement in optimization techniques.
Finding stationary points in non-convex landscapes can be achieved with significantly fewer queries using a novel quantum approach.
We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $ε$-stationary point using $\widetilde O(n^2/ε^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $δ$ using $\widetilde O(n^2\log(1/δ))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $ε$-stationary point, which takes $\widetilde O(n/ε^{1.5})$ queries.
Stanford HAI