The excess is what the fit spent

Four folds feed one rule estimated the noise level of a blurred signal from the data alone: hold out each quarter of the samples in turn, fit the other three by Tikhonov regularisation on a grid of $\lambda$, add the held-out squares, and read the noise off the smallest total. On 960 draws the estimate was never below the true noise, and that was the property the discrepancy principle needed — told it, the rule’s worst draw stayed within 1.19 of the oracle where told one held-out quarter it had missed by eighteen. The estimate was high, though, by a median of 1.60 at the worst corner, and the essay gave a reason: “with few samples per unknown each fit, trained on three quarters, has fewer samples to fit with.” It closed on the obvious next step. “With $k$ folds each fit trains on $(k-1)/k$ of the samples, so the bias should shrink toward the noise as $k$ grows while the estimate stays above it. The prediction with a sign is that leave-one-out, the limit, gives an estimate whose median over the true noise is under 1.1 at every ratio and noise level, still never below the noise on any of the 960 draws, and that the discrepancy principle told it keeps its worst draw under 1.2.”

Two of those three hold. The first does not, and the reason it does not corrects the explanation it rested on. The bias was never the folds’. It is a property of the fit at the chosen $\lambda$, every cross-validation pays it whatever the folds, and once it is named it can be taken out — which produces an estimate that breaks the rule the earlier essay thought essential and costs the discrepancy principle nothing.

Leave-one-out without m fits #

Leave-one-out sounds expensive: $m$ samples, $m$ fits, each one a Tikhonov solve on a grid of 121 values of $\lambda$. For a linear smoother it is not. A Tikhonov fit at fixed $\lambda$ predicts the data by $\hat b = Hb$, with the hat matrix $H = U \operatorname{diag}(f_k) U^{\mathsf T}$ built from the singular vectors and the filter factors $f_k = \sigma_k^2/(\sigma_k^2 + \lambda^2)$. The fit that never saw sample $i$ predicts it with residual $r_i/(1 - h_{ii})$, where $r_i$ is the whole fit’s residual and $h_{ii}$ the sample’s leverage. That identity is the deletion formula one minus a leverage is a subtraction wrote down for least squares, carried through the filter; the observation that cannot be removed is the same $1 - h$ reaching zero.

So leave-one-out costs one singular value decomposition and a sum over samples at each $\lambda$, less than four folds’ four decompositions. Checked against the real thing — $m$ separate fits, each with one sample removed — on one draw at each ratio, the two totals agree at every $\lambda$ on the grid to a relative $1.3 \cdot 10^{-12}$. The measurement below uses the identity for leave-one-out and honest refitting for 2, 4, 8 and 16 folds, on the same 960 draws the earlier essays used: five grid sizes from 24 to 96 unknowns, 1.25, 1.5, 2 and 4 samples per unknown, noise of $10^{-2}$, $10^{-3}$ and $10^{-4}$ of the signal, sixteen draws each.

More folds stop helping at four #

At 1.25 samples per unknown the median falls from two folds to four — 1.374 to 1.288 at noise $10^{-2}$, 1.720 to 1.570 at $10^{-4}$ — and then nearly stops. Eight folds, sixteen and leave-one-out read 1.275, 1.270 and 1.271 at $10^{-2}$; 1.412, 1.397 and 1.397 at $10^{-3}$; 1.560, 1.518 and 1.519 at $10^{-4}$. Turn the dial and the shape is the same at every ratio, with the whole curve lower as the samples per unknown rise: at four per unknown leave-one-out reads 1.067, 1.087 and 1.102.

So the prediction fails on ten of the twelve cells. Leave-one-out’s median is under 1.1 only at four samples per unknown with noise $10^{-2}$ and $10^{-3}$, and it is within four per cent of four folds’ on every cell; the largest difference is 1.570 against 1.519. If the bias came from training on a fraction of the samples it would have shrunk by a quarter of itself between four folds and leave-one-out, which train on 75 per cent and on all but one. It shrinks by about a twentieth. Most of what training size does is between two folds and four, where each fit loses half the samples instead of a quarter, and two folds are high on every cell.

The excess is the fit’s degrees of freedom #

What every fold count shares is the fit. Cross-validation’s error at its minimum is the noise plus whatever the fit gets wrong about a sample it did not see, and a regularised fit at a moderate $\lambda$ gets something wrong about every sample: it spends some of the data on fitting the signal, and the spending shows up as variance in its predictions. The amount spent has a standard measure. The trace of the hat matrix, $\operatorname{df} = \sum_k f_k$, counts the degrees of freedom the fit uses — the number of parameters it is effectively estimating — and a residual from a fit that has spent $\operatorname{df}$ of $m$ samples carries noise on only $m - \operatorname{df}$ of them. The prediction error the fit makes at an unseen sample is then larger than the noise by about the reciprocal of that share, and the estimate read from it, over the noise, should be about $\sqrt{m/(m - \operatorname{df})}$.

