The degree that is safe to overshoot

A basis built from the points settled what a polynomial basis does to a fit: in monomials the fitted curve moves by the condition number times the rounding times the residual, and in the basis Arnoldi builds from the sample it does not move at all. It ended at the question that basis makes answerable. Every separation it measured was at a fixed degree, and choosing the degree is the regularisation question for polynomial fits — too low loses the function, too high fits the noise. Whether cross-validation and the discrepancy principle choose a degree as well as they choose a Tikhonov parameter, on a basis whose conditioning no longer interferes, was left as the place where fitting meets regularisation.

The regularisation field’s answer for the Tikhonov parameter is not reassuring. One draw in twenty found generalised cross-validation choosing a second, wrong answer on four to six draws in every hundred, between ten and seven million times worse than the best parameter, and more samples take the floor and leave the dip found the interior dip that causes it surviving four samples per unknown. If the same rules behave the same way on a degree, a polynomial fit chosen automatically is a fit that is badly wrong one time in twenty.

The rules, on one basis #

The data are the smooth function the earlier essay fitted — $e^x\sin 4x + 1/(x + 2.5)$, analytic around $[-1, 1]$ — at 200 equispaced points, with Gaussian noise of standard deviation $\sigma$ at three levels, a tenth, $10^{-3}$ and $10^{-6}$, and a hundred seeded draws at each. The basis is the one Arnoldi builds: columns orthonormal on the 200 points, so the fit of degree $d$ is the sum of the first $d + 1$ coefficients $q_k^{\mathsf T} y$, its residual is what the dropped coefficients leave, and every point’s leverage is the running sum of its squared entries in the columns kept. One pass gives every degree’s fit, residual and leverages from 0 to 60, with no condition number anywhere above one.

Four rules then choose a degree. Generalised cross-validation minimises the residual over the square of the degrees of freedom left. Leave-one-out cross-validation minimises the sum of each residual divided by one minus its point’s leverage — the prediction error of the fit with that point removed, in closed form, which is the residual the solution cannot hold’s identity put to work. The Bayesian information criterion minimises the log of the residual plus a penalty of $\log m$ per coefficient. The discrepancy principle takes the first degree whose residual norm is at most $\tau\sigma\sqrt m$, with $\tau = 1$ unless stated. The oracle knows the true function and takes the degree whose fit is closest to it.

Every rule is forgiven #

In three hundred draws no rule ever costs five times the best degree’s error. The largest ratio of any rule on any draw is 2.69. Generalised cross-validation’s medians are 1.03, 1.03 and 1.01 at the three noise levels and its worst draws 2.37, 1.91 and 1.49; leave-one-out is within a few per cent of it; the information criterion is tighter than both, with medians of 1.00 to 1.01 and a worst draw of 1.40. The discrepancy principle has the heaviest spread — its median at $10^{-3}$ is 1.43 and its worst draws reach 2.69 — and it too stays inside a factor of three.

The contrast with the Tikhonov parameter is the finding, because the rules are the same rules. Generalised cross-validation is not a better rule here than it was there. It is choosing on a different landscape.

The valley is lopsided #

Averaged over draws and measured from the best degree, the error curve has two very different walls. On the left, too few degrees: one too few costs 2.7, 1.3 and 4.9 times the best error at the three noise levels, and six too few costs 44, 525 and 16,419 times. On the right, too many: ten too many costs 1.6, 1.5 and 1.3 times, and forty too many 2.7, 2.3 and 2.0.

Both walls have simple causes. Past the best degree every extra coefficient is fitting noise, and in an orthonormal basis each one adds $\sigma^2/m$ to the mean-square error, so the error grows like $\sigma\sqrt{(d+1)/m}$ — the square root of the number of coefficients. Forty extra coefficients on top of ten multiply the variance by five and the error by the square root of five, which is the 2.2 the curves level toward. Below the best degree every missing coefficient is signal, and for an analytic function the coefficients fall geometrically, so each degree removed multiplies the error by the ratio at which they fall. The lower the noise, the further down that geometric slope the best degree sits, and the steeper the left wall is where the rules have to stop.

A single draw shows the same shape at the scale a rule sees it. At noise $10^{-3}$ the error falls steeply to the best degree, ten, and then runs up the noise line so slowly that degree forty is barely distinguishable from degree fifteen on a logarithmic axis. Turn the dial and the best degree moves — seven or eight at a tenth, thirteen at $10^{-6}$ — but the shape does not. A rule that stops late loses a factor of two at worst; a rule that stops early loses as much as the geometric slope makes it. All four rules err late far more readily than early, and that is why none of them is ever expensive.

