A parameter that counts steps

Two fields on this site end on a knob, and only one of them calls it that.

The regularisation field’s is λ, a positive real number multiplying a penalty, and choosing it is a subject with a literature: three published rules, scored here against an oracle that requires the exact answer, landing at 1.00, 1.06 and 2.29 times its error.

The iterative field’s is when to stop. It appears in every account of every method in that field as a tolerance — a number small enough that the residual falling below it means the work is done. It is not presented as a modelling decision, and on the problems that field is built on it is not one: the model problem has an exact answer, the iteration converges to it, and stopping early costs accuracy in a way stopping later would fix.

Put the second knob on the first field’s problem and it stops being a tolerance. It becomes the regularisation parameter, it has an optimal value that is not the smallest available, and running past it destroys the answer — while every quantity the method can compute says the run is going well.

The method, and the one thing about it that is not standard #

CGLS is conjugate gradients applied to AᵀAx = Aᵀb with AᵀA never formed. That distinction matters more here than anywhere else on the site, because the road that squares the problem is what forming it costs: κ(AᵀA) = κ(A)², and below ε = √u the product of a matrix with itself comes out exactly singular. The iteration touches A and Aᵀ separately, so its arithmetic is done at κ(A) while its convergence behaves as though the operator were AᵀA.

Every iterate is kept, because the whole subject is which one to hand back. A routine that returned only the last would have thrown away the question.

Semi-convergence, and the two curves that make it #

Read the hero figure as two claims rather than one.

The residual falls at every step. Not on average, not in trend: at every one of the 120 steps, and this is asserted step by step rather than between the ends, because a quantity that falls throughout is the whole of what a solver can see. Conjugate gradients minimises ‖b − Ax‖ over a space that grows by one dimension per step, so the minimum over the larger space cannot be worse than the minimum over the smaller one. This is a theorem, and the figure is it.

The error turns. It falls for twenty steps, reaches 0.1426, and then climbs through two orders of magnitude. Nothing has gone wrong with the arithmetic — the run at step 120 is exactly what the recurrence produces — and nothing has gone wrong with the method. What has happened is that the iteration has started fitting the noise, and the noise is the part of b that has no answer behind it.

The mechanism is the one the previous field measured. The singular values of this operator decay exponentially with no gap anywhere; the coefficients uₖᵀb of the exact right-hand side decay faster; the coefficients of the noisy one flatten at the noise floor and stop. Every term of the solution past that flattening is noise divided by a σ of 10⁻¹⁰ or less. The early iterations reconstruct the components where the signal is; the later ones reconstruct the components where it is not.

So the site’s oldest sentence — a small residual is not a small error — arrives here with a stopping rule attached, and the stopping rule is the regularisation.

Where the turn happens, and how much running past it costs, both move with the noise, and the slider is the whole argument for calling this a regularisation parameter rather than a tolerance.

Across noise levels of 10%, 5%, 2%, 1%, 0.5%, 0.2% and 0.1% the best step reads 3, 5, 10, 20, 27, 35 and 44 and the penalty for running to step 120 reads 361, 194, 81, 42, 25, 7.7 and 5.3. Two decades of better data buy a stopping point fourteen times later and take the cost of getting it wrong down by seventy.

Which inverts what the figure looks like it is warning about. Semi-convergence is drawn as the danger of a long run, and the long run is most dangerous exactly where the data is worst: at ten per cent noise there are three good steps and a factor of 361 waiting past them, and at a tenth of a per cent there are forty-four and a factor of five. A method run to a fixed step count is therefore safest on the problems nobody worries about.

And the best error barely moves at all. It reads 0.1675, 0.1562, 0.1498, 0.1426, 0.1217, 0.1113 and 0.1050 across those same two decades — a factor of 1.6 for a factor of a hundred in the noise. That is what ill-posedness costs stated as plainly as this site can state it: on a well-posed problem a hundredfold better measurement buys a hundredfold better answer, and here it buys sixty per cent.

Which knob is more forgiving, and which way each forgives #

The essay’s framing is that two fields end on a knob and only one of them calls it that. The comparison so far is about what each does. The other comparison is how precisely each has to be set, which is what decides whether a rule is needed at all — and it is measurable on this problem, because both knobs are available on it.

The window inside which each lands within a stated fraction of its own best error:

within 5 per cent, the step count runs 7 to 23 around an optimum of 20, and λ runs 1.33·10⁻² to 1.10·10⁻¹ around an optimum of 2.37·10⁻². Within 25 per cent, steps 2 to 27 and λ from 8.25·10⁻³ to 2.61·10⁻¹. Within a factor of two, steps 1 to 39 and λ over a factor of 110.

λ is the more forgiving knob, and by a factor. At five per cent it tolerates a spread of 8.3 either side where the step count tolerates 23/7 = 3.3; at twenty-five per cent, 31.6 against 13.5. So the parameter with a literature and three published rules is the one that needs the rules least.

And both forgive the same direction #

