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:\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that outputs 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 $\delta$ using $\widetilde O(n^2\log(1/\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 $\widetilde O(n/\epsilon^{1.5})$ queries.

How fast can we find a near minimum point of a function when we can only compare the function values at two given points? We wondered if we can achieve our goal through accessing the direction of the gradient and the Hessian and applying known algorithms. Our paper presents a well performance optimization algorithm that visits an alternative of minimum point — a point with tiny gradient, which means that it achieves "balance" on this function. Our algorithm can approximately compute the direction of Hessian and reduce the function value step by step through using a quadratic (certainly the "direction" of this quadratic) to approximate the function and minimizing it in every step. By reducing the function value in each step, we can find our target point when there is no space to reduce. Our findings have implications for providing an algorithm faster in dependence of precision requirement (despite slower in dimension requirement, which is inevitable), thus providing a trade-off when choosing optimization algorithm in many machine learning problems.