It is. On all twelve cells the median leave-one-out estimate is within five per cent of the median $\sqrt{m/(m - \operatorname{df})}$: 1.271 against 1.259, 1.397 against 1.374, 1.519 against 1.472 at 1.25 samples per unknown; 1.067 against 1.069, 1.087 against 1.084, 1.102 against 1.097 at four. The share of the samples the fit spends is what moves: 37, 47 and 54 per cent at 1.25 samples per unknown from the highest noise to the lowest, 12, 15 and 17 per cent at four. Lower noise means a smaller $\lambda$ at the minimum, more filter factors near one, more degrees of freedom spent, and a larger excess — which is the earlier essay’s observation that the bias is largest where the noise is smallest and the samples fewest, with a mechanism attached that has nothing to do with folds. Draw by draw the agreement is looser — the logarithms of the two correlate at 0.63 — because each draw’s $\operatorname{df}$ is read at a $\lambda$ on a grid and each draw’s estimate has its own luck.

Drawn against the ratio, the share falls the same way at every noise level and the three lines never cross. At 1.25 samples per unknown the fit spends 37 to 54 per cent of what it is given; at four per unknown, 12 to 17 per cent. That is the whole of the excess’s dependence on the ratio, read straight off the trace: $\sqrt{1/(1 - 0.54)}$ is 1.47 and $\sqrt{1/(1 - 0.17)}$ is 1.10, the two ends of the measured medians at the lowest noise. And it says why more samples per unknown help where more folds do not. A fold changes which samples each fit is trained on and leaves the fit’s appetite for degrees of freedom as it was. More samples per unknown leave the appetite roughly fixed, since the signal has the same number of things worth fitting, and divide it by a larger $m$.

The draws far above the diagonal are a second effect riding on the first, and where they sit says what it is. Seventy-nine draws read leave-one-out at more than three times the noise, and every one is on the coarsest grid, 24 unknowns, at noise $10^{-3}$ or $10^{-4}$: all sixteen draws at $10^{-4}$ on every ratio, and fifteen at $10^{-3}$ on the two lowest. None is on a finer grid, and none at noise $10^{-2}$. That is the signature the grid on which the discretisation stops mattering measured from the other side: on a coarse grid the discretised problem cannot represent the signal it is fitting to better than some fixed accuracy, and once the noise is below that accuracy the misfit is the larger error. Cross-validation measures everything the fit gets wrong about an unseen sample, and on those draws most of it is the model’s, which no choice of folds or $\lambda$ removes. The estimate there is not a noise level at all; it is the size of what the grid cannot say.

Never low, and the rule holds #

The rest of the prediction stands. Leave-one-out is never below the true noise on any of the 960 draws; its lowest is 1.014, at four samples per unknown. And the discrepancy principle told it keeps its worst draw under 1.2 at every ratio: 1.194, 1.193, 1.180 and 1.179, against four folds’ 1.19. The worst draws of the estimate itself are lower than four folds’ at the corners where it went furthest astray — 36 times the noise at 1.25 samples per unknown and $10^{-4}$, against four folds’ 51 and two folds’ 141 — but they are the misfit draws, and the rule shrugs them off for the reason the earlier essay gave: the residual curve is flat on the right, so a level too high costs a few per cent.

So leave-one-out is a little better than four folds on every count and the same on the one that mattered. Its cost is lower. Its bias is not, and the bias can now be named.

Taking the fit’s share out #

If the excess is $m/(m - \operatorname{df})$ in the square, then multiplying the estimate’s square by $1 - \operatorname{df}/m$ should take it out. That is the same correction that turns a residual sum of squares into an unbiased variance by dividing by the degrees of freedom left rather than by the samples — the denominator generalised cross-validation already uses, squared, in its objective.

It works on the median. With the share taken out, the median over the true noise is between 1.005 and 1.073 on every cell, and within 1.03 on eight of twelve. And it breaks the property the earlier essay held essential: the corrected estimate is below the true noise on 344 of the 960 draws — about a third — and as low as 0.645 at 1.25 samples per unknown. An unbiased estimate of a noise level is below it about as often as above, and that is what an unbiased estimate is.

Choosing without knowing found the discrepancy principle catastrophic when told a noise level ten times too small, and an estimate that shares the dips’ luck watched it miss by 570,000 times when told the least-squares residual’s estimate. Both are what a low level does to this rule. So a third of the draws below the noise looks like a disaster in waiting.

It is not. Told the corrected estimate, the discrepancy principle’s worst draw is 1.163, 1.162, 1.160 and 1.164 at the four ratios. Told the true noise it is 1.163, 1.162, 1.155 and 1.164. Told leave-one-out uncorrected, 1.194, 1.193, 1.180 and 1.179. The corrected estimate is as good as knowing the noise, on the worst draw at every ratio, and better than the estimate that was never low.

