Gradient Testing and Estimation by Comparisons

We study gradient testing and gradient estimation of smooth functions using only a comparison oracle that, given two points, indicates which one has the larger function value. For any smooth f\colon\mathbb R^n\to\mathbb R, x\in\mathbb R^n, and \varepsilon>0, we design a gradient testing algorithm that determines whether the normalized gradient \nabla f(x)/|\nabla f(x)| is \varepsilon-close or 2\varepsilon-far from a given unit vector v using O(1) queries, as well as a gradient estimation algorithm that outputs an \varepsilon-estimate of \nabla f(x)/|\nabla f(x)| using O(n\log(1/\varepsilon)) queries which we prove to be optimal. Furthermore, we study gradient estimation in the quantum comparison oracle model where queries can be made in superpositions, and develop a quantum algorithm using O(\log (n/\varepsilon)) queries.