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:{\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 $\nabla f(\mathbf{x})/\Vert \nabla f(\mathbf{x})\Vert$ 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 $\nabla f(\mathbf{x})/\Vert \nabla f(\mathbf{x})\Vert$ using $O(n\log (1/\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/\epsilon ))$ queries.

v3: 37 pages, 1 figure. To appear in the Forty-Third International Conference on Machine Learning (ICML 2026). Added numerical experiments to validate the proposed algorithms (Section 5), and minor fixes that improve presentation compared to v2. This version subsumes the note "Comparisons are all You need for optimizing smooth functions" (v1)