A parameter chosen on a smaller problem

Choosing without knowing scored the published rules for picking a regularisation parameter against an oracle that requires the exact answer, and none of them reached it. That was a comparison between rules, on one problem, all of them looking at the same 64×64 matrix.

The previous essay put a penalty inside a Krylov method, and in doing so moved the choice somewhere else. The parameter is now chosen on the projected problem — a bidiagonal matrix of twenty-five rows and twenty-four columns, built by the iteration itself out of the problem it was handed. Every rule from the regularisation field can be run on it, because it is a least-squares problem with a matrix and a right-hand side like any other.

The question is what a rule is reading when it reads a projection.

The rule that transfers by an identity #

The discrepancy principle asks for the largest λ whose residual is still no larger than the noise. It is the only rule in the field that has to be told ‖e‖, and the standard objection is that nobody knows ‖e‖.

Under projection it has a property none of the others do. The left basis Uₖ₊₁ is orthonormal, so ‖b − A Vₖ y‖ equals ‖β₁e₁ − Bₖ y‖ for every y — the residual of the small problem is the residual of the large one. A rule that consults nothing but a residual and a noise level is therefore consulting identical numbers on both problems, and must return the same answer.

It does, and “the same” is meant literally:

The same grid point, ten times out of ten. Nothing is being approximated: an identity holds, and the rule inherits it.

What the identity does not do is make the rule available, and the figure’s own readout says where it is not. The discrepancy principle asks for the largest λ whose residual is no larger than the noise, and on a subspace too small to have reduced the residual that far there is no such λ: the rule returns nothing at all.

Across noise levels of 10%, 5%, 2%, 1%, 0.5%, 0.2% and 0.1% the discrepancy principle first becomes defined at 4, 4, 6, 8, 12, 20 and 24 steps. So the rule that transfers exactly is the rule that is unavailable longest, and the subspace it needs grows by a factor of six over the same two decades in which the projected GCV’s bias moves by a factor of two. A hybrid method that reaches its floor in twelve steps at 0.1% noise has no discrepancy principle to consult when it gets there.

The rule that does not #

Generalised cross-validation is the rule that needs nothing but the data. It minimises the residual squared over the square of trace(I − AA⁺) — a rule that needs nothing but the data, and that trace is the part that does not survive.

The trace of the influence matrix counts the data the fit did not consume — n minus the effective number of parameters. On the projected problem there is no n. There are k + 1 projected rows, and the denominator is bounded by k + 1 whatever the problem’s dimensions were:

On a problem with sixty-four rows. The criterion at four steps and the criterion at forty-eight are two different criteria, and neither is the criterion the rule was derived for.

The interesting part is what that does, which is much less than it sounds like and in a very particular way.

The λ it selects hardly moves — at this noise level. Across the whole run, at 1% noise, it stays between 3.2·10⁻² and 6.8·10⁻² — a factor of 2.15 while its own denominator moves by a factor of 27. GCV is a ratio, its numerator is a residual that changes by orders of magnitude as λ crosses the noise level, and a denominator wandering by a factor of twenty-seven cannot move the minimum of something that steep.

And “hardly moves” is a property of the noise rather than of the rule. Over the seven noise levels the selection’s range across the run reads 2.15, 1.47, 2.15, 2.15, 3.16, 6.81 and 14.68, while the denominator it is supposedly insensitive to climbs by 31, 30, 28, 27, 26, 23 and 21 — falling. The two go opposite ways. At a tenth of a per cent the rule’s answer depends on where in the run it is asked by a factor of fifteen, on a denominator that varies less than the one at ten per cent where it varies by two.

The mechanism the argument gives is still the right one and its scope is narrower than the sentence claimed. A steep numerator is what stops a wandering denominator moving the minimum, and the numerator is steep in λ near the noise level — so as the noise falls and the optimal λ falls with it, the region where GCV’s ratio is steep shrinks towards zero and the denominator gets its say. Insensitivity is bought by the noise, and it is spent by the time the noise is a thousandth.

But it is biased, and the bias has a size. Against the same rule applied to the full problem:

The λ grid steps by a factor of 1.468. So the bias is two grid steps at twenty-four, one grid step at forty, at every noise level across two decades, with a single exception at the smallest noise and the smallest subspace where it is three.

A bias that depends on the subspace size and not at all on the data is exactly what “the denominator counts the subspace” predicts, and it is the strongest available evidence that the mechanism named above is the mechanism operating. It is also always in the same direction: the projected rule chooses more regularisation than the full one, because a smaller denominator makes small λ look worse than it is.

How much of that regularity is the grid #

“Two grid steps at twenty-four, one grid step at forty, at every noise level across two decades” is a striking sentence, and it is stated in units of the grid — which is a warning rather than a coincidence, because a parameter chosen by minimising over a grid is only ever reported to the grid’s resolution. A quantity that varies smoothly will be rounded to whole steps, and a rounded quantity looks constant.

