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\text{\hspace{0.17em}⁣}:{\mathbb{R}}^n\to \mathbb{R}$, $\mathbf{x}\in {\mathbb{R}}^n$, and $\epsilon >0$, we design a gradient testing algorithm that determines whether the normalized gradient $\mathrm{\nabla }f(\mathbf{x})\mathrm{/}\mathrm{\parallel }\mathrm{\nabla }f(\mathbf{x})\mathrm{\parallel }$ is $\epsilon$-close or $2\epsilon$-far from a given unit vector $\mathbf{v}$ using $O(1)$ queries, as well as a gradient estimation algorithm that outputs an $\epsilon$-estimate of $\mathrm{\nabla }f(\mathbf{x})\mathrm{/}\mathrm{\parallel }\mathrm{\nabla }f(\mathbf{x})\mathrm{\parallel }$ using $O(n\log (1\mathrm{/}\epsilon ))$ 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\mathrm{/}\epsilon ))$ queries.