The step that stops mattering

A parameter that counts steps established the awkward fact this essay removes. On an ill-posed problem an iterative method’s error falls, reaches a minimum, and then climbs by orders of magnitude — and the residual, the only quantity a solver can see, falls at every step throughout. The step count is the regularisation parameter, and getting it wrong in the safe-looking direction is expensive.

Everything about that is a statement about where the penalty is not. The iteration builds a subspace, projects the problem onto it, and solves the projection exactly. Nothing regularises the projected problem, because the projection was supposed to be the regularisation.

So put a penalty there too.

What the noise level changes, and the one thing it does not #

The headline above is measured at one noise level, and a claim of the form “it stops turning” needs the whole slider before it is worth anything — a curve can be flat at one level and not at another.

Two things move as the noise falls, and one of them is the whole difficulty of stopping. Watch where the lower curve reaches its minimum, and how far it has climbed by the right-hand edge, because those two readings go in opposite directions as the data gets cleaner.

The best step has moved out by twenty-one since the frame at noise 0.1 — from step 3 to step 24 — while the final error has fallen by a factor of fifty, from 1,607 to 32.2. Neither of those is the regularised curve doing anything at all.

The step at which the unregularised run is best walks from 3 to 27 across the sweep — 3, 10, 20, 24, 27 at noise 0.1, 0.02, 0.01, 0.002 and 0.001. That is the reason stopping is a problem worth an essay: the right step is a strong function of a quantity a caller does not know, and being at step 3 when the answer was at step 27 is as wrong as the reverse.

And the divergence is exactly linear in the noise. The unregularised error at step 40 reads 1,607, 322, 161, 32.2 and 16.1, and dividing each by its own noise level gives 16,070, 16,100, 16,100, 16,100 and 16,100. Not approximately — the same five digits at four of the five stops. So the run past its optimum is not amplifying the noise in some complicated way; it is multiplying it by a constant that belongs to the operator and the step count.

What does not move is the regularised curve’s floor, which reads 0.1720, 0.1500, 0.1429, 0.1180 and 0.1079 — a factor of 1.6 across a hundredfold range of noise. The best achievable answer barely depends on the data quality, which is what an ill-posed problem means; what depends on the data quality is how catastrophically it can be missed.

One qualification the headline needs. The dek’s 1.000000000003 times above its own best is the measurement at noise 0.01, and it is the best case rather than the general one. At 0.002 and 0.001 the end is unchanged from the best to every digit printed, so the claim holds there too — but at 0.02 the regularised run ends 2% above its best, and at 0.1 it ends 14% above. The hybrid stops the curve turning outright below about 10⁻², and above that it turns a little. That boundary is worth having, because it is the regime a caller with genuinely noisy data is in.

What is being built #

The Golub–Kahan bidiagonalisation generates two orthonormal bases at once — one for the row space and one for the column space — and between them a matrix Bₖ that is (k+1)×k and has entries on only two diagonals, satisfying A Vₖ = Uₖ₊₁ Bₖ exactly. Least squares over the subspace spanned by the columns of Vₖ is then a least-squares problem in k unknowns with a bidiagonal matrix, which is what LSQR solves at every step. Its answer is the projected problem’s exact one.

A hybrid method changes one line. Instead of minimising ‖Bₖ y − β₁e₁‖ it minimises ‖Bₖ y − β₁e₁‖² + λ²‖y‖², and takes the same x = Vₖ y. There are now two parameters — the step count k on the outside and the penalty λ on the inside — and the whole question is what having both does.

The construction is not a hybrid of two methods in the sense of alternating between them. It is one iteration with a second decision taken inside every step of it, and the reason that is worth a name is that the two decisions are about the same quantity: how much of the data to believe.

Two identities make the small problem the same problem #

A penalty applied to a projection is only meaningful if the projection has kept what the penalty is supposed to act on. Two facts settle that, and both are asserted rather than quoted.

The residual is preserved exactly. Uₖ₊₁ has orthonormal columns, so ‖b − A Vₖ y‖ equals ‖β₁e₁ − Bₖ y‖ for every y. Not approximately: the residual of the (k+1)×k problem is the residual of the 64×64 one. Checked at four subspace sizes and three penalties — twelve pairs — the worst relative disagreement is 7.7·10⁻¹⁵, on a basis whose own orthogonality error is 1.8·10⁻¹⁵.

That is what makes the small problem worth choosing a parameter on. A rule that reads a residual is reading the same number either way, and the next essay is about what happens to a rule that reads something else.

And the projected problem is solved twice. The stacked route hands the (2k+1)×k system [B; λI] y ≈ [β₁e₁; 0] to this site’s own Householder least squares; the second route takes the singular value decomposition of B and applies the filter σ²/(σ² + λ²) to each projected component, which is the regularisation field’s own filter applied to a 17×16 matrix instead of a 64×64 one. At three penalties the two agree to 1.4·10⁻¹⁵.

The measurement #

