Choosing without knowing

The first essay in this field establishes that the answer is a choice and that both standard methods make it by weighting one sum. The second finds the index where the data stops carrying signal and shows it is not the index where stopping is best.

This essay is about the three published rules for making the choice, and about the fact that they can be scored here — against a parameter that requires the exact answer and is therefore not a method at all.

The oracle, which is not a method #

The problem is constructed, so the exact signal is known, so for every λ on the sweep the actual relative error is computable. The λ that minimises it is the best any parameter choice could do.

That is not a method and it must not be mistaken for one. It requires the answer to the question being asked. It is here for one reason: without it, three rules can only be compared with each other, and a comparison between three heuristics tells a reader which is most popular rather than which is right.

assertNoRuleReachesTheOracle asserts that no rule beats it — which is a statement about the experiment rather than about the rules, and would catch a rule that had cheated by touching the exact answer. And assertTheRegularisationAssertionsReject feeds the claim that a rule beats the oracle and requires it to fail, so a future refactor that accidentally handed a rule the truth would stop the build.

This is exact ground truth in the one place a field could not be written without it.

The three rules, and what each of them knows #

They differ in what information they are entitled to, and that is the interesting axis rather than their names.

The discrepancy principle is told the noise level. Choose the largest λ whose residual is still no bigger than ‖e‖, on the reasoning that fitting the data more closely than the noise permits is fitting the noise. It is the only rule here that needs something outside the data, and the standard criticism of it is that nobody knows ‖e‖.

The L-curve is told nothing. Plot ‖x‖ against ‖Ax − b‖ on log–log axes as λ sweeps; the curve has a corner, and to the left of it the noise is being amplified while to the right the signal is being thrown away. Choose the corner, found here as the point of maximum discrete curvature.

Generalised cross-validation is also told nothing. Minimise ‖Ax_λ − b‖²/trace(I − AA⁺_λ)², which is a leave-one-out prediction error with the leaving-out done in closed form. The trace is available exactly from the filter factors — it is Σ(1 − fₖ) — which is what makes GCV cheap once the SVD is in hand and expensive otherwise.

What they score #

At 64 points with 0.1% noise:

GCV lands on the oracle’s λ exactly — the same grid point, not merely nearby. The discrepancy principle over-smooths slightly and pays 6%. The L-curve under-smooths substantially and pays 129%.

Three things about that table are worth saying carefully.

It is one problem. No claim is made that GCV wins in general, and the drag exists partly to show that the ordering is not stable across noise levels. The assertion is deliberately weak — that at least one rule pays a real price — because asserting a ranking would be asserting something about this problem and calling it a result.

GCV landing exactly is a property of the grid. The sweep has 61 λ values over eight decades, so “exactly” means the same grid point rather than the same real number. On a finer grid the two would differ slightly. What the coincidence does establish is that GCV’s minimum and the error’s minimum are in the same place to within a sixth of a decade, which is what the claim amounts to.

And the L-curve is not broken. The corner is a real feature of the curve, it is where the two regimes meet, and the curvature maximum finds it. Choosing the corner is simply not the same as choosing the minimiser of the error, and the figure shows both points on one curve so the difference between them is visible rather than argued.

A parameter for choosing a parameter #

The L-curve has a detail that deserves stating rather than hiding: computing the curvature of a discrete curve from three consecutive points is noisy, so the implementation smooths first.

That smoothing is a parameter of the rule for choosing a parameter. The rule advertised as requiring no information about the noise requires a decision about how much to smooth its own curve, and different decisions move the corner.

This is not a criticism unique to the L-curve — GCV’s minimum is also found on a grid, and the grid is a choice — but it is worth naming because the L-curve is usually presented as the parameter-free option, and a parameter-free rule with a smoothing window in it is a rule with a parameter in a place nobody looks.

The asymmetry, which is the finding #

The obvious objection to the discrepancy principle is that ‖e‖ is unknown. The obvious response is that it is often known approximately. So the measurement worth making is not how well it does when told the truth — 6% — but how fast it degrades when told a wrong one.

Fed a noise level ten times too large and ten times too small:

The same factor of ten, in the two directions, costs 27% and five orders of magnitude.

Over-stating the noise over-smooths: the answer is blurrier than it needed to be, some detail is lost, and the error rises gently. Under-stating it under-smooths: the rule keeps searching for a λ whose residual is small enough, does not find one until λ is at the bottom of the grid, and returns the unregularised catastrophe the first essay measures at 5.5·10⁸.

The assertion states the direction of each — an overstated level over-smooths, an understated one under-smooths — because those are properties of the rule. The sizes are properties of this problem and are reported rather than asserted.

The practical conclusion is a rule about which way to be wrong, and it is unusually clear-cut: when the noise level is uncertain, over-state it. The penalty for caution is a factor of 1.3 and the penalty for optimism is a factor of ninety thousand.

That is the same shape as the cliff in the block-size scan — a gradual slope on one side of an optimum and a discrete failure on the other — and the same practical advice falls out of both: when the curve is asymmetric, err towards the gradual side.

Why no rule can reach the oracle, in principle #

Not a limitation of these three. Every rule that uses only A and b is choosing λ from information that does not determine the answer, which is the definition of the problem this field is about.

The oracle uses x_true. The discrepancy principle uses ‖e‖, which is one number about x_true’s absence. The L-curve and GCV use nothing beyond the data, and are therefore inferring the noise level from the shape of the sweep — which is a genuine inference and a lossy one.

