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\text{\hspace{0.17em}⁣}:{\mathbb{R}}^n\to \mathbb{R}$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $\epsilon$-stationary point using $\tilde{O}(n^2\mathrm{/}{\epsilon }^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $\delta$ using $\tilde{O}(n^2\log (1\mathrm{/}\delta ))$ 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 $\epsilon$-stationary point, which takes $\tilde{O}(n\mathrm{/}{\epsilon }^{1.5})$ queries.