Finding Stationary Points by Comparisons

arXiv:2606.27082v1 Announce Type: new 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 folonmathbb R^nomathbb R with Lipschitz gradient and Hessian, we develop an algorithm that visits an epsilon-stationary point using widetilde O(n^2/epsilon^{1.5}) queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy elta using widetilde O(n^2log(1/elta)) 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 widetilde O(n/epsilon^{1.5}) queries.

Source: arXiv cs.LG | 2026-06-26