Komorebi Space

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chap{Certifying an inexact protected correction}\label{sec:inexact-repair}
2 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.
3 
4 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.
5 
6 \begin{scopebox}
7 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.
8 \end{scopebox}
9 
10 \subsection{There are three different residuals}
11 Keep $H=\ker p$, $T=d|_H$, and a residual datum $r$. Fix $\alpha>0$. Write $a_\alpha$ for the unique minimizer of Theorem~\ref{WR06} and let $a\in H$ be any proposed correction. Three quantities now have different meanings:
12 \[
13  v=r-Ta,\qquad
14  g=T^*(Ta-r)+\alpha a,\qquad
15  e=a-a_\alpha.
16 \]
17 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$.
18 
19 The adjoint in $g$ is the restricted adjoint on $H$, not the unrestricted ambient adjoint. Equivalently,
20 \[
21  T^*v=P_Hd^*v.
22 \]
23 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.
24 
25 \subsection{A posteriori correction and fit bounds}
26 \begin{theorem}[Normal residual as a solver certificate]\label{WR13}
27 For every proposed $a\in H$,
28 \begin{align}
29  \norm{a-a_\alpha}&\le\frac{\norm g}{\alpha},\label{eq:solver-error}\\
30  \norm{T(a-a_\alpha)}&\le\frac{\norm g}{2\sqrt\alpha},\label{eq:solver-fit}\\
31  0\le J_\alpha(a)-J_\alpha(a_\alpha)&\le\frac{\norm g^2}{\alpha}.
32  \label{eq:solver-objective}
33 \end{align}
34 \end{theorem}
35 \begin{proof}
36 Let $e=a-a_\alpha$ and $B=T^*T+\alpha I$. The normal equation of the constructed optimizer gives
37 \[
38  Be=(T^*T+\alpha I)a-T^*r=g.
39 \]
40 Pairing with $e$ yields the exact identity
41 \begin{equation}\label{eq:solver-energy}
42  \norm{Te}^2+\alpha\norm e^2=\langle g,e\rangle
43  \le\norm g\norm e.
44 \end{equation}
45 If $e=0$, all three conclusions hold with zero error. Otherwise drop the first nonnegative term and divide by $\alpha\norm e>0$ to obtain $\norm e\le\norm g/\alpha$.
46 
47 To obtain the sharper fitted-data bound, retain the quadratic dependence on $\norm e$ instead of substituting the first estimate. Multiplying \eqref{eq:solver-energy} by $\alpha$ and rearranging gives
48 \[
49 \begin{aligned}
50  \alpha\norm{Te}^2
51  &\le\alpha\norm g\norm e-\alpha^2\norm e^2\\
52  &=\frac{\norm g^2}{4}
53      -\left(\alpha\norm e-\frac{\norm g}{2}\right)^2
54  \le\frac{\norm g^2}{4}.
55 \end{aligned}
56 \]
57 Division by $\alpha$ and square roots give the factor $1/(2\sqrt\alpha)$.
58 
59 By Theorem~\ref{WR06} the objective gap is exactly $\norm{Te}^2+\alpha\norm e^2$, hence by \eqref{eq:solver-energy} it is also $\langle g,e\rangle$. It is nonnegative and satisfies
60 \[
61  J_\alpha(a)-J_\alpha(a_\alpha)
62  \le\norm g\norm e\le\frac{\norm g^2}{\alpha}.
63 \]
64 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.
65 \end{proof}
66 \written{WR13}
67 
68 \paragraph{Sharp scalar examples.} For sharpness of the correction-error bound, take $T=0$ on $\R$ and a nonzero error. Then $g=\alpha e$. For sharpness of the fitted-data bound, take $T=\sqrt\alpha\,I$ on $\R$, so $g=2\alpha e$ and $\norm{Te}=\norm g/(2\sqrt\alpha)$. These examples establish worst-case sharpness, not simultaneous equality for every operator.
69 
70 For a fixed raw vector $f$, the corresponding repaired candidates are $f-a$ and $f-a_\alpha$. Their distance is exactly $\norm e$. Both preserve $pf$ because both corrections belong to $H$. The theorem therefore controls a genuine protected candidate error, not just an intermediate coordinate vector.
71 
72 \fixedplate{37_solver_amplification}{A fixed normal-equation tolerance has different consequences at different regularization parameters. The curves are universal certified upper bounds for a declared normal-residual norm, not observed errors of a particular experiment. The correction estimate grows as $\alpha^{-1}$ while the fitted-data estimate grows as $\alpha^{-1/2}$.}{fig:solver-amplification}
73 
74 \subsection{Why a vanishing normal residual is not enough}
75 Let $T=0$ on $\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
76 \[
77  v_n=0,\qquad g_n=\alpha_n\longrightarrow0,\qquad
78  J_{\alpha_n}(a_n)=\alpha_n\longrightarrow0,
79  \qquad\abs{a_n-a_{\alpha_n}}=1.
80 \]
81 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 $\abs{g_n}/\alpha_n=1$.
82 
83 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.
84 
85 \subsection{A dual certificate does not require solving the normal equation}
86 For an arbitrary $z\in Y$, define
87 \[
88  \mathcal D_\alpha(z)=2\langle r,z\rangle-\norm z^2
89                     -\frac{\norm{T^*z}^2}{\alpha}.
90 \]
91 Unlike the fixed-budget witness in Theorem~\ref{WR04}, this dual witness has no unit-norm constraint. Its quadratic penalties supply the control.
92 
93 \begin{theorem}[Exact regularized primal and dual gap]\label{WR14}
94 For every $a\in H$ and $z\in Y$,
95 \begin{equation}\label{eq:regularized-duality-gap}
96  J_\alpha(a)-\mathcal D_\alpha(z)
97  =\norm{Ta-r+z}^2+
98    \frac{\norm{T^*z-\alpha a}^2}{\alpha}.
99 \end{equation}
100 Consequently $\mathcal D_\alpha(z)\le J_\alpha(a)$ for every pair. At
101 $a=a_\alpha$ and $z=z_\alpha=r-Ta_\alpha$, equality holds, so the dual maximum is attained and equals the primal minimum. Moreover,
102 \[
103  \alpha\norm{a-a_\alpha}^2
104  \le J_\alpha(a)-\mathcal D_\alpha(z).
105 \]
106 For the easily computed choice $z=r-Ta$,
107 \begin{equation}\label{eq:residual-dual-gap}
108  J_\alpha(a)-\mathcal D_\alpha(r-Ta)=\frac{\norm g^2}{\alpha}.
109 \end{equation}
110 \end{theorem}
111 \begin{proof}
112 For arbitrary $a,z$, expand the first square as
113 \[
114  \norm{Ta-r+z}^2
115  =\norm{Ta-r}^2+\norm z^2+2\langle Ta,z\rangle-2\langle r,z\rangle,
116 \]
117 and the scaled second square as
118 \[
119  \frac{\norm{T^*z-\alpha a}^2}{\alpha}
120  =\frac{\norm{T^*z}^2}{\alpha}+\alpha\norm a^2
121        -2\langle T^*z,a\rangle.
122 \]
123 The adjoint identity cancels $2\langle Ta,z\rangle$ against the last term. The remaining expression is
124 \[
125  \norm{Ta-r}^2+\alpha\norm a^2
126  -\left(2\langle r,z\rangle-\norm z^2
127                     -\alpha^{-1}\norm{T^*z}^2\right),
128 \]
129 which is the asserted gap. Its nonnegativity gives weak duality for every pair, without any constraint on the witness norm.
130 
131 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
132 \[
133  \mathcal D_\alpha(z_\alpha)=J_\alpha(a_\alpha).
134 \]
135 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.
136 
137 For a general proposed pair $(a,z)$, decompose its gap as
138 \[
139  J_\alpha(a)-\mathcal D_\alpha(z)
140  =[J_\alpha(a)-J_\alpha(a_\alpha)]
141   +[J_\alpha(a_\alpha)-\mathcal D_\alpha(z)].
142 \]
143 The second bracket is nonnegative by weak duality, while Theorem~\ref{WR06} bounds the first below by $\alpha\norm{a-a_\alpha}^2$. This proves the correction-error certificate.
144 
145 Finally take $z=r-Ta$. The first square in the gap is zero, while $T^*z-\alpha a=-g$. The second becomes $\norm g^2/\alpha$, proving the residual-witness formula. A small duality gap controls optimizer error only after division by the specified positive parameter.
146 \end{proof}
147 \written{WR14}
148 
149 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~\ref{WR13} exactly.
150 
151 \subsection{A protected example with every certificate calculated}
152 Take
153 \[
154  d(x,y)=x,\qquad p(x,y)=x-y,\qquad f=(1,0),\qquad r=df=1,\qquad\alpha=1.
155 \]
156 Every allowed correction has the form $(t,t)$. The objective is
157 \[
158  J(t,t)=(t-1)^2+2t^2,
159 \]
160 so $a_\alpha=(1/3,1/3)$ and $J(a_\alpha)=2/3$. Suppose a procedure returns only $a=(1/4,1/4)$. Then
161 \[
162  v=\frac34,\qquad T^*v=(3/8,3/8),\qquad
163  g=(-1/8,-1/8),\qquad\norm g^2=\frac1{32}.
164 \]
165 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~\ref{WR13} is $1/128$.
166 
167 The proposed objective is $11/16$. Its actual excess over the optimum is $1/48$. The residual witness gives
168 \[
169  \mathcal D_1(3/4)=\frac{21}{32},\qquad
170  J(a)-\mathcal D_1(3/4)=\frac1{32}.
171 \]
172 The duality gap is an upper bound for suboptimality, not necessarily the exact suboptimality. Both repaired candidates preserve $p(f)=1$.
173 
174 \fixedplate{38_objective_certificate}{The objective on the actual protected line is $3t^2-2t+1$. The proposed correction at $t=1/4$, exact minimizer at $t=1/3$, and residual-witness lower bound are distinct. The vertical gap to the dual level is the checkable certificate. The smaller gap to the minimum is the true suboptimality.}{fig:objective-certificate}
175 
176 The supplied program \path{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.

Back to source controls

Back to Komorebi Space