Forty steps, sixty-four unknowns, 1% noise, and the inner λ chosen at every step by generalised cross-validation on the projected problem.

The unregularised run is the one this site has drawn before under another name — that column is LSQR, and its shape is semi-convergence. Twenty steps in it is at its best; twenty steps later it is wrong by a factor of a thousand, and its residual has fallen monotonically the whole way.

The regularised run reaches a floor 0.2% higher and then does not move. The last twelve steps change the answer in the twelfth significant figure.

What is bought is not accuracy. The two floors are within a fifth of a per cent of each other, which is the combination field’s own finding arriving again: the floor belongs to the problem, four knobs find it, and a fifth arrangement of two of them finds the same one. What is bought is that the floor is reached and held, so the outer parameter can be set by a budget rather than by a rule.

Why the curve turned in the first place #

The obvious explanation for semi-convergence is that the projected problem inherits the ill-posedness: more steps, more of the small singular values, more amplified noise. The first half of that is true and the arithmetic in it is not.

The singular values of Bₖ are the Ritz values of the bidiagonalisation, and they converge to the largest singular values of A first — the top four agree with A’s to 10⁻⁶ by the end of the run. So the projected condition number does climb:

And κ(A) is 5.7·10¹². At forty-eight steps the projected problem is a million times better conditioned than the problem, and the unregularised answer there is wrong by a factor of 14,300. A condition number six orders of magnitude short of the one being blamed is not the explanation.

The quantity that moves with the error is the last column of that table. Each step admits one more direction, each new direction has a smaller singular value than the last, the noise has a component along it, and that component is divided by the singular value. So the cost of a step is ‖e‖/σ_min, and from twenty-four steps on the error is a fixed fraction of it:

The error moves by a factor of 62,000 and the fraction moves by a factor of 1.5. The numerator of a condition number — the largest singular value — has nothing to do with any of it, which is why the ratio is the quantity worth drawing and κ is not.

This also says what the penalty is doing. σ²/(σ² + λ²) is small where σ is small, so the directions the subspace has just admitted are the ones it suppresses, and it suppresses more of them the further the run goes — at a fixed λ. Whether the rule choosing λ then has to move it is a separate question, and the answer is the subject of the next section.

The penalty settles, it does not track #

The natural story about why the inner knob works is that it follows the outer one: each step admits a smaller singular value, so λ must rise to keep suppressing what has just arrived. It is a tidy story and the measurement refuses it.

Here is what generalised cross-validation actually chooses, step by step, beside the projected problem’s smallest singular value:

at four steps λ is 3.2·10⁻² and σ_min is 5.7·10⁻¹. At eight, 3.2·10⁻² and 2.8·10⁻¹. At twelve, 4.6·10⁻² and 1.7·10⁻¹. At sixteen, 6.8·10⁻² and 8.8·10⁻². At twenty-four, 6.8·10⁻² and 9.7·10⁻³. At thirty-two, 4.6·10⁻² and 6.8·10⁻⁴. At forty, 4.6·10⁻² and 1.3·10⁻⁵.

λ moves by a factor of two, up and then back down, and settles. σ_min falls by four and a half orders of magnitude. Their ratio runs from 0.055 to 3,540, which is what not tracking looks like.

So the rule is not chasing anything, and after about sixteen steps it is choosing a constant. That is the explanation the fixed-λ table was waiting for: a fixed penalty works as well as an adaptive one because the adaptive one has converged to a fixed penalty. And the reason it can is one-directional — σ_min only ever falls, so a λ once above it stays above it, and a filter that is suppressing the newest direction goes on suppressing every direction admitted after it without being told.

The oracle says the same thing from the other end, and adds where the handover is. Given the true solution and allowed to pick the best λ at every step, it takes the grid’s floor of 10⁻⁶ — which is no inner penalty at all — for the first twelve steps, and from twenty steps on it holds 2.15·10⁻² and never moves again. For the first twelve steps the projection is doing the whole of the regularisation and the penalty is switched off; from twenty it is doing all of it and the projection has stopped mattering. The two knobs hand over at a point rather than sharing the work throughout.

That is a better statement of what this construction is than “two parameters instead of one”. It is one parameter with two implementations, and the run crosses from the implementation that is a truncation to the implementation that is a filter somewhere around step sixteen — which is exactly where the section below finds the projected problem becoming ill-conditioned in its own right.

What the rule costs against knowing the answer #

The oracle is also the price list for the rule, and it is worth reading because this collection’s regularisation field has spent essays on how far a chosen parameter sits from the best one.

GCV’s final error is 0.14286 and the oracle’s is 0.14057, so the rule is 1.6 per cent worse than knowing the answer. That is a small number and it is the right one to compare against — not against the unregularised run’s 160.77, which is a comparison with a method that has no parameter rather than with a better choice of this one.

