Optimal Classical and Quantum Algorithms for Gradient Testing and Estimation by Comparisons

Abstract

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$, $\mathbf{x}\in\mathbb R^n$, and $\varepsilon>0$, we design a gradient testing algorithm that determines whether the normalized gradient $\nabla f(\mathbf{x})/||\nabla f(\mathbf{x})||$ is $\varepsilon$-close or $2\varepsilon$-far from a given unit vector $\mathbf{v}$ using $O(n)$ queries, as well as a gradient estimation algorithm that outputs an $\varepsilon$-estimate of $\nabla f(\mathbf{x})/||\nabla f(\mathbf{x})||$ using $O(n\log(1/\varepsilon))$ queries. We prove lower bounds establishing the optimality of both algorithms. Furthermore, we study these problems in the quantum comparison oracle model where queries can be made in superpositions, and develop quantum algorithms for gradient testing and gradient estimation using $O(1)$ and $O(\log (n/\varepsilon))$ queries, respectively.