The rule that divides by one minus the leverage

The degree that is safe to overshoot transplanted the rules that choose a Tikhonov parameter to a simpler choice, the degree of a polynomial fit, and found them forgiven. In a basis orthonormal on the data — so that every degree’s fit comes from one set of columns and every rule can be evaluated exactly — generalised cross-validation, leave-one-out, the Bayesian information criterion and the discrepancy principle never cost more than 2.7 times the best degree’s error in three hundred draws. The reason was the shape of the valley they search: six degrees too few cost from 44 to 16,000 times the best error, forty too many about twice. A rule only had to avoid the cliff.

The function was smooth, entire but for a pole far from the interval, and its coefficients fell geometrically. The essay ended on functions that are not, with a prediction. “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.”

Each clause holds somewhere. The rule the prediction accused is costliest on one of the two functions and not the other; and the rule that fails badly is one the prediction did not mention.

Three functions, three decays #

The measurement repeats the earlier one with two new functions, in the basis a basis built from the points constructed so that the degree could be chosen without the basis’s conditioning getting in the way: 200 equispaced points on $[-1, 1]$, a basis orthonormal on them built by Arnoldi’s process — now to degree 120, twice the earlier cap, because one of the new functions wants it — noise of standard deviation $10^{-2}$, $10^{-4}$ and $10^{-6}$, a hundred seeded draws of each, and the same four rules scored against the degree an oracle that knows the true function would choose.

The prediction treated $|x|$ and a near pole as one case, “whose coefficients fall algebraically”. They are two. The coefficients of $|x|$ fall like the inverse square of the degree — $0.4$ at degree 6, $10^{-2}$ at 40, $10^{-3}$ at 120 — which is algebraic, and slow enough that at noise $10^{-4}$ every coefficient the basis has is still above the noise. The coefficients of $1/(1.05 - x)$ fall geometrically, by a factor of about 1.37 a degree, which is the radius of the largest ellipse with foci at $\pm 1$ that avoids the pole: $10^{-1}$ at degree 20, $10^{-4}$ at 40, $10^{-8}$ at 60, rounding by 120. A pole near the interval slows the geometric decay; it does not change its kind. The smooth function’s coefficients reach rounding by degree 30.

The left wall flattens, the best degree climbs #

The dial puts the three valleys side by side, and the first clause of the prediction is the most visible thing in them. Six degrees too few costs the smooth function 200, 1,800 and 15,000 times its best error at the three noise levels; it costs $|x|$ 6, 11 and 12 per cent; it costs the pole 72 to 86 per cent. On $|x|$ the valley has no left wall worth the name, because a coefficient that falls like $k^{-2}$ is barely smaller at degree $d - 6$ than at $d$, and dropping six of them removes almost nothing the fit had.

And the best degree climbs, as predicted. The smooth function’s best degree is 9, 11 and 13 at the three noise levels. The pole’s is 27, 40 and 52 — each two decades of noise buys twelve or thirteen degrees, near the fifteen that two decades divided by the logarithm of 1.37 would give. On $|x|$ at one per cent noise the best degree has a median of 34 and ranges from 24 to 46 over the draws; at $10^{-4}$ and $10^{-6}$ it is 120 on every draw, the largest the basis has. The earlier cap of sixty would have been the answer on those, and a doubled cap moved it to the new wall: $|x|$ sampled at 200 points and measured at $10^{-4}$ wants every degree it can have, which in the limit is interpolation.

Which rule pays #

The prediction’s liability is real on $|x|$ at one per cent noise. The information criterion chooses a median degree of 20 where the best is 34 and pays a median of 1.21 times the best error, the worst of the four rules there; generalised cross-validation chooses 32 and pays 1.07. The criterion’s penalty of $\log m$ per coefficient is a threshold of about 2.3 standard deviations on each coefficient’s size, and on a function whose coefficients near the best degree are about one standard deviation each, the threshold drops coefficients that together are worth keeping.

