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:\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})/\lVert\nabla f(\mathbf{x})\rVert$ is $\varepsilon$-close or $2\varepsilon$-far from a given unit vector $\mathbf{v}$ using $O(1)$ queries, as well as a gradient estimation algorithm that outputs an $\varepsilon$-estimate of $\nabla f(\mathbf{x})/\lVert\nabla f(\mathbf{x})\rVert$ 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.

Many machine-learning systems are trained by repeatedly deciding which way to change their parameters to improve performance. Usually, this requires numerical information about how the training objective changes. In some settings, however, such information is unavailable or too costly to obtain, and we may only be able to compare two choices and ask which one is better. This paper studies what can be learned from this very limited type of feedback. We show that simple comparisons are enough to reliably check whether a proposed direction is nearly correct, and to estimate a good direction for improvement. We design algorithms that use the smallest possible number of comparisons in the standard classical setting. We also study a quantum version of the problem, where comparisons can be queried in quantum superposition, and give algorithms that use many fewer queries. These results help clarify the fundamental power and limits of comparison-based learning and optimization. They may also guide future methods for training or improving models when only relative judgments, rather than exact numerical scores, are available.