One thing the windows do not settle, and it is worth marking because the comparison invites it. λ being the wider knob is not an argument for preferring Tikhonov to a stopped iteration — the two windows are measured in different units, and a factor of eight in a continuous parameter is not obviously better or worse than a factor of three in an integer one. What the widths compare is how much a rule for each may be wrong by, and rules for the two are not interchangeable either: one reads a residual against a noise level, and the other has to decide at every step whether to take another.

The comparison that would settle it is the one this field’s next essay makes, where the two knobs are put on the same problem at the same time and the question becomes which of them the other has made unnecessary.

The asymmetry is the sharper half.

The step window at five per cent runs thirteen steps below the optimum and three above it. Stopping early is four times more forgiving than stopping late — which is the semi-convergence curve said as a tolerance: the descent is gentle and the climb past the minimum is not.

The λ window at five per cent runs a factor of 1.8 below its optimum and 4.6 above. That looks like the opposite asymmetry and it is the same one, because a larger λ is more regularisation. On both knobs the forgiving side is the over-regularised side, and the sharp side is the under-regularised one.

Two parameters, two fields, two mechanisms — a Krylov space that has admitted too many directions, and a penalty too small to suppress them — and the same lopsidedness, measured independently on one problem. That is the strongest form of this essay’s claim available: the two knobs are not merely analogous in what they do, they have the same shape of risk.

It also says what a rule has to be good at, which is not what it looks like. Neither knob needs to be found precisely. A rule landing anywhere in a factor of three on the step count, or a factor of eight on λ, gives up five per cent. What a rule must not do is err on the under-regularised side, where the error climbs through two orders in twenty more steps.

Which is why every published rule for both parameters is biased conservative, and why the discrepancy principle’s habitual over-regularisation is the right kind of wrong. A rule that stops a little early is inside the window; a rule that stops a little late may not be. The numbers here are the reason that is a design decision rather than a timidity.

That bias is measured on this figure rather than asserted about the rule. Across the seven noise levels the discrepancy principle stops at steps 3, 3, 5, 7, 11, 19 and 27 against optima of 3, 5, 10, 20, 27, 35 and 44 — at or before the best step at every one of them, and never after. The ratio runs from 1.00 at ten per cent noise down to 0.35 at one per cent and back to 0.61 at a tenth, so the rule is not conservative by a constant; it is most conservative in the middle of the range, where the optimum is moving fastest.

At 1% noise it stops at exactly 7, which is the bottom of the five-per-cent window measured above. The rule that is criticised for over-regularising lands on the edge of the good region and on the forgiving side of it, and that is the whole of what a stopping rule is for.

The filter, and why it is a claim rather than a change of coordinates #

The regularisation field writes both of its standard methods as one expression with different weights:

$$x_{\text{reg}} = \sum_k f_k \, \frac{u_k^{\mathsf T} b}{\sigma_k} \, v_k$$

with fₖ = 1 or 0 for a truncation and fₖ = σₖ²/(σₖ² + λ²) for Tikhonov. The claim about conjugate gradients is that the mth iterate has the same form, with

$$f_k = 1 - \prod_j \left(1 - \frac{\sigma_k^2}{\theta_j}\right)$$

where the θⱼ are the Ritz values of AᵀA after m steps — a polynomial in σ² of degree m, with its roots where the iteration has converged.

There is an obvious way to check that and it proves nothing. The vₖ are an orthonormal basis of the whole space, so any vector can be written as a filtered sum: measure fₖ = σₖ(vₖᵀx_m)/(uₖᵀb), substitute it back, and the sum reproduces xₘ exactly. That is a change of coordinates wearing the clothes of a theorem, and this file’s first version of the check did precisely it.

What makes it a claim is that the polynomial route never looks at the iterate. Conjugate gradients and Lanczos are the same process written twice, so the α and β of the recurrence are the entries of the Lanczos tridiagonal of AᵀA, and its eigenvalues are the θⱼ. The predicted factors are then a function of σ alone, determined by m numbers. The measured factors are sixty-four independent coordinates of a vector, constrained to be nothing at all.

What the shape says #

Two properties of the measured curve are not shared by any Tikhonov filter at any λ, and both follow from what the polynomial has to do.

It goes above one. The largest factor at step 16 is 1.2035. A filter factor above one means the method has overcorrected that component — put back more of it than the data contains. For Tikhonov that is impossible: σ²/(σ² + λ²) is below one for every positive λ, by construction.

It is not monotone. The measured factors change direction eight times. A polynomial that is one at the converged Ritz values and small far below them cannot descend steadily in between; it oscillates around one in the region it has resolved and falls off past it.

Neither is a defect. The overshoot is where the method is ahead of the smooth filter at the same effective cutoff, which is part of why a handful of steps competes with a factorisation. But it settles a question the field’s vocabulary invites: conjugate gradients is a spectral filter in the same sense Tikhonov is, and it is not the same filter, and no λ makes it one.

And the identity has an expiry date #

Now run the two routes further apart and watch them separate.