On the pole it does not happen. There the criterion pays 1.07, 1.04 and 1.03 at the three noise levels, and the costliest rule is the discrepancy principle at 1.25 — the rule that stops at the first degree whose residual is at the noise level, which is early when the coefficients beyond it are falling slowly but steadily and each one is just under the noise. The two functions the prediction lumped together punish opposite rules: the algebraic one punishes the rule with the highest threshold, the slow geometric one the rule that stops first.

Both liabilities are mild. Nothing on the pole costs more than 2.1 times the best error on any draw; on $|x|$ at one per cent nothing costs more than 1.61. The flattened wall that makes the best degree hard to find also makes a wrong degree cheap.

The rule that divides by one minus the leverage #

The one large cost in the figure is not the criterion’s. At noise $10^{-4}$ and $10^{-6}$ on $|x|$, leave-one-out cross-validation chooses degree 26 on every draw, where the best is 120, and costs 12.4 and 12.9 times the best error. Every other rule chooses 120 and pays nothing.

Leave-one-out scores a degree by the prediction sum of squares, which in closed form divides each residual by one minus its point’s leverage — the diagonal entry of the projection onto the columns kept, which for an orthonormal basis is the sum of the point’s squared entries over those columns. One minus a leverage is a subtraction measured what that division does when a leverage is near one: the subtraction loses digits, and the score is dominated by the point that is almost alone in determining its own fit. On 200 equispaced points a polynomial basis concentrates on the ends, and the largest leverage rises fast: 0.45 at degree 10, 0.89 at 20, 0.974 at 26, 0.99979 at 40, and within $10^{-8}$ of one by 60. A residual divided by one minus its leverage is exactly the error with which the fit to the other 199 points predicts the one left out, and at an end point that prediction is an extrapolation. The division makes the score grow with the noise amplified by extrapolation, which on equispaced points grows quickly with the degree; what makes the score fall is the approximation error the extra degree removes.

That is why the pole survives what $|x|$ does not. On the pole the best degrees, 27 to 52, are all past the point where the end leverages approach one, and leave-one-out still tracks them to within a degree or two at the median — 28, 40 and 51 — because each degree there removes a fixed fraction of the remaining error, and a geometric fall can outrun the growing amplification until the noise is reached. On $|x|$ each degree removes almost nothing; past degree 26 the amplified noise at the ends grows faster than the slowly falling approximation error shrinks, the score turns upward, and leave-one-out stops — where the error averaged over all 200 points, which is what the oracle and the other rules see, would go on falling for another ninety degrees.

The earlier essay’s last question was about “clustered points” whose leverages range widely, and predicted that leave-one-out and generalised cross-validation would measure different things there. Equispaced points turn out to be such a sample once the degree is high: their leverages range from a few per cent in the middle to almost one at the ends. Generalised cross-validation replaces each point’s leverage by the average, which is the degree over the number of points — 0.6 at degree 120 — and is never close to one; it chooses 120 and is right.

Two places on one interval #

The failure has a geography, and it is worth saying where on $[-1, 1]$ each quantity lives. The error a further degree removes from a fit to $|x|$ is concentrated near the kink at the origin: away from it the function is a straight line, which a low degree already fits, and the slowly falling coefficients are the polynomial’s struggle to turn a corner. The noise that leave-one-out’s score accumulates as the degree rises is concentrated at the two ends, where a high-degree polynomial on equispaced points is free to swing. The oracle, and the rules that average over all 200 points, weigh the corner’s improvement against the ends’ noise across the whole grid and find the corner worth it. Leave-one-out weighs them point by point and finds two points where the noise wins outright.

On the pole the two places are one: the pole at 1.05 sits just past the right end, so the error the degree removes is concentrated there too, at the same points where the noise is amplified, and the two effects are traded at the same location by every rule. That is a second reason the pole’s leave-one-out tracks the best degree and $|x|$'s does not — the difficulty of the function and the weakness of the grid happen to coincide. The residual the solution cannot hold found the same kind of coincidence deciding whether a deleted observation’s residual could be trusted: it depends on whether the point is unusual in the same way the fit is.

Two rules that read the same residuals #