So it is worth re-running on a finer grid. The essay’s steps by a factor of 1.4678; this one steps by 1.1007, four times finer.

At k = 24 the bias becomes 1.957 at 10% noise, 2.154 at 1% and 4.642 at 0.1%, against a coarse 2.154, 2.154 and 4.642. At k = 40 it becomes 1.334, 1.334 and 1.616, against a coarse 1.468 three times over.

The finding survives and its exactness does not. Every fine value sits within one coarse step of its coarse value, so the coarse grid was resolving the minimum correctly — nothing here says the earlier numbers are wrong. What it says is that the bias at k = 40 is not one number: it runs from 1.33 to 1.62 across two decades of noise, and the coarse grid rounded all three to 1.468 because 1.33, 1.33 and 1.62 all fall within half a step of it.

One number in the table above is worth separating out, because it is the one case where the two grids disagree about the shape rather than the value. At 0.1% noise and k = 24 the bias is 4.64 on both grids — more than twice what it is at the other two noise levels, and the essay’s own table records it as the single exception to the one-or-two-step regularity. The fine grid confirms it rather than dissolving it, so that exception is real: at the smallest noise and the smallest subspace the projected rule is choosing nearly five times the full problem’s λ.

That is the corner where the mechanism should bite hardest and does. A small noise level puts the full problem’s optimum at a small λ, and a small subspace gives GCV a denominator of a few — so the rule is comparing a residual that varies over orders of magnitude against a normalisation that has almost nothing left in it. The bias is a ratio of two small quantities there, and ratios of small quantities are where every measurement on this site gets large.

What survives, and the habit it argues for #

The mechanism stands and it is worth restating in the weaker form the finer grid supports.

The bias depends on the subspace and barely on the data. At k = 40 it varies by a factor of 1.21 across two decades of noise; between k = 24 and k = 40 it varies by a factor of 1.47 to 2.87 at fixed noise. The subspace moves it several times more than the noise does, which is what “the denominator counts the subspace” predicts and is the claim the section above was making.

And it is always in the same direction. Every one of the six fine-grid measurements is above one: the projected rule chooses more regularisation than the full one, at every subspace size and every noise level, because a smaller denominator makes a small λ look worse than it is.

What does not survive is the arithmetic exactness, and the way it failed is worth carrying past this rule. Every individual number in the coarse table is correct. The grid is a reasonable grid. Nothing about the measurement is wrong, and no residual, self-test or two-route check would have caught anything, because there is nothing to catch — the defect is in the reading, where a quantised observable was reported as a law.

The check costs one re-run at a finer resolution, and it is the same check the plateau exponent needed in a different disguise: before believing a regularity, vary the thing the measurement was quantised or fitted against. A striking constant is the one result most worth being suspicious of, because it is the one an artefact most easily produces.

What the bias costs, which is almost nothing #

At 1% noise the oracle’s λ is 2.15·10⁻² and returns 0.1406. The full problem’s GCV picks 3.16·10⁻² and returns 0.1413. The projected GCV at k = 32 picks 4.64·10⁻² and returns 0.1429.

Two grid steps of over-regularisation, and 1.6% of error.

That is not a defence of the bias so much as a statement about the terrain. This site’s combination field has spent two essays establishing that a wide band of sensible parameters lands on one floor, and a rule biased by two grid steps is still inside the band. The bias would matter on a problem whose error curve had a sharp minimum, and the reason this one does not is the same reason regularisation is necessary at all: the singular values decay smoothly with no gap, so nothing about the answer changes abruptly with the cut-off.

The rule that declines #

There is a third behaviour, and this site has an established preference about it.

Below eight steps the discrepancy principle returns nothing at all. Not a bad λ — no λ. In a six-dimensional subspace, the residual at λ = 0 is still above the noise level, because the projection has not yet let in enough of the problem for the data to be fitted that well. The rule asks for the largest λ whose residual is under the noise, and there is no such λ.

GCV answers everywhere, including where the answer means nothing. The verified-bound essays made the argument for the other behaviour directly: an interval method’s three outcomes are there is a root here, there is no root here, and nothing can be said, and the third is what makes the first two worth having. A rule that always returns a number cannot distinguish between a problem it has understood and one it has not.

In practice the distinction is small here, because the errors at k ≤ 6 are close together whatever λ is used — 0.175 and 0.150 at two and four steps, from either rule. But the reason they are close is that the subspace is doing the regularising at that size, which the previous essay’s condition numbers show directly: at two steps the projected problem has κ = 1.38 and there is nothing for a penalty to suppress.

The third rule, and why it half transfers #