The polynomial description of conjugate gradients is exact while the recurrence stays orthogonal and false after it. That is not surprising once stated — the whole derivation runs through a Krylov basis that is orthogonal in exact arithmetic and is not in floating point, which is the ghosts essay’s subject in another field.

What is worth having is where it breaks. On this problem the basis loses orthogonality between steps 16 and 20, and the error is least at step 20. The textbook description of the method stops being true at exactly the step anybody would want to stop at. Both halves of that are asserted rather than reported, because an assertion that the routes always agree would be false and one that quietly stopped checking past step 16 would be hiding the interesting half.

The knob is an integer, and that changes what a mistake costs #

The discrepancy principle is the one parameter-choice rule that needs to be told the noise level, and the standard criticism is that nobody knows it. In the λ field the criticism has teeth: told a noise level ten times too small the rule returns λ = 10⁻⁸ and an error of 10,449 against a truthful 0.112 — five orders of magnitude, from a factor of ten.

Applied to a step count, the same rule and the same lie behave differently:

Overstating costs 17%. Understating costs a factor of forty — bad, and bounded by the run, because the rule cannot ask for more steps than are taken. A continuous knob has no such floor: λ can be made arbitrarily small, and the answer it produces is unbounded.

That is a genuine difference between the two parameters and it points the other way from the usual one. The integer is coarser, so it cannot be tuned as finely; and it is coarser, so a wrong noise estimate below a certain size changes nothing at all, because the stopping step is the same integer either way.

Twenty steps against a factorisation #

The comparison the whole essay is for. On this problem:

A ratio of 1.014. The λ needed a singular value decomposition, or a QR of a 2n×n stacked matrix; the step count needed twenty products with A and twenty with Aᵀ, and neither the matrix nor its factorisation was ever formed.

This is where the two fields stop being two fields. What the regularisation field measures as a choice about a penalty, the iterative field can produce as a choice about a budget — and on a problem where A is a convolution and its products cost n log n, the second is available at sizes where the first is not.

The other half of the deferral: a penalty with a null space #

Everything above penalises ‖x‖. The general form penalises ‖Lx‖ for some other matrix L, and with L a discrete derivative the change is not cosmetic: L₁ has a null space, and a vector in it is not penalised at all. assertTheNullSpaceIsTheDifference feeds it a constant vector and requires ‖L₁·(3.7…)‖ to be exactly zero, which it is.

That matters whenever the answer has a nonzero mean, and the size of it is measurable by raising the offset and watching the two forms diverge.

The advantage is not a fact about derivative penalties being better. It is the offset, arriving in the answer, because a penalty on ‖x‖ shrinks — it prefers small answers, and a signal with a large mean is not small. The measured shortfall says so directly: the norm penalty’s solution is short of the truth’s length at every offset, and the derivative penalty’s is not.

And it is the one place where the filter-factor reading of this whole field stops. The general-form solution is not a weighted sum over A’s singular vectors; it is a weighted sum over the generalised singular vectors of the pair (A, L), which are a different basis. A routine that reported measured filter factors for it would be reporting sixty-four numbers that reconstruct the vector and mean nothing, which is exactly the trap the two-route check above exists to avoid — and it is one of the refusals this file runs.

What the two knobs turn out to have in common #

Three things, and the third is what makes this a combination essay rather than a regularisation one.

Both have an interior optimum. Neither the smallest λ nor the largest step count is the right one, and in both cases the reason is the same trade: too little regularisation fits the noise, too much discards signal.

Neither optimum is computable from the data. The oracle in both fields requires the exact answer. Every practical rule is a heuristic, and the ones for the step count are the ones for λ transposed — the discrepancy principle, the L-curve, generalised cross-validation, each with the same weaknesses in the same places.

And the quantity that is easy to compute is monotone in both. The residual falls at every step and falls with every decrease in λ. A stopping rule that watches it and nothing else will always run to the end of whatever budget it is given, which is a correct implementation of a wrong idea — and it is the idea this essay’s refusal is fed.

What is left #

The other Krylov regularisers. LSQR is CGLS in a numerically better arrangement and would change the step at which the two routes above part company; GMRES applied to a square ill-posed system regularises differently again, because its Krylov space is built from A rather than AᵀA. The comparison would be about the bases, which is a phase’s work.

Hybrid methods, where a Tikhonov problem is solved inside the Krylov space at every step, so the two knobs are turned together. That is the obvious next thing to build from this essay and it needs a figure this site does not have: a two-dimensional sweep over λ and m with the oracle drawn on it.

And the noise model. Everything here adds Gaussian noise of a stated size to b. Correlated noise, noise in A rather than in b, and a right-hand side that is not in the range of A at all are three different problems, and only the first is what “1% noise” is usually taken to mean.

A step count that is not a regularisation #

Stopping a Krylov iteration early is a regularisation, and the step count is the parameter. For a matrix function the step count is not a parameter of that kind — it is a polynomial degree, and more of it is simply more accuracy.