Finding Stationary Points by Comparisons

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.