A stopping rule that follows the run it is given

What a cheap preconditioner has to leave alone found a preconditioner a real deconvolution can afford that reaches the unpreconditioned floor in a quarter of the steps: the blur approximated by a cosine-diagonal matrix, inverted only in the directions whose eigenvalue in the approximation is at least τ. Every number in that essay was read against the truth. The best step was the step with the least error, and a real run has no error to read.

What it has is a residual, and a rule written on the residual. The discrepancy principle stops at the first step whose residual is no larger than the noise, and a parameter that counts steps measured it on the plain run: step 7 against a best of step 20, at 0.1488 against 0.1426. Four per cent lost for not knowing the answer, on one draw of the noise, which is the kind of loss that makes a rule worth using.

The preconditioner makes the rule’s job look harder. A run that reaches its best in five steps reaches it on a steeper curve, and the stretch of steps that are nearly as good as the best is shorter. A rule that stops a step early on a curve that is flat for twenty steps loses a little; the same rule a step early on a curve that is flat for four ought to lose more. A preconditioner that arrives past the answer asked the question directly — how much a rule loses on each side of the preconditioner’s optimum — and this essay measures it, over forty draws of the noise and at two noise levels.

The answer runs the other way. The window of good steps does shrink by a factor of four, and the rule’s stop lands nearer the preconditioned run’s best than it lands on the plain run. What the rule cannot do is notice a preconditioner that has gone past its edge: it keeps stopping close to the run’s own best while that best walks away from anything worth having.

A window twenty-three steps wide, and one of six #

On the draw of the noise every figure here has used, the plain run’s error is least at step 20 and within 10% of that least value from step 4 to step 26: twenty-three steps, any of which a reader comparing answers by eye would accept. Preconditioned with τ = 0.032, the least error is at step 8 and the steps within 10% run from 4 to 9. Six steps. The preconditioner has moved the best answer twelve steps earlier and removed three quarters of the room around it.

The rule does not know where either window is. It watches the residual fall and stops the moment it crosses the noise level, 1.01 times the norm of the noise that was added. On the plain run that happens at step 7, which is inside the window and early in it — the error is still falling, and at step 7 it is 1.043 times its eventual least value. On the preconditioned run the residual crosses at step 4, the first step of the window, where the error is 1.021 times its least value.

So on this draw the rule stops nearer the best of the narrow window than the best of the wide one. One draw is an anecdote, and a noise draw is exactly the kind of accident a stopping rule’s reputation can rest on for years; one draw in twenty found cross-validation’s second answer on four to six draws in a hundred after sixteen draws had shown none. The measurement that means something is the same comparison repeated on draws that share nothing but their size.

Forty draws, and the rule does better where it has less room #

Forty draws of the noise at 1%, each scaled to the same norm, each run plain and preconditioned at seven values of τ from 0.3 down to 3·10⁻⁴, each run scored twice: against its own best step, and against the best Tikhonov solution of the same draw, which is the oracle neither the run nor the rule can see.

On the plain run the rule stops, in the median draw, at 1.073 times the run’s best, with a worst draw of 1.200 and sixteen steps within 10% of the best. On the run preconditioned at τ = 0.032 it stops at 1.030 times the run’s best, with a worst draw of 1.113 and four steps within 10%. The window is a quarter the width and the rule’s median loss is less than half. Measured against the oracle rather than against each run’s own best, the plain run’s stop is 1.095 times Tikhonov’s error and the preconditioned run’s is 1.069, so the narrower window has not only failed to cost the rule anything but has left it with a better answer.

It is not that the preconditioned run is simply better. Its own best, in the median draw, is 1.027 times Tikhonov’s, a shade worse than the plain run’s 1.013. What improves is the distance between the step the rule chooses and the step the truth would have chosen, and it improves by more than the run’s best worsens.

At τ = 0.1, above the edge, the picture is the plain run’s again: nine steps within 10%, a rule’s stop at 1.081 times the run’s best and 1.102 times Tikhonov’s. The benefit is specific to a preconditioner near its edge, which is also the one worth running — the τ that needs the fewest steps is the τ at which the rule stops best.

Why an early stop costs less on a run that arrives early #

The discrepancy principle on conjugate gradients stops early, and the reason is known from the plain run. The residual reaches the noise level while the iteration is still adding signal components slowly: in the median draw the rule stops at step 7 and the best is at step 18, and the eleven steps between them are spent improving the answer by the seven per cent the rule gives up. The residual cannot see that improvement, because a component whose singular value is small changes the residual by very little when it is added and changes the error by a great deal.

