Gradient Testing and Estimation by Comparisons

arXiv:2405.11454v3 Announce Type: replace 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 folonmathbb R^nomathbb R, mathbf{x}inmathbb R^n, and arepsilon>0, we design a gradient testing algorithm that determines whether the normalized gradient nabla f(mathbf{x})/|nabla f(mathbf{x})| is arepsilon-close or 2arepsilon-far from a given unit vector mathbf{v} using O(1) queries, as well as a gradient estimation algorithm that outputs an arepsilon-estimate of nabla f(mathbf{x})/|nabla f(mathbf{x})| using O(nlog(1/arepsilon)) 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/arepsilon)) queries.

Source: arXiv cs.LG | 2026-06-26