The Tikhonov landscape is the opposite. Undersmoothing an ill-posed problem does not add noise at the rate of a square root; it divides noise by singular values that fall to the rounding level, and a parameter too small by a decade can let in errors of any size. The rules that make the same kind of mistake on both problems pay on one and not on the other.

The iterative form of regularisation makes the contrast sharper still, because its parameter is an integer like the degree. A parameter that counts steps chose where to stop conjugate gradients on a blurred problem, and the semi-convergence curves there are lopsided the other way: each step past the best one brings in a component of the data divided by a smaller singular value, so stopping late is the expensive mistake and stopping early the cheap one. Two integer knobs, one count of steps and one count of coefficients, sit in valleys that are mirror images of each other. A rule’s habits — erring late, erring early — are only good or bad relative to which wall it is standing next to.

Where each rule lands #

At noise of a tenth, all four rules land most often on the best degree or within two of it, and every one of them falls short of it on a third to a half of the draws — 40 draws below for cross-validation of both kinds, 50 for the information criterion, 36 for the discrepancy principle — but never far short, because the left wall is steep enough that the residual itself says the degree is too low. What separates them is the right tail. The information criterion never lands more than two degrees past the best. Generalised cross-validation lands more than five past on 8 draws and at most 13 past; leave-one-out on 13 draws and at most 17 past. The discrepancy principle lands more than five past on 24 draws, and once 38 past.

In an orthonormal basis each of the minimising rules is, in effect, a threshold on the coefficients. Adding coefficient $k$ changes the residual’s square by $c_k^2$, so a rule that penalises each coefficient by a fixed amount includes it when $|c_k|$ exceeds a multiple of $\sigma$. The information criterion’s penalty of $\log 200$ puts that multiple near 2.3, and a pure-noise coefficient passes it about two times in a hundred. Generalised cross-validation’s penalty is close to the classical two per coefficient, a multiple near 1.4, and pure noise passes it about one time in six — so runs of noise coefficients that happen to be large carry it a few degrees past the best, occasionally a dozen. The measured tails are in that order.

Leave-one-out is the one rule that sees the points individually, and on equispaced points it sees the ends. At degree 10 the leverage of an end point is 0.455 against 0.037 in the middle, twelve times larger, because a polynomial is pinned hardest where it has the fewest neighbours; dividing an end residual by one minus 0.455 nearly doubles it. At degree 40 the end leverage is 0.9998 and the division multiplies the end residual by five thousand, which is why leave-one-out, alone of the four, has a built-in wall against high degrees on this sample — and why its tail, though longer than generalised cross-validation’s at noise of a tenth, never runs past seventeen. The two cross-validations agree in the middle of the interval and disagree about its ends, and on data whose ends matter less than their middle they would disagree about which degree to trust.

The discrepancy principle’s threshold #

The discrepancy principle is not a threshold on coefficients; it is a threshold on the residual’s total, and its tail comes from where the threshold sits. At the best degree the residual is almost entirely noise, and its square divided by $\sigma^2 m$ has an expected value of one minus the fraction of coefficients kept, about $0.95$, and a spread of about $\sqrt{2/m}$, a tenth. Measured, its median over the draws is 0.948, 0.933 and 0.917 at the three noise levels. The threshold at $\tau = 1$ is one — half a spread above the value the residual is centred on. On 33, 28 and 24 draws of the hundred the residual at the best degree is above it, the rule does not stop, and it walks on through degrees whose coefficients are noise, each lowering the residual by a random amount, until one of them happens to bring it under. That walk is the tail.

The worst draw at noise of a tenth shows it step by step. Its best degree is 6, and at degree 6 its residual’s square is 1.251 times $\sigma^2 m$ — this draw’s noise happens to be a quarter above its expected size, two and a half spreads. From there every further coefficient is noise and lowers the residual by a little: 1.232 at degree 7, 1.207 at 10, 1.159 at 20, 1.082 at 30, 1.021 at 40. It crosses one at degree 44, thirty-eight past the best, where the fit costs 2.42 times the best error. No single step was a mistake; the rule was waiting for a total the noise could not reach without being fitted.

The standard remedy is a safety factor above one, and the measurement says how much. At $\tau = 1.1$ the threshold’s square is 1.21, two spreads above the residual’s centre; one draw in three hundred had its best-degree residual above that, and no draw at any noise level lands more than five degrees past the best. The worst draw at noise of a tenth falls from 2.69 to 1.19, and at $10^{-6}$ from 1.93 to 1.03. But the cost moves to the other wall. At $10^{-3}$ the median rises from 1.43 to 1.56 and the worst draw from 2.27 to 3.21, because a larger threshold stops earlier and this function’s coefficients fall in steps, so stopping one degree early can mean stopping before a large one. At $\tau = 1.5$, which the Tikhonov literature often uses, every draw at noise of a tenth underfits and the median costs 4.1 times the best error.

