How Loud Is a Gradient? An Amplitude Law for Noisy Comparisons

A comparison oracle reports which of two points is better. Can it certify that an optimizer may stop, that is, that $\Vert \nabla f(\bar{x})\Vert \le \epsilon$? Exact comparisons cannot: they preserve only the order of values. Under Bradley–Terry noise a query returns $1$ with probability $\sigma (\beta (f(x)-f(y)))$, so repeated answers measure value gaps. We show that every question posed to this oracle has a natural size, its amplitude: the least uniform change of the logit potential $\beta f$, modulo constants, that flips the answer. A question of amplitude $a$ needs at least $H/a^2$ comparisons, with $H$ the entropy of what must be distinguished, and it is unanswerable when opposite answers can share a potential. Computing amplitudes organizes the theory. A gradient is a small value step, of amplitude exactly $\beta {\epsilon }^2/(4L_1)$ for $\epsilon$-vs-$2\epsilon$ tests over $L_1$-smooth objectives; for $p$-th order smoothness, the exponent of Kolmogorov's inequality yields search lower bounds $\Omega (n{L}^{2/p}/({\beta }^2{\epsilon }^{2+2/p}))$. When $\beta$ is known only up to a ratio $\rho$, the amplitude is proportional to $(c^{\prime }-\rho {)}_{+}^2$: $\epsilon$-vs-$c^{\prime }\epsilon$ verification is impossible exactly when $\rho \ge c^{\prime }$, and its cost grows as $(c^{\prime }-\rho {)}^{-4}$ at the edge, a rate an explicit tester attains. Value-margin tests have amplitude $\beta m_0$ and need neither smoothness nor dimension-dependent sampling. The unresolved factor is dimension: at fixed confidence, known-scale verification costs between $$\begin{gathered} \max \\ 1,a^{-2} \end{gathered}$$ and $$\begin{gathered} \max \\ 1,n^2{a}^{-2} \end{gathered}$$ comparisons up to constants, and nonadaptive verifiers need order $(n-1)a^{-2}$.