One draw in twenty

Choosing without knowing scored three rules for choosing a regularisation parameter against an oracle and then, clearing its own shortfall, scored them again over sixteen noise draws. Generalised cross-validation came out of the second measurement better than the first had suggested: a median excess over the oracle of 0.16%, landing on the oracle’s grid point on several draws, with a worst case of 12%. The same essay said, in a sentence it did not measure, that the rule “is known to fail occasionally and badly — its objective can be nearly flat”.

Both statements are true, and they are about different parts of a distribution that sixteen draws cannot see together. This essay draws a thousand, at each of five noise levels, and adds the two rules that essay named and left out: the unbiased predictive risk estimator, which is told the noise variance, and the quasi-optimality criterion, which is told nothing.

The median and the worst draw rank the rules in opposite orders #

At 0.1% noise, a thousand draws, the error each rule’s choice produces divided by the best available on the same draw:

Sorted by the median, the order is risk estimator, cross-validation, discrepancy principle, quasi-optimality, L-curve. Sorted by the worst draw it is discrepancy principle, quasi-optimality, L-curve, risk estimator, cross-validation — the first two and the last two exchange ends.

Neither order is wrong, and a comparison that reports one has chosen a reader. A caller who runs the rule on many independent problems and cares about the typical answer wants cross-validation, which is within one and a half per cent of the oracle on half its draws. A caller whose one answer goes straight into something else — an image that is published, a model that is fitted to it — takes whichever draw arrives, and one in eighteen of those is an answer more than ten times worse than it needed to be.

The mean says which of those callers the average belongs to. Cross-validation’s mean excess at 0.1% noise is 905 times the oracle, which is the fifty-seven failures and nothing else; its other 943 draws would give a mean near 1.05. The quasi-optimality criterion’s mean is 1.23. Averaged over draws, the rule with the best median is by far the worst rule on the page.

The counts hold still while the medians trade places #

The same thousand draws at every noise level from 10% to 0.001%:

The medians reorder from row to row. At 10% noise the discrepancy principle has the best median, 1.000, and cross-validation’s is 1.146, fourth of five. At 0.01% the quasi-optimality criterion has the best, 1.001. At 0.1% it has the worst but one. A ranking by median drawn at one noise level describes that noise level.

The counts do not. Cross-validation exceeds ten times the oracle on between forty and fifty-seven draws in a thousand at every level; the risk estimator on between eleven and seventeen; the discrepancy principle and the quasi-optimality criterion on none, and neither of them ever reaches one and a half. What moves with the noise is the size of a failure rather than its frequency: cross-validation’s worst draw falls from seven million at 10% noise to 1,750 at 0.001%, because the catastrophe it lands in is the unregularised solution, and that is a smaller catastrophe when there is less noise to amplify.

Two minima, less than a per cent apart #

The mechanism has a picture, and the picture is of one draw. Cross-validation minimises

G(λ) = ‖A x_λ − b‖² / (n − Σfₖ)²

over the grid, where Σfₖ is the trace of the influence matrix — the effective number of components the solution keeps. On a well-behaved draw G has one minimum and it sits at the oracle.

On draw 303 it has two.

The two minima of the objective differ by nine parts in a thousand. The errors beneath them differ by a factor of twelve and a half. The rule is doing exactly what it was derived to do — minimising an estimate of the prediction error — and the estimate cannot resolve a difference of nine parts in a thousand, because it is computed from sixty-four noisy numbers and its own draw-to-draw scatter is larger than that.

This is what “its objective can be nearly flat” means when it is measured, and it is more specific than the phrase. The objective is not flat between the two minima; it rises by several per cent between them. What is flat is the comparison between them: two separate valleys whose floors happen to lie within the objective’s own noise, only one of which is the right answer.

Where the objective dips in the wrong place #

G is a ratio of two quantities that both fall as λ falls. The residual in the numerator falls as more components are kept. The denominator, the number of components not kept, falls with it. Where the residual falls faster than the square of the denominator, G falls.

Deep in the noise-dominated part of the spectrum, each component kept removes one noise coefficient from the residual and one unit from the denominator, and on average the ratio climbs, which is why the right minimum is a minimum. But the removed coefficient is a random number, and a run of noise coefficients that happen to be larger than average makes the residual fall faster for a stretch, and the objective dips.

