An inexact gradient residual certifies distance under strong convexity

Let $U\subseteq {\mathbb{R}}^d$ be open and convex, let $f\in C^2(U,\mathbb{R})$ have an attained interior global minimizer $x^{\ast }$, and suppose $H_f(x)⪰\mu I$ on $U$ for some $\mu >0$. For a candidate $\tilde{x}\in U$, let $\widehat{g}\in {\mathbb{R}}^d$ be a computed gradient vector. If independently verified bounds

$\mathrm{\parallel }\widehat{g}{\mathrm{\parallel }}_2\le \eta ,\mathrm{\parallel }\widehat{g}-\mathrm{\nabla }f(\tilde{x}){\mathrm{\parallel }}_2\le \delta$

hold for $\eta ,\delta \ge 0$, then

$\mathrm{\parallel }\tilde{x}-x^{\ast }{\mathrm{\parallel }}_2\le \frac{\eta +\delta }{\mu }\mathrm{.}$

The residual $\eta$ and discrepancy $\delta$ are mathematical hypotheses. A software stopping flag alone establishes neither bound.

The certificate combines two distinct checks: a residual of the computed vector and an error bound comparing that vector with the true gradient. If $\delta =0$, it reduces to the exact-gradient certificate; if the objective is computed by quadrature or another inner method, its gradient error must still be bounded separately.