The preconditioner compresses that stretch. In the median draw at τ = 0.032 the rule stops at step 4 and the best is at step 7, three steps rather than eleven, because the preconditioner has already delivered in its first steps most of the components the plain run was still assembling after the residual had nothing left to say. The rule stops at the same place relative to the noise — the first step whose residual is below it — and less of the answer remains to be built after that point.

That reading fits the step counts and the losses, and it is not established by them: the median step counts are medians of different draws, and a draw on which the rule stops early by one step on a steep stretch could lose more than a draw on which it stops early by three on a flat one. What is measured is the outcome, over forty draws: a narrower window, a smaller loss, and a worst case that moves in the same direction as the median.

Past the edge the rule has nothing to warn about #

The same sweep has a second half, and it is the half that decides how far the rule can be trusted.

At τ = 10⁻³ the preconditioner has begun dividing directions the approximation gets wrong, and the run’s best error is no longer worth having. On the drawn noise it is least at step 9, with two steps inside its 10% window, and the rule stops at step 6 at 2.13 times that least error. Over forty draws the median run’s best at this τ is 5.52 times Tikhonov’s, and the rule’s stop is 1.66 times the run’s best — 8.95 times Tikhonov’s, with a worst draw of 21.

Read one way, the rule has done well: it stopped within a factor of 1.7 of the best step of a run whose best was terrible, a closer ratio than a stop a few steps late on a run past its edge would have given. Read the other way, it has said nothing. Its criterion is a residual at the noise level, and a preconditioned run past its edge reaches that residual as readily as one before it, because it reaches it by fitting noise that the approximation’s wrong directions supplied. At τ = 3·10⁻⁴ the run’s best is 13.9 times Tikhonov’s and the rule’s stop 24.1 times. Nothing in the residual history of those runs differs in kind from the history of a good one.

So the rule is faithful to the run it is given. It chooses a step, and it chooses well among the steps on offer. It does not choose τ, and it cannot detect that τ was chosen badly — which is choosing without knowing one level up: that essay found the discrepancy principle within 6% of the oracle when it is told the noise and catastrophic when it is told the noise wrongly. Here it is told the noise correctly and handed an iteration that is wrong, and it is exactly as uninformative about the second as about the first.

At a tenth of the noise the rule is nearly exact #

The same forty draws at 0.1% noise change the numbers and keep the shape.

On the plain run at 0.1% noise the rule stops in the median draw at 1.115 times the run’s best, with twenty-six steps within 10% of it — a wider window than at 1% and a larger loss, because at a tenth of the noise the run goes on adding useful components for longer after the residual has reached the noise: best at step 42, stopped at step 24 or 25. At τ = 3.2·10⁻³, the preconditioner near its edge at this noise level, the rule stops at 1.001 times the run’s best, with six steps within 10% and a worst draw of 1.057. Against the oracle the stop is 1.005 times Tikhonov’s error.

The drawn case makes the median concrete. The rule stops the plain run one step before its window begins and the preconditioned run on the first step of its window. The preconditioned stop is at step 7, the best at step 8: the residual crossed the noise one step before the error turned, which is as close as a rule that reads a different quantity from the error can reasonably be asked to come.

That is a result an expiry date the noise does not move would not have predicted from the plain run. There the step worth stopping at walked from 3 to 44 as the noise fell through three decades, and a rule chasing a walking target has more to lose the further it walks. The preconditioner near its edge holds the best step at seven or eight at both noise levels, and holds the rule’s stop a step before it.

The Fourier approximation, and where the rule stops following #

The cosine approximation was swept first because it is the nearer of the two to the blur. The Fourier one is four times further away, reached the floor as well on the drawn noise, and makes the harder test of faithfulness, because far past its edge its runs fail in a different way from the cosine runs.

Near its edge the Fourier-preconditioned run gives the rule what the cosine one did: seven steps within 10% of the best against the plain run’s seventeen, and a median stop at 1.029 times the run’s best against 1.073. Measured against the oracle the gain disappears at 1% noise. The run’s own best is 1.036 times Tikhonov’s, a shade worse than the cosine run’s 1.027, and the rule’s stop lands at 1.095 times Tikhonov’s — exactly where it lands on the plain run. At 0.1% noise the gain returns: at τ = 3.2·10⁻³ the rule stops at 1.037 times the run’s best against the plain run’s 1.116, and at 1.044 times Tikhonov’s against 1.110.