That is measurable on the failures. At 0.1% noise, on the forty-eight draws where cross-validation fails inside the search rather than at its floor, the coefficients uₖᵀb whose singular values lie within a decade of the chosen λ have a mean square 1.49 times the value noise should give them — the median over those forty-eight failures, with one in ten above twice. The dip is where the draw put a cluster of large noise coefficients, and the rule reads the cluster as the place the signal ends.

The bottom of the search is a minimum too #

The other kind of failure is at the floor of the grid, λ = 10⁻⁸, and it has a different cause.

Twelve of the blur’s sixty-four singular values are below 10⁻⁸. At that λ they are the components discarded, so the residual is made of twelve coefficients and the denominator is n − Σf = 12.3. The objective there is essentially the mean square of twelve noise coefficients divided by twelve. A mean of twelve random squares is a small sample, and on some draws it comes out small.

On the nine draws at 0.1% noise where cross-validation fails at the floor, the mean square of those twelve coefficients is 0.30 of its expected value at the median and no more than 0.44 on any of them. Across the other draws the same quantity has a median of 0.97, and one draw in ten is below 0.58. The floor minimum is the draw having happened to put little noise in the dozen directions the search reaches last.

A floor is a parameter of the rule that has none #

If the floor minimum is made of the components below the floor, then moving the floor changes how many there are, and it should change how often the rule fails. It does.

At 10⁻¹⁴ no singular value is below the floor, the denominator is a small fraction of one component, and the objective at the floor is a ratio of two numbers that are both nearly nothing. One draw in five lands there. At 10% noise the counts are 38, 40, 43, 71 and 157; at 0.001% they are 21, 54, 69, 126 and 236.

So the rule advertised as needing nothing has a parameter, and it is the same kind of parameter choosing without knowing found inside the L-curve’s smoothing window: a decision nobody thinks of as part of the rule, sitting where nobody looks, moving the result by a factor of four or five. Implementations do bound the search, usually between the smallest and largest singular values or at some multiple of the machine precision, and each of those is a floor. The failure share a user sees is a property of that choice as much as of cross-validation.

Why a rule told nothing need not fail #

The quasi-optimality criterion is told exactly as little as cross-validation, and in five thousand draws it never costs more than 1.41. The difference is in the shape of what each rule minimises at small λ.

The quasi-optimality criterion minimises the change in the solution between neighbouring points of the grid. At small λ the change is made of components whose singular value is near λ, each contributing its coefficient divided by that singular value. The coefficient is noise and varies from draw to draw by a factor of two or three. The singular value falls by a factor of ten every few indices. A random factor of three cannot compete with a systematic factor of ten, so the criterion’s objective climbs steeply into the noise-dominated region on every draw, and it cannot be fooled into choosing there.

Cross-validation’s objective at small λ is a ratio of two things that both vanish, each estimated from the few coefficients not yet absorbed, and a ratio of small samples is exactly the quantity that scatters. The risk estimator sits between them for a reason that is visible in its formula: it adds 2σ²Σf − nσ² to the residual, a penalty on an absolute scale fixed by the variance it is told, so a small sample of discarded coefficients can make it cheaper but not arbitrarily cheaper. It fails on eleven to seventeen draws in a thousand instead of forty to fifty-seven.

The quasi-optimality criterion pays for its immunity in bias. At 0.1% noise its choice sits above the oracle’s λ on 906 draws of the thousand — it over-smooths almost every time, by enough to cost 28% on the median draw. At 10% it sits below the oracle on 884 and costs 4%. A rule that is never catastrophic and usually a little wrong, in a direction that depends on the noise, is a trade and not a victory.

A share settles where a worst case does not #

The tail a sample never reaches measured an estimator whose worst case kept falling as more matrices were drawn, and concluded that a running worst case can only get worse. That is true here too, and it is not the useful number.

