31 Certifying an inexact protected correction
On this page · Permalink · Source line 1
An existence theorem for a regularized optimizer does not guarantee that a numerical procedure has reached it. The procedure may stop early, use a poorly scaled basis, or report the residual of the wrong equation. These are mathematical distinctions, not implementation details that can be deferred until after a certificate has been interpreted.
The relevant question is now more specific. Given a proposed correction, what quantities can be checked without first computing the exact optimizer? The answer is a normal-equation residual and, independently, a primal and dual objective gap. Both give quantitative statements about the declared regularized problem. Neither promises that the original unregularized realization problem is solvable.
Do not conflate
The accompanying formalization constructs the positive-parameter optimizer and proves the energy identity, global uniqueness, and the estimates in this chapter, with a separate bridge to the actual protected kernel. Regularization limits and the combined inexact stopping theorem also have formal counterparts. The explicit infinite diagonal results also have formal counterparts. The printed weak-subsequence argument remains written background material. The exact Python certificate verifier is tested, not universally verified as a refinement of Lean.
31.1 There are three different residuals
On this page · Permalink · Source line 10
Keep \(H=\ker p\), \(T=d|_H\), and a residual datum \(r\). Fix \(\alpha>0\). Write \(a_\alpha\) for the unique minimizer of Theorem 29.1 and let \(a\in H\) be any proposed correction. Three quantities now have different meanings:
The vector \(v\) is the fit residual. The vector \(g\) is the normal-equation residual, equal to one half of the derivative of the quadratic objective after identifying the dual with \(H\). The vector \(e\) is the unknown correction error. The exact optimizer generally has \(v\ne0\) but always has \(g=0\).
The adjoint in \(g\) is the restricted adjoint on \(H\), not the unrestricted ambient adjoint. Equivalently,
Thus the correction certificate must measure the part of the normal equation that belongs to the permitted correction space. A numerical program that forgets this projection can incorrectly reject an exact protected optimizer.
31.2 A posteriori correction and fit bounds
On this page · Permalink · Source line 25
Theorem 31.1: Normal residual as a solver certificate
For every proposed \(a\in H\),
Proof
Let \(e=a-a_\alpha\) and \(B=T^*T+\alpha I\). The normal equation of the constructed optimizer gives
Pairing with \(e\) yields the exact identity
If \(e=0\), all three conclusions hold with zero error. Otherwise drop the first nonnegative term and divide by \(\alpha{\left\lVert e\right\rVert}>0\) to obtain \({\left\lVert e\right\rVert}\le{\left\lVert g\right\rVert}/\alpha\).
To obtain the sharper fitted-data bound, retain the quadratic dependence on \({\left\lVert e\right\rVert}\) instead of substituting the first estimate. Multiplying (31.4) by \(\alpha\) and rearranging gives
Division by \(\alpha\) and square roots give the factor \(1/(2\sqrt\alpha)\).
By Theorem 29.1 the objective gap is exactly \({\left\lVert Te\right\rVert}^2+\alpha{\left\lVert e\right\rVert}^2\), hence by (31.4) it is also \(\langle g,e\rangle\). It is nonnegative and satisfies
Every certificate quantity on the right is computed from the proposal \(a\) and the declared problem. The unknown optimizer was used to prove the guarantee, but it is not required to evaluate the certificate.
Sharp scalar examples.
On this page · Permalink · Source line 68
For sharpness of the correction-error bound, take \(T=0\) on \({\mathbb R}\) and a nonzero error. Then \(g=\alpha e\). For sharpness of the fitted-data bound, take \(T=\sqrt\alpha\,I\) on \({\mathbb R}\), so \(g=2\alpha e\) and \({\left\lVert Te\right\rVert}={\left\lVert g\right\rVert}/(2\sqrt\alpha)\). These examples establish worst-case sharpness, not simultaneous equality for every operator.
For a fixed raw vector \(f\), the corresponding repaired candidates are \(f-a\) and \(f-a_\alpha\). Their distance is exactly \({\left\lVert e\right\rVert}\). Both preserve \(pf\) because both corrections belong to \(H\). The theorem therefore controls a genuine protected candidate error, not just an intermediate coordinate vector.
31.3 Why a vanishing normal residual is not enough
On this page · Permalink · Source line 74
Let \(T=0\) on \({\mathbb R}\), let \(r=0\), and take \(\alpha_n=n^{-2}\) for \(n\ge1\). The exact optimizer is zero for every such \(n\). The fixed proposal \(a_n=1\) instead has
Thus the fit residual, the normal residual, and even the absolute objective value can all tend to zero without convergence to the selected optimizer. The certificate correctly reports \({\left\lvert g_n\right\rvert}/\alpha_n=1\).
This is not an infinite-dimensional obstruction. It occurs in one dimension because the regularizing penalty itself disappears. The question is not whether the reported residual is small in isolation, but whether it is small relative to the parameter that converts it into an error bound.
31.4 A dual certificate does not require solving the normal equation
On this page · Permalink · Source line 85
For an arbitrary \(z\in Y\), define
Unlike the fixed-budget witness in Theorem 28.2, this dual witness has no unit-norm constraint. Its quadratic penalties supply the control.
Theorem 31.2: Exact regularized primal and dual gap
For every \(a\in H\) and \(z\in Y\),
Consequently \(\mathcal D_\alpha(z)\le J_\alpha(a)\) for every pair. At \(a=a_\alpha\) and \(z=z_\alpha=r-Ta_\alpha\), equality holds, so the dual maximum is attained and equals the primal minimum. Moreover,
For the easily computed choice \(z=r-Ta\),
Proof
For arbitrary \(a,z\), expand the first square as
and the scaled second square as
The adjoint identity cancels \(2\langle Ta,z\rangle\) against the last term. The remaining expression is
which is the asserted gap. Its nonnegativity gives weak duality for every pair, without any constraint on the witness norm.
Set \(a=a_\alpha\) and \(z_\alpha=r-Ta_\alpha\). The first square is zero by this definition. The normal equation gives \(T^*z_\alpha=\alpha a_\alpha\), so the second is zero as well. Therefore
For every other \(z\), weak duality with \(a_\alpha\) gives \(\mathcal D_\alpha(z)\le J_\alpha(a_\alpha)\). This proves attainment of the dual maximum and equality with the primal minimum directly.
For a general proposed pair \((a,z)\), decompose its gap as
The second bracket is nonnegative by weak duality, while Theorem 29.1 bounds the first below by \(\alpha{\left\lVert a-a_\alpha\right\rVert}^2\). This proves the correction-error certificate.
Finally take \(z=r-Ta\). The first square in the gap is zero, while \(T^*z-\alpha a=-g\). The second becomes \({\left\lVert g\right\rVert}^2/\alpha\), proving the residual-witness formula. A small duality gap controls optimizer error only after division by the specified positive parameter.
A proposed correction and a proposed dual witness can come from different procedures. The verifier only needs the mathematical problem, the two vectors, and the displayed identities. A poor witness remains valid as a lower bound, but can give a loose gap. The residual witness avoids a second optimization routine and recovers the bound in Theorem 31.1 exactly.
31.5 A protected example with every certificate calculated
On this page · Permalink · Source line 151
Take
Every allowed correction has the form \((t,t)\). The objective is
so \(a_\alpha=(1/3,1/3)\) and \(J(a_\alpha)=2/3\). Suppose a procedure returns only \(a=(1/4,1/4)\). Then
The actual correction-error square is \(1/72\), while the certified upper bound is \(1/32\). The actual fitted-error square is \(1/144\), while the sharper bound in Theorem 31.1 is \(1/128\).
The proposed objective is \(11/16\). Its actual excess over the optimum is \(1/48\). The residual witness gives
The duality gap is an upper bound for suboptimality, not necessarily the exact suboptimality. Both repaired candidates preserve \(p(f)=1\).
The supplied program examples/inexact_repair_certificate.py verifies this calculation without calling the optimizer. It also accepts a user-supplied dual witness. Every reported scalar is rational, and all norm error bounds are stored as squared quantities so that no rounding of a square root is required.