The L-curve reads two coordinates — the residual and the norm of the solution — and looks for the corner where the curve bends. Both coordinates survive projection, and the second does so for the same reason as the first: Vₖ has orthonormal columns, so ‖Vₖ y‖ equals ‖y‖ exactly, measured here at 8.9·10⁻¹⁶ and at zero.

So every point of the projected L-curve is a genuine point of an L-curve. And at forty steps the projected corner is the same grid point as the full problem’s — 6.813·10⁻³, error 0.1944, which is the corner’s own known shortfall and not a projection effect.

At twenty-four steps it is not. The projected rule returns 1.468·10⁻⁶ — the far end of the grid, nowhere near a corner anybody would draw — and an error of 0.2297.

The reason is worth separating from the trace story, because it is a different failure. Every point transfers exactly; the corner does not, because a corner is a property of the whole curve, and the projected curve is truncated. With twenty-four directions available, driving λ towards zero cannot make ‖x‖ large, since the solution cannot leave the subspace — so the vertical arm of the L, which is the thing the corner is the corner of, is simply absent. The rule then finds the largest curvature somewhere else and reports it with no indication that the feature it was looking for was not there.

That is the third behaviour on this page: a rule that is exactly right pointwise and wrong globally. GCV is biased by a knowable amount, the discrepancy principle is exact or undefined, and the L-curve is correct at every point and looking for something the small problem does not contain.

What a lie costs inside a subspace #

The discrepancy principle’s fragility is that it has to be told ‖e‖. The transfer identity means the projected rule inherits the fragility exactly — the same λ is chosen from the same lie — and the answers are not the same at all.

Understating the noise by a factor of ten costs a factor of 5,000 on the full problem and a factor of 28 inside the subspace. The rule made the identical mistake in both cases; what differs is how much damage the mistake could do, and the subspace has only thirty-two directions to be wrong in.

This is krylovreg.js’s own finding one construction along. There, the integer knob degraded gently where the continuous one did not, because a run has an end. Here the continuous knob degrades gently too, for the same reason and by a different mechanism: a run has an end, and so does a subspace.

Overstating the noise costs 12% either way, which is the asymmetry the regularisation field already measured, unchanged by projection.

Choosing on a small problem is not choosing cheaply #

The obvious reason to want the parameter chosen on the projection is cost. A sweep over forty-three penalties on a 25×24 bidiagonal system is nothing; the same sweep on the full problem needs a factorisation or a singular value decomposition per parameter, which is what the regularisation field pays and why its figures are drawn at n = 64.

That is real, and it is not the interesting half. The interesting half is that the projected problem is available and the full problem may not be. An iterative method is chosen when A is too large to factorise or is only known through its action on a vector; in that setting the full problem’s GCV cannot be computed at all, because its trace needs the singular values. The projected trace needs the singular values of a 25×24 bidiagonal matrix, which cost nothing.

So the comparison drawn above — projected rule against full rule — is a diagnostic rather than a choice anybody has. It exists because the problem was constructed small enough for both to be run, which is the same reason the oracle exists on this site at all.

What is being asserted, and what would break it #

The identity is asserted at four subspace sizes and three penalties, with the worst relative disagreement 7.7·10⁻¹⁵; the transfer is asserted as equality of the chosen grid point at five noise levels and two subspace sizes; and the trace bound — that the denominator cannot exceed k + 1 — is asserted at every k drawn.

That last one is the refusal. Feeding the build a claim that the projected trace counts the problem’s degrees of freedom, at k = 8 on a 64-row problem, has to fail: the trace there is 1.03 and the claim says it exceeds thirty-two. If someone later replaced the projected trace with a scaled version pretending to be the problem’s — which is one of the published repairs for this exact bias — the refusal would stop accepting the counterexample and the build would say so.

What the drag does #

The slider is the noise level, and it moves one thing that matters: the subspace size at which the discrepancy principle becomes available. With less noise the residual has further to fall before it reaches the noise level, so a larger subspace is needed before any parameter can bring it down.

The trace curve does not move at all under the slider. It is a property of the subspace and of λ, and the data does not enter it — which is the whole argument of this essay drawn as an absence.

Below half a per cent of noise something else appears: GCV’s λ starts to move with k in earnest, a factor of 6.8 at 0.2% noise and 14.7 at 0.1%. That is not the trace catching up. It is the problem: at low noise the components the subspace admits late are still worth keeping, so the right λ genuinely falls as k grows, and the rule is following the answer rather than its own denominator. The assertion is therefore written in two halves either side of that noise level, in the precedent this site set at the mixed-precision threshold — a claim stated unconditionally where it is false over a third of the slider is a claim the figure would be quietly wrong about.

A parameter that can be chosen from a norm #

Some parameters have to be searched for. Others are set by a formula from a quantity already in hand, and it is worth noticing which kind is in hand: the number of squarings in a matrix exponential is chosen from ‖A‖ by a rule, and the search would cost more than the computation.