The failure share of cross-validation behaves like that estimator’s share of exact answers rather than like its worst case. At 0.1% noise, counted after 100, 250, 500, 1,000, 2,000 and 4,000 draws, the share of draws more than ten times worse than the oracle reads 3.0%, 3.6%, 5.2%, 5.7%, 5.5% and 5.8%. After a thousand it moves by a few tenths of a point. The worst draw over the same counts reads 25,000, 110,000, 140,000, 140,000, 140,000 and 150,000 — still creeping, as a maximum must.

That separates the two things a thousand draws can report. The share is a measurement, settled to about a percentage point, and it is what a caller needs in order to decide whether to trust the rule. The worst case is a running record, and it says only that the tail reaches at least that far.

It also puts the sixteen draws in their place. With a failure rate of 5.7%, sixteen independent draws all come out clean with probability 0.943¹⁶ = 0.39. The clean sixteen of the earlier table were the single likeliest outcome of a sample that small, and they were no evidence that the tail was absent. What a single draw cannot report made the same point about a spread, one level down: the number a small run cannot produce is the one that decides whether its other numbers mean anything.

A second rule as an alarm #

A caller with one draw cannot compute a share. The caller can compute two rules.

Cross-validation’s failures choose a λ far below where the quasi-optimality criterion chooses, and its ordinary draws do not. Flag a draw whenever cross-validation’s λ is more than thirty times smaller than the criterion’s, and over a thousand draws:

At 0.1% and 0.001% the alarm catches every failure, at the price of ringing on one ordinary draw in nine or sixteen. At 10% it catches two thirds and never rings falsely: the failures there are almost all of the interior kind, a factor of ten or twenty below the oracle’s λ rather than a factor of a thousand, and a threshold of thirty misses the milder ones.

The alarm needs no answer and no noise level, which makes it the same kind of check as a test with no answer in it: two computations that should agree, compared, with their disagreement read as evidence. It does not choose λ. What it does is turn cross-validation’s worst property — a failure that arrives with no warning — into a failure that arrives with one, on this problem, at a known cost in false alarms.

What a comparison of rules should report #

Three numbers per rule, and the earlier essays on parameter choice reported one of them.

The median excess over the oracle, which is what cross-validation is good at and what a single draw approximates.

The share of draws beyond some multiple, which settles within a thousand draws and is what the median hides. For the rules here it runs from zero to six in a hundred, and the rules with the best medians are the ones that are not zero.

And what the rule reads that nobody set — the floor of a search, the smoothing of a curvature, the τ in a residual test — because those move the share, sometimes by a factor of five, without appearing in the rule’s description.

What none of this establishes is a ranking beyond the problem measured. Every number above is one blur, one signal, white noise and a grid of sixty-one values of λ, and four knobs and one floor is the reminder that on this problem the attainable errors of very different methods lie within 3% of each other — which is exactly the situation in which the tails, rather than the floors, are where rules differ. On a problem whose error curve has a sharp minimum the medians would separate further and the tails might not. That is unmeasured.

Where this goes from here #

The same five rules under a different penalty. Everything here penalises ‖x‖. Cross-validation’s floor failure is made of the components the penalty discards last, and a derivative penalty discards different ones first. The corner reads the norm it is drawn in measures the rules in the general form, and the L-curve’s cost in particular turns out to depend on the penalty rather than on the rule.

The projected problem. A parameter chosen on a smaller problem showed cross-validation inside a Krylov method reading a denominator bounded by the size of the subspace. A floor minimum made of the last dozen discarded components should behave differently when there are only twenty-five components in all; how often it fails there is the measurement that would say whether hybrid methods inherit this tail or escape it.

An alarm that chooses. The disagreement between two rules flags failures; the next question is whether a rule that takes the larger of the two choices, or the quasi-optimality choice whenever the alarm rings, keeps cross-validation’s median and loses its tail — and what that costs on the draws the alarm rings on falsely. The alarm has a number of its own that nobody set, the factor of thirty, and by the standard of the section above its share of missed failures and false alarms has to be reported as that factor moves: at 10% noise it already misses a third of the failures, which says the factor that suits one noise level is not the one that suits another.

And the noise level the discrepancy principle needs, which thirty-two coefficients instead of a noise level read from the same data: the principle handed that estimate has no tail at all at or below 1% noise, which makes it the rule the share column above is quietest for.