Two things follow. The first is that the inner rule is cheap in accuracy as well as in arithmetic: a rule reading only the data gives up under two per cent against a rule reading the answer, on a problem where the outer parameter chosen badly gives up a factor of a thousand. The second is that the 1.6 per cent is not the interesting margin. The best fixed λ in the table above reaches 0.1400, which is better than GCV’s 0.14286 and better than the oracle-at-every-step’s 0.14057 — because a λ held constant from the first step is a different object from the best λ at each step, and on this problem the constant is the luckier one.

So the honest ordering is: a well-chosen constant, then the per-step oracle, then GCV, then a long way down the unregularised run. Three of those four are within two per cent of each other and the fourth is off by a factor of a thousand, which is the whole argument for the construction and is not an argument about which rule to use inside it.

It is the penalty, not the rule #

The reading the table above invites is that the rule is doing the work: GCV watches the projected problem grow ill-posed and raises λ to match. That reading is wrong, and the check is cheap — fix λ once, never revisit it, and run the same forty steps.

Any λ of about 0.02 or above removes the turn completely, and every one of them lands on the floor — the best of the fixed runs, at λ = 0.02, reaches 0.1400, which is better than both the adaptive run and the best unregularised iterate. A penalty chosen once and left alone is enough.

What a fixed penalty does not survive is being too small. At λ = 0.01 the run turns again, gently; at λ = 0.001 it turns properly and ends 9.5 times above its own best. A penalty an order of magnitude below what the subspace has just admitted suppresses nothing that the subspace has just admitted, which is the same sentence as the σ_min table one paragraph up.

So the inner rule’s job is not to remove the turn. It is to remove the need to know in advance which λ is large enough — and that is the outer rule’s job moved one level down rather than abolished. This construction redistributes the difficulty; it does not eliminate it. The redistribution is worth having because the new question has a much flatter answer: a factor of ten in λ is the difference between working and not, where a factor of two in the step count was.

The projection is a truncation until it stops being one #

There is a reading of the table above that makes the whole construction unsurprising, and it is worth stating because it is nearly right.

At small k the projected problem is well conditioned because the subspace has not let the difficult part of the problem in. That is a truncation — the same object the rank essay is about, arrived at without anybody choosing a cut-off. It is why stopping early was ever a regularisation, and it is why the two knobs land on the same floor.

What the table shows is where that reading expires. By thirty-two steps the projected problem is ill-conditioned in its own right, and the projection has stopped being a truncation and become a faithful reproduction of a problem that has no answer in it. From there, only the inner penalty is regularising anything.

The one thing the construction cannot skip #

The bases have to stay orthogonal, and on this problem the plain three-term recurrence does not keep them.

The right-hand column is the Lanczos field’s ghost arriving in a regularisation method. A lost basis produces a projected matrix with two singular values where the problem has one, and every quantity computed from that matrix — the filter, the trace GCV divides by, the residual the discrepancy principle reads — is then computed on a problem the method is not solving.

What makes it worth stating as a rule rather than a caution is that the error is often barely affected. A method can be choosing its parameter on a fictional spectrum and returning a reasonable answer, which is the condition under which nobody investigates.

What it costs #

Per step, the hybrid method adds one sweep over a grid of forty-three penalties, each of which is a least-squares solve of a (2k+1)×k bidiagonal-plus-diagonal system. At k = 28 that is forty-three solves of a 57×28 system against one solve of a 29×28 system — arithmetically trivial beside the two products with A that the step itself costs once the matrix is large, and not trivial at all at the sizes drawn here, where A is 64×64 and dense.

That is the honest scaling statement and it runs in the method’s favour: the inner problem’s cost depends on k and the outer problem’s on n, so the arrangement gets cheaper relative to the iteration exactly as the problem gets big enough for an iterative method to be the right choice.

What it does not cost is a decision. The comparison that matters is against running LSQR and stopping well, and stopping well requires a rule, and the rules do not reach the oracle.

Two knobs, and only one of them is now a knob #

The step count has not disappeared. It still decides how much arithmetic is done, and it still has to be large enough for the subspace to contain the answer — below twelve steps the error is visibly worse whatever λ is chosen, because no penalty can recover a component the subspace does not have.

What it has stopped being is a modelling decision. Past the point where the subspace holds the answer, running longer changes nothing that matters, and the parameter that decides how much of the data to believe is the inner one. The outer loop can then stop on a budget, on a residual, or on the wall clock, and none of those choices is wrong by a factor of a thousand.

What the drag does #

The slider is the noise level. Less noise moves the floor down and the unregularised turn later, in exactly the way the step-count essay’s figure does — at 0.1% noise the unregularised run’s best sits further right and lower, and its overrun by the end of the run is larger rather than smaller, because a smaller σ_min is reached before the run ends and the noise is divided by it just the same.

What does not change at any position of the slider is which of the two curves has a minimum in it. That is the claim the figure is drawn to be falsifiable about, and it is asserted at every frame: the unregularised run must end at least five times above its own best, and the regularised one must end within 50% of its own.

A step count that is not a parameter #

Where the iteration count is a regularisation parameter, more steps eventually hurt. Where it is a polynomial degree for a matrix function, more steps are simply more accuracy until rounding stops them.