The two facts fit together once the size of the error is in view. What hurt the discrepancy principle before was an estimate low by a factor of ten or of hundreds of thousands, and the least-squares residual’s estimate was that low because it was read at $\lambda = 0$, where the fit had spent every degree of freedom it had. The corrected estimate is low by at most 35 per cent. On these problems the residual curve is steep enough that a level a third low moves $\lambda$ by little, and flat enough on the right that a level a few per cent high costs a few per cent. “Never low” was the right demand of the estimates the earlier essays had, which were either never low or wildly low. It is not a property the rule needs; what it needs is an estimate that is not far off, and the corrected leave-one-out estimate is never more than 35 per cent below the noise or, at its median, more than 7 per cent above.

Why the folds were blamed #

The four-fold essay’s explanation was reasonable from what it could see. It measured one fold count, so it could not separate what changes with the folds from what does not, and the training fraction was the obvious thing a fold count changes. An estimate that shares nothing with the fit, the essay before it, held out a single quarter and fitted the other three, and its estimate’s trouble was scatter — too few held-out samples to average — which more folds did cure. The two defects looked alike from one fold count each, and only one of them belonged to the folds. Its other observation — the bias largest at low noise and few samples per unknown — was true and is explained better here: those are exactly the corners where the fit spends most of its samples on degrees of freedom. A share of 54 per cent at 1.25 samples per unknown and noise $10^{-4}$ puts the excess at $\sqrt{1/0.46} = 1.47$, and the measured median there is 1.52.

More samples take the floor and leave the dip found that oversampling does something similar to generalised cross-validation’s objective: it changes what the floor of the curve is, and it leaves the defect that was the reason for looking. Here more samples per unknown shrink the excess by shrinking the share the fit spends — 54 per cent at 1.25 per unknown, 17 at four — and no number of folds does.

What this changes, and what it does not #

For the discrepancy principle the practical answer is now simple. Estimate the noise by leave-one-out, which for Tikhonov costs one decomposition and is as good as any fold count; multiply the estimate’s square by $1 - \operatorname{df}/m$ at the $\lambda$ where it was read; and hand the result to the rule. On these 960 draws that is indistinguishable from being told the noise.

For the guard on generalised cross-validation it changes nothing, and it is worth saying why. The four-fold essay found the guard needs a noise estimate that does not share the residual’s luck, and that no estimate made from the same samples qualifies. Correcting the bias leaves the sharing exactly where it was: the corrected estimate is made from the same residuals, at the same $\lambda$, with the same draw’s luck in it. A unit is a statement about the noise reached the same conclusion for total least squares: what the data alone can supply about their own noise is limited by the fact that they are the data.

The rule that needs no noise level at all is still in the comparison. The minimum on the right proposed taking generalised cross-validation’s rightmost local minimum, and the earlier essay found it right to the grid on the typical draw — a median of 1.004 or 1.005 over the oracle — and wrong by 2.57 to 3.70 on the worst. The discrepancy principle told the corrected estimate has its median a few per cent above the oracle and its worst at 1.16. The choice between them is the one the earlier essay described, a few per cent on every draw against a factor of three on some, and the corrected estimate moves the second rule’s worst draw down to the true noise’s without changing that trade.

What 960 draws do not show #

One family of problems: a blurred signal, Tikhonov’s filter, a grid of 121 values of $\lambda$. The hat-matrix identity holds for any linear smoother, and the degrees-of-freedom argument for any fit whose prediction variance is set by its trace, but a truncated decomposition spends its degrees of freedom in whole units and might read differently at the boundary. White Gaussian noise of one level per draw; with noise whose level varies across samples, leave-one-out weights each sample’s error by its own leverage and the correction by an average share might over-correct some samples and under-correct others. And the misfit draws, where the discretised problem cannot represent the signal to the noise’s accuracy, are present at the coarsest grid only, so how a corrected estimate behaves when model error is the larger part everywhere is not measured.

Still open: a corrected estimate for the guard, and noise from outside the sample #

Noise from outside the sample. The earlier essay’s second prediction still stands untested: a guard told an estimate from four replicate readings of each sample — independent of the fitted data by construction — refuses more dips than real minima at the 1% threshold, the first configuration in these essays to do so. This essay adds a sign to its other half: the discrepancy principle told that replicate estimate does no better than told the corrected leave-one-out estimate, whose worst draw is already within 0.01 of the true noise’s at every ratio.

Where the correction over-corrects. The corrected estimate’s lowest draws, at 0.65 to 0.75 of the noise, are all at 1.25 to 2 samples per unknown, where the fit spends the largest share. The prediction is that they are the draws whose chosen $\lambda$ sits furthest left of the oracle’s — where $\operatorname{df}$ is read too high — and that reading $\operatorname{df}$ at the discrepancy principle’s own $\lambda$ instead, iterating once, lifts every one of them above 0.85 without moving the median by more than two per cent.