Past the edge the rule stops following, in two stages. At τ = 10⁻³ it stops early, at step 8 against a best at step 11 in the median draw, and at 2.63 times the run’s best — already further from its run than the cosine rule ever was. At τ = 3.2·10⁻⁴ the median run is best at its first step, where the iterate has barely left zero, and every later step is worse; the rule stops at step 11, at 5.90 times the run’s best, with a worst draw of 8.1. The first residual of such a run is about as large as the data, because the first step fitted nothing, and it reaches the noise only after ten steps of fitting boundary disagreement and noise. The rule does exactly what it always does — stops at the first residual below the noise — and on a run whose best is its first step that is ten steps too late.

So faithfulness has a condition, and the two approximations locate it. The rule follows a run whose best answer is reached by fitting: an error that falls while the residual falls and turns once the residual has reached the noise. A run whose best answer is its first step, because the preconditioner aimed that step into what the approximation gets wrong, has no such turn for the residual to mark, and the rule is then worse than stopping at once would have been. It happens at a τ nobody would choose on purpose, and it is still worth having measured: it is the one place in either sweep where running the rule loses more than the run itself had already lost.

Bounded above the edge, and not below it #

The exact preconditioner’s table suggested that a rule’s loss would be bounded on the safe side of the optimal shift and unbounded on the other. With the cheap preconditioner and forty draws that becomes a measurement rather than a suggestion. Against Tikhonov’s error on the same draw, the rule’s median stop at 1% noise reads:

Above the edge the rule’s median is within a few per cent of its median on the plain run, and its worst draw within a few per cent of the plain run’s worst. Below the edge each half decade roughly doubles the median and more than doubles the worst case, and almost all of the growth is in the first column rather than the second: the run got worse and the rule followed it. The loss is bounded where the preconditioner is safe because the preconditioner is safe there, not because the rule has any means of keeping it so.

The practical asymmetry is the one the exact preconditioner already suggested for its shift. A τ a little too large costs a few steps and nothing else, and a stopping rule on it performs as it does on the plain run or better. A τ a little too small costs accuracy the rule cannot recover and cannot report.

What a residual can certify on a preconditioned run #

A residual at the noise level is a necessary condition for a regularised answer and not a sufficient one. The discrepancy principle turns the necessary condition into a stopping rule by adding one assumption: that the first step satisfying it is the step at which the iteration has fitted the signal and not yet fitted the noise. On the plain run that assumption is approximately true and early by a known margin. On a preconditioned run near its edge it is more nearly true, because the preconditioner has moved the fitting of the signal earlier and left the fitting of the noise where the plain run had it.

Past the edge the assumption fails and nothing in the residual says so, because the preconditioner has moved the fitting of some of the noise earlier too. The residual reports that something has been fitted to the noise level; it cannot say what. A stopping test is a race is the same limitation in a well-posed setting, where a residual test stops the iteration that reaches the tolerance first and has no opinion about whether it is the iteration that should have. And the step that stops mattering is the construction that removes the question rather than answering it, by regularising inside the iteration so that stopping late is harmless — a construction whose interaction with a preconditioner past its edge is itself unmeasured.

What this does not settle #

The rule here is told the norm of the noise exactly. Thirty-two coefficients instead of a noise level found that told too little it falls off a cliff at a definite understatement, and a run whose window is a quarter as wide may put that cliff somewhere else; that is not measured. The noise is white. Noise that spares the answer and fools the rules found correlated noise breaking two parameter rules while improving the best answer, and the discrepancy principle’s behaviour on a preconditioned run with correlated noise is not measured either.

Both approximations are swept over the same forty draws, but only two of the four combinations of approximation and noise level are drawn, and the two runs that fail differently past their edges were found by sweeping rather than predicted: a third construction could fail in a third way. And forty draws are forty draws, at each of two noise levels, on one operator and one signal. The medians settle well within that many; the worst cases are the worst of forty and nothing more.

Still open: can the rule choose τ, and can the pair be one number? #

A rule for τ that reads what the residual cannot. The discrepancy principle picks the step and is blind to τ. A rule for τ would need a quantity that differs between a run before its edge and a run past it — perhaps the size of the first preconditioned step against the data, or the approximation’s coefficients of the data read as a Picard plot. Which of those separates the two cases over forty draws, if either does, is the measurement that would make the preconditioner usable without an oracle.

The pair as one parameter. A step that is not a unit of work found Landweber’s regularisation parameter to be the product of step length and step count rather than either alone. A truncated preconditioned run has τ and a step, and the steps at the edge fall as τ falls: whether some combination of the two plays the part ωk played — so that a rule could choose one number instead of two — is unmeasured.

The rule told the noise wrongly. The cliff the discrepancy principle falls off when the noise is understated was measured on the plain run, whose window is sixteen steps wide. On a run with four steps in its window the same understatement may send the rule past the window sooner, or the residual’s steeper fall may keep it inside; the sweep over understatements on the preconditioned run is the direct continuation.