We study gradient testing and estimation of smooth functions using a comparison oracle that indicates which of two points has a larger function value. For any smooth function $f: \mathbb R^n \to \mathbb R$, point $\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(1)$ queries.
Additionally, we develop 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, which we prove to be optimal.
Furthermore, we explore gradient estimation in the quantum comparison oracle model, developing a quantum algorithm that uses $O(\log(n/\varepsilon))$ queries.
Blogger's Review: The gradient testing and estimation algorithms presented in this paper show excellent performance in query complexity, particularly the application in the quantum model, highlighting the potential of quantum computing in optimization problems. These advancements will provide new insights and tools for future research.