Finding Stationary Points by Comparisons

Abstract

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

41 pages, 4 figures. To appear in the Forty-Third International Conference on Machine Learning (ICML 2026)