So the discrepancy principle has a correct setting, it is narrow — somewhere between 1.05 and 1.1 at 200 points — and it depends on the number of points through the spread $\sqrt{2/m}$, which shrinks as the sample grows. The rules that minimise a score have no such setting to get wrong.

The basis that was built for this #

The earlier essay built the orthonormal basis to protect the fitted curve from the condition number, and it is natural to expect that it also protects the choice. It barely needs to. Refitting each draw at the degree the discrepancy principle chose, in monomials by Householder least squares, gives the same error on 99 of the 100 draws at noise of a tenth — the exception a draw that ran to degree 45, where the monomial fit costs 2.35 times the best error against the orthonormal fit’s 2.13 — and on every draw at the two smaller noise levels. The monomial curve moves by the condition number times the rounding times the residual, which a small residual is not a small error would call the second-order term, and the rules almost never walk far enough into the ill-conditioned degrees for that term to reach the noise. What the orthonormal basis buys here is speed and the leverages: one pass gives every degree, and leave-one-out’s closed form needs the leverages that only an orthonormal basis hands over for free.

What a fit that chooses its own degree should do #

Three things follow, in order of how much they buy.

Prefer a rule that minimises a score over one that waits for a total. On this landscape the minimisers are a coefficient threshold in disguise and cannot run away; the discrepancy principle can, by forty degrees, and its remedy is a safety factor whose right value depends on the sample size and on how the coefficients fall. Of the minimisers, the information criterion’s higher threshold made it the tightest here, at the price of the most early stops — a trade that is cheap only because this function’s left wall is where it is.

Compute the rules in a basis that hands them the leverages. The orthonormal basis costs one Arnoldi pass and makes every degree’s fit, residual and leverages available at once, so trying all sixty degrees costs no more than fitting one. The route the textbooks start from — forming the normal equations in monomials for each degree, which the road that squares the problem shows is solving a Hilbert system — would have to factor afresh, sixty times over, a matrix of condition number past $10^{16}$ to produce the same scores, and at the high degrees would produce them wrong.

And do not carry the Tikhonov literature’s caution over without its reason. The warnings about generalised cross-validation are true of ill-posed problems, where the variance side of the valley is a cliff. For a well-posed fit with many more points than coefficients the variance side is a gentle slope, and the same rule that fails one draw in twenty there is safe on every draw here. What decides whether a rule can be trusted is the shape of the error curve it is searching, and that is a property of the problem — something to measure, as this essay did, before choosing a rule by reputation.

The same reasoning extends to the fits the earlier essay pointed beyond. The points the algorithm chose builds rational approximants by adding poles one at a time, and the number of poles is a degree with its own valley; whether that valley is lopsided the same way, with an extra pole cheap and a missing one expensive, is the natural next measurement of the same kind.

What the valley depends on #

One function, one sample, one noise model. The left wall’s steepness is the geometric decay of an analytic function’s coefficients; for a function with a nearby singularity or a kink, the coefficients fall slowly, the left wall is gentle, and stopping early costs less — the rules would then be judged on both walls rather than one. The right wall’s gentleness is $\sqrt{(d+1)/m}$ with $m = 200$ fixed; with twenty points and the same degrees the variance grows in proportion rather than as a small correction, and fitting forty coefficients to twenty points is not an option at all. Gaussian noise of known level is assumed by the discrepancy principle and not by the others. And the valley with no bottom is the reminder that the coefficients themselves are not what these rules protect: the curve is, and the curve is what the error measures.

Still open: a slowly converging function, and the degree under the leverage #

A function with a kink. The prediction with a sign is that on $|x|$ or on a function with a pole near the interval, whose coefficients fall algebraically, the left wall flattens, the best degree rises towards the right wall, and the rules’ costs rise with it — the information criterion’s tight threshold turning from an advantage to a liability, because a coefficient of the signal that falls below 2.3 standard deviations is signal it throws away.

Clustered points. The earlier essay’s clustered and gapped samples make some points far more influential than others. Leave-one-out divides each residual by one minus its leverage and generalised cross-validation by the average of that quantity; on a sample whose leverages range widely the two rules measure different things, and which one then lands nearer the best degree is a measurement the equispaced sample here cannot make.

Fewer points than the problem wants. At $m = 20$ the right wall is no longer gentle. The degree at which the valley stops being lopsided — where adding a coefficient costs as much as dropping one — is the sample size at which choosing a degree becomes as hazardous as choosing a Tikhonov parameter, and it is the number that would say when this essay’s reassurance applies.