Generalised cross-validation and leave-one-out are usually presented as one idea with two implementations: leave each point out, refit, and add up how badly the refit predicts it, either exactly or with every leverage replaced by the average. On the smooth function and on the pole the two choose the same degree to within two at the median at every noise level, and their costs differ in the second decimal. On $|x|$ at small noise they differ by ninety-four degrees and a factor of twelve in error. The averaging that turns the second rule into the first is not a convenience there; it is a different question. Leave-one-out asks how well the fit predicts each point from the others, ends included. Generalised cross-validation asks, in effect, how well it predicts a typical point, and a typical point on an equispaced grid is not at an end.

Which question is right depends on what the fit is for. A fit that will be evaluated at the ends — extrapolated, or used for a boundary value — should be chosen by the rule that pays for the ends, and leave-one-out’s degree 26 is the honest answer to that question: past it, the fit’s value at $x = \pm 1$ is determined by the noise in the samples there. A fit that will be evaluated throughout the interval should be chosen by the average. The excess is what the fit spent found a related split for noise-level estimates, where leave-one-out’s inflation was exactly the degrees of freedom the fit used; here the inflation is concentrated at two points and the average dilutes it a hundredfold.

Two observations that hide each other measured the case where the leverage of a pair, not a point, is the quantity a deletion diagnostic needs; the end points of a high-degree equispaced fit are the single-point version, and the masking there is complete — each end point is predicted only by itself.

What the prediction was about #

The prediction’s mechanism was a threshold on coefficients: a rule that drops coefficients below 2.3 standard deviations drops signal when the signal’s coefficients are small but many. That is true on $|x|$ at one per cent noise, and it costs a fifth. The larger failure is a rule’s arithmetic meeting the basis’s geometry: leave-one-out is computed by a formula that assumes no point determines its own fit, and a high-degree polynomial on equispaced points is the standard example of a fit in which the end points do. The valley with no bottom found the error valley of an equispaced monomial fit had no minimum because the basis’s conditioning swamped it; with the basis fixed, the same equispaced points come back through the leverage, and through one rule only.

Influence is decided before the data made the general point that leverage is a property of the design and not of the measurements; here it decides, before any data is drawn, the degree above which one of four rules can no longer be trusted. A code that chooses a degree by leave-one-out should compute the largest leverage at each candidate degree, which costs nothing in this basis, and stop trusting the score where it passes 0.95. That does not make the score right past that point — it says only that the score has stopped measuring the fit’s quality in the interior — and the honest response is to switch to the averaged rule there, or to say that the degree is being chosen for the ends.

What three functions do not show #

The functions are one of each kind, and the noise levels are three; the claims about which rule pays are about these. The cap of 120 on 200 points is where $|x|$‘s best degree sits at small noise, so the right wall of its valley is never seen, and its best degree is a lower bound. Points clustered towards the ends, as Chebyshev points are, would keep the leverages from one at much higher degrees — the property that makes them good interpolation points — and leave-one-out would then follow the best degree further; that is the obvious next measurement and is not made here. And the rules are scored against an oracle that knows the function; on real data the valley’s flatness means the four rules’ choices on $|x|$ differ by up to a dozen degrees with little difference in error, which is reassuring for the fit and useless for any reading of the degree itself.

Still open: Chebyshev points, and a leverage-aware leave-one-out #

Points that keep the leverage down. On Chebyshev points the largest leverage of a degree-$d$ fit stays near $2d/m$ rather than approaching one. The prediction with a sign is that on 200 Chebyshev points leave-one-out follows the best degree on $|x|$ to within five degrees at every noise level, that its cost there falls to within 1.1 of the best, and that the information criterion’s liability at one per cent noise is unchanged — so that the leave-one-out failure is the points’, and the criterion’s is the function’s.

Leave-one-out without the subtraction. The prediction sum of squares can be computed without forming $1 - h_i$, from the null-space columns the fit discards. The prediction is that on equispaced points this changes leave-one-out’s choice on $|x|$ by no more than a degree, because the failure is not rounding in the subtraction but the score’s genuine growth as end points come to determine their own fit — which would make the leverage threshold, not a better formula, the repair.