So the rules form a ladder in information rather than in cleverness, and the measured errors are roughly monotone in it: the oracle at 0.1051, the rule told ‖e‖ at 0.1118, and the rules told nothing at 0.1051 and 0.2406. GCV’s position on that ladder is the anomaly worth noticing — it is told nothing and does as well as the oracle here — and the honest reading is that GCV’s inference happened to be right on this problem rather than that it has escaped the ladder.

What the L-curve is actually a picture of #

Worth keeping, because the figure is drawn on those axes and the axes carry an argument.

‖x‖ against ‖Ax − b‖ is a trade-off curve, and its two arms are the two failure directions the first essay measures. The vertical arm on the left is λ too small: the residual is as small as it will get and ‖x‖ is climbing without limit, which is the amplified noise having to go somewhere. The horizontal arm on the right is λ too large: ‖x‖ has collapsed towards zero and the residual is climbing, which is the signal being thrown away.

The corner is where neither is happening much. That is a genuine and useful thing to identify — and it is a statement about where the curve bends, not about where the error is least, and those are two different points on the same curve. The figure marks both.

Why the sweep is a sweep #

A detail of construction that decides what the comparison means.

Every rule is scored on the same grid of sixty-one λ values over eight decades, and every λ on it is applied to the same noise — the noise vector is drawn once from a fixed seed and added before any λ is chosen. So a sweep over λ is a sweep over λ, rather than over λ and the noise together.

That sounds obvious and it is the discipline the gap sweep in the subspace field had to adopt for the same reason: with the perturbation redrawn at every point, a curve that should have been smooth in the parameter would have been a scatter of unrelated experiments, and the shape being measured would have been the seed’s rather than the parameter’s.

It also means the oracle is the oracle for this noise draw. A different draw moves it, and the rules’ errors move with it in a correlated way. The essay reports one draw and does not average, which is a shortfall recorded rather than concealed — acrossSeeds exists in this site’s library and this field does not use it.

Three rules, three kinds of failure #

The errors in the table are one number each, and the ways they arrive at them are not the same kind of thing.

The discrepancy principle fails by being told wrong. Given ‖e‖ correctly it is 6% off the best, and given it wrongly it is anywhere. Its error is entirely an error in its input, which is a comfortable place for a rule to be: it is right about what it needs and honest about needing it.

The L-curve fails by answering a different question. It finds the corner reliably, on this problem and on others, and the corner is 2.29× off the best. Its error is not an error at all in its own terms; it is a mismatch between what it optimises and what a reader wants.

And GCV fails by not always working. It landed on the oracle here. It is known to fail occasionally and badly — its objective can be nearly flat, so its minimum is sometimes decided by noise in the noise — and a rule that is exactly right most of the time and occasionally far wrong is a harder thing to advise about than one that is consistently 6% off.

Which is the most useful summary this field can offer: the three rules are not three attempts at the same thing with different accuracies. They fail differently, and the choice between them is a choice about which failure is acceptable.

The oracle is what makes this a field rather than a survey #

A closing note about method, because the device is unusual enough to be worth defending.

A comparison of parameter-choice rules without an oracle can say two things. It can say what each rule chooses, which is a description. And it can say that they disagree, which is a fact about them rather than about the problem. Neither says which to use.

With an oracle it can say a rule costs 6% and another costs 129%, on a problem where the answer is known — and it can then be honest about the fact that the answer is known only because the problem was built for the purpose.

That trade is one this collection has made repeatedly. The Hilbert matrix’s exact rational inverse is not a realistic problem; it is the one place a forward error can be known rather than estimated, and an answer that is known is a whole essay about what that buys. The discrete Laplacian’s closed-form spectrum is not a realistic operator; it is what lets every stationary rate be checked against a number that was not measured.

A constructed problem is a measuring instrument. What matters is that it is stated as one — which is why every figure in this field draws the oracle in a different colour, marked as requiring the answer, rather than as a fourth method.

The rules that are not here #

Three more are in common use and none of them is measured, which is worth listing so the comparison is not read as exhaustive.

The unbiased predictive risk estimator, which needs the noise variance and estimates the prediction error directly rather than through cross-validation. It sits between the discrepancy principle and GCV in what it is told.

The quasi-optimality criterion, which needs nothing and chooses the λ at which the solution changes least — a stability argument rather than an error argument, and one that fails in a completely different way.

And residual-based stopping for an iterative method, which is what most large computations actually use, and where the parameter is an integer and the sweep is the iteration itself rather than a separate loop.

Three is enough to show that rules using different information land in different places, which is the essay’s claim. It is not enough to rank them, and nothing here does.

What is left #

Iterative regularisation. Conjugate gradients on the normal equations, stopped early, is itself a regulariser with its own filter factors, and the parameter is the iteration count — an integer, chosen from the same three kinds of information. It is what anybody solving a large problem does, since it needs no SVD, and none of it is here.

The general form. Everything above penalises ‖x‖. Penalising ‖Lx‖ for a derivative operator L is what a real deconvolution does, and the parameter-choice rules all have general-form versions whose behaviour is not the same — the L-curve in particular changes shape, because ‖Lx‖ and ‖x‖ have different arms.

And multiple parameters. A problem with two regularisation terms has a two-dimensional trade-off surface rather than a curve, the L-curve becomes an L-surface, and “find the corner” stops being well defined. That is where the whole approach reaches its limit, and it is the case most modern inverse problems are in.