Chebyshev points make the two rules one

The rule that divides by one minus the leverage chose the degree of a polynomial fit four ways and found one of them failing badly on one function. On 200 equispaced points, at noise $10^{-4}$ and $10^{-6}$, leave-one-out cross-validation chose degree 26 on every draw of a fit to $|x|$ where the best degree was 120, and paid twelve to thirteen times the best error, while every other rule chose 120 and paid nothing. The cause was the points. Leave-one-out divides each residual by one minus its point’s leverage, a polynomial basis on equispaced points concentrates on the two ends, and the largest leverage there was 0.974 by degree 26 and within $10^{-8}$ of one by 60.

Its closing section named the obvious repair and made it a prediction with a sign: “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.”

Most of it holds. What it misses is the more interesting half: on Chebyshev points leave-one-out does not merely recover, it turns into the rule it was being compared with.

Twice the average, until the top #

Every piece of the earlier study is kept — the three functions, the noise levels $10^{-2}$, $10^{-4}$ and $10^{-6}$, a hundred draws each, the four rules, and a basis built by Arnoldi’s recurrence to be orthonormal on the points themselves, the construction a basis built from the points introduced to take conditioning out of the question. Only the 200 abscissae change: from equally spaced on $[-1, 1]$ to the Chebyshev points of the first kind, $-\cos(\pi(i + \tfrac12)/200)$, which bunch towards the ends with a density proportional to $1/\sqrt{1 - x^2}$.

The leverage of a point is the sum of its squared entries over the basis columns kept, and the leverages of all 200 points add up to the number of columns, $d + 1$. So the average leverage is $(d+1)/m$ whatever the points are, and the question is only how unevenly it is shared.

On Chebyshev points the largest leverage is 0.10 at degree 10, 0.20 at 20 and 0.26 at 26, where on equispaced points it is 0.45, 0.89 and 0.974. Up to degree 45 it is within five per cent of $(2d + 1)/m$, which is the prediction’s $2d/m$ with the constant term counted. The Chebyshev polynomials are themselves orthogonal on these points, and normalised there every one but the constant has a squared value of about $2/m$ at an end point, where it is close to $\pm 1$, while the constant has $1/m$ everywhere — so an end point’s leverage is one share for the constant and two for every other degree. Above 45 it falls away below that line, since a leverage cannot pass one, and approaches one only near the top: 0.56 at 60, 0.90 at 120, 0.974 — the equispaced value at 26 — at degree 149, and 0.9985 at 180.

That is the wall moved from 26 to about 150. Inside it, no point’s residual is divided by much less than a half until degree 100, and the score leave-one-out computes is the score of a fit whose points all share its determination.

The prediction’s three numbers #

At noise $10^{-4}$ and $10^{-6}$, leave-one-out on Chebyshev points chooses degree 120 on the median draw, where the best degree is also 120, and its median cost is 1.00 — against 12.4 and 12.9 on equispaced points. The worst draw at $10^{-4}$ costs 1.04. That part of the prediction holds as stated, and the earlier essay’s diagnosis with it: the failure was the points.

At one per cent noise the best degree on Chebyshev points is a median 30, leave-one-out chooses 28, and its median cost is 1.06; the 95th percentile is 1.21. Within ten per cent, as predicted. But the median gap between its degree and the best is six, not five or less, and the worst draw is thirty-two degrees off. That is not leave-one-out’s failing: generalised cross-validation’s median gap is also six and its worst also thirty-two, the information criterion’s are ten and twenty-two, the discrepancy principle’s eight and twenty. On $|x|$ at one per cent the error valley is so flat that the degree is not well determined by anything, and a rule six degrees off pays six per cent. The prediction’s five degrees was a number about the valley, not the rule, and the valley would not give it.

The third number holds exactly as the prediction framed it. The information criterion costs 1.21 on equispaced points and 1.19 on Chebyshev points at one per cent, the worst of the four rules on both, choosing degree 20 on both. Its threshold of about 2.3 standard deviations drops coefficients of $|x|$ that together are worth keeping, and moving the points does not change the coefficients’ size relative to the noise. The leave-one-out failure was the points’; the criterion’s is the function’s.

Two rules that become one #

The earlier essay ended its comparison of the two cross-validations with a distinction: leave-one-out asks how well the fit predicts each point from the others, ends included, and generalised cross-validation asks how well it predicts a typical point. On equispaced points those questions had different answers. On Chebyshev points they do not.

On Chebyshev points the two choose the same degree on 86 to 100 draws in a hundred, for every function at every noise level: 91, 98 and 100 on $|x|$, 90, 96 and 86 on the pole, 97, 98 and 96 on the smooth function. On equispaced points they agree on none of the draws on $|x|$ at small noise, on about a third of them on the pole, and on two thirds to four fifths on the smooth function, where the best degree is low enough that the leverages are still nearly even.

The algebra says why. Generalised cross-validation is leave-one-out with every leverage replaced by the average, $(d+1)/m$: the two scores are $\sum_i r_i^2/(1 - h_i)^2$ and $\sum_i r_i^2/(1 - \bar h)^2$. They differ only through the spread of the leverages, and on Chebyshev points that spread is at most a factor of two between the middle and the ends, up to degree 45 — and more to the point, the leverage is large exactly where the points are dense, so a point’s share in determining the fit is matched by its neighbours’. The residuals near the ends are not the ones being amplified most, as they were on the equispaced grid; they are amplified by a factor that every residual near them shares. Two rules that disagree only through a spread of leverages make the same choice when the spread is mild.

One minus a leverage is a subtraction measured the other face of the same quantity, the digits lost in forming $1 - h_i$ when $h_i$ is near one. On Chebyshev points at the degrees measured here there is nothing to lose: the smallest value of one minus a leverage at degree 120 is 0.096.

What the stop at 26 was worth to the ends #

The earlier essay offered a defence of leave-one-out’s equispaced stop. Past degree 26, it said, the fit’s value at $\pm 1$ is determined by the noise in the samples there, so “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.” That is a claim with a number in it, and the number can be checked: for each draw, find the degree that minimises the larger of the two end-point errors, and price each rule’s degree against it.

On equispaced points at noise $10^{-6}$, the degree best for the ends is a median 56 — not 26. Leave-one-out’s degree gives the end points a median error 1,242 times the least they could have. Every other rule’s degree, 120, gives them 1.6 times the least. At $10^{-4}$ the best for the ends is 40, leave-one-out’s degree costs them 14 times the least, and the other rules’ 1.7 times. Only at one per cent, where every rule chooses a degree in the twenties or low thirties, does leave-one-out cost the ends about what the others do, 2.3 times.

So the defence fails. The rising score was not tracking the end values; it was tracking the end points’ residuals divided by numbers going to zero. A fit at degree 26 is still far too smooth to follow $|x|$ near its kink, but on $[-1, 1]$ the ends are nowhere near the kink, and there the fit’s error at degree 26 is the polynomial’s failure to be straight. Each degree removes part of that until the noise at the ends takes over at about 56. Leave-one-out’s score turned at 26 because $1/(1-h)$ grew faster than the end residuals fell — an arithmetic fact about the formula, as the earlier essay showed, and not a judgement about the ends. On Chebyshev points the ends’ best degree is 97 at $10^{-4}$ and 120 at $10^{-6}$, every rule’s choice costs the ends 2.8 and 1.0 times the least, and the four rules agree there as they agree everywhere.

Where the protection runs out #

The comparison is made with degrees up to 120, the earlier cap. To find where Chebyshev points stop protecting the score, the same fits were run to degree 190 of a possible 199, where the largest leverage on Chebyshev points is 0.9998.

On Chebyshev points the score follows the error the whole way, a little above it, and turns up only at the last few degrees: at $10^{-6}$ the best degree is 190, leave-one-out chooses a median 188 and costs 1.35 times the best error, the worst draw 1.73. At $10^{-4}$ the best is 178 and leave-one-out chooses 166 at a cost of 1.04. Turn the dial to equispaced points and the picture is the earlier essay’s, drawn further: the score turns upward at 26, is eleven times the error at degree 40, two thousand times at 60 and fourteen thousand at 65, where one minus the largest leverage has fallen below $10^{-8}$, is not even a finite number on the median draw by degree 120, and the error goes on falling for 160 degrees past the stop. At degree 190 leave-one-out’s choice costs 117 times the best error at $10^{-6}$, and even generalised cross-validation, which never divides by a single leverage, stops at a median 164 and pays 3.4 times. At that height the average leverage is 0.95 and the averaged rule’s denominator is small as well.

What the points were for #

Chebyshev points are usually introduced for interpolation, where they keep the Lebesgue constant of a degree-$n$ interpolant growing like $\log n$ instead of exponentially and so tame the Runge phenomenon; the valley with no bottom met equispaced points from the other side, through the conditioning of the monomial basis. This measurement is a least-squares fit with more points than coefficients, and the property that matters is a different face of the same distribution: their density matches the weight under which polynomials of high degree are best behaved, so no point has to determine its own fit until the degree is close to the number of points. The leverage is how a least-squares fit sees a Lebesgue constant, and the two are the same story about where a polynomial is free to swing.

Influence is decided before the data made the general point that leverage is fixed by the design before any measurement. Here the design decides something more specific: whether two rules that read the same residuals reach the same answer. Which suggests the practical advice is not “use leave-one-out on good points and generalised cross-validation on bad ones”, but that on good points the choice does not matter and on bad points the averaged rule is the one that does not divide by almost nothing. Two observations that hide each other found the same lesson for deletion diagnostics, where a pair of high-leverage points masks itself from any test that removes one at a time: a score built on one point’s leverage is only as good as that point’s share of the fit is small.

The other two rules keep their own characters on the new points, which is the control the comparison needs. The discrepancy principle — stop at the first degree whose residual is down to the noise — still costs a median 1.26 on the pole at one per cent on Chebyshev points, as it did on equispaced ones, because it stops early whenever each further coefficient is just under the noise; and it still costs nothing much on the smooth function, 1.04. The information criterion still loses most on $|x|$. Neither rule ever divides by a leverage, and neither changed. Only the rule whose arithmetic reads one point’s share of the fit changed, and it changed into its averaged twin. The excess is what the fit spent found leave-one-out’s inflation of a noise estimate to be the degrees of freedom the fit used, spread over the points; on Chebyshev points the spreading is even, and the inflation is the same at every point to within a factor of two.

The pole is a reminder that this is not the whole story. On $1/(1.05 - x)$ leave-one-out tracked the best degree on equispaced points as well — a median gap of two at every noise — because the error the degree removes is concentrated at the right end, where the noise is amplified, and the two effects are traded at the same place. On Chebyshev points it does the same, with the same costs, 1.02 to 1.03. Changing the points helped the function whose difficulty sits in the middle and changed nothing for the function whose difficulty sits at an end, and the degree that is safe to overshoot found the smooth function forgiving to every rule on any points, which it remains.

What two point sets do not show #

Two point sets of one size are a comparison, not a law. The leverage profile of $(2d+1)/m$ is a property of Chebyshev points of the first kind; the second kind, which include the ends, and the clustered sets of the earlier essays would give their own, and data that arrive where they arrive give whatever their distribution does. The ends’ best degree is measured as the larger of two errors, which is the right measure for a boundary value and a pessimistic one for a fit evaluated near but not at the end. And the cap of 190 is close enough to 200 that every rule’s arithmetic is strained there; what happens beyond the last few degrees, where the system is nearly square, belongs to interpolation rather than fitting.

Still open: data that arrive unevenly, and a score that knows its spread #

Points from a distribution. Data rarely arrive on a grid. Drawn uniformly at random on $[-1, 1]$ they leave gaps and clumps, and a point alone in a gap has high leverage at any degree. The prediction with a sign is that on 200 uniform random points leave-one-out on $|x|$ at noise $10^{-4}$ stops before degree 40 on most draws, earlier than on the equispaced grid’s 26 on some, and that generalised cross-validation, which averages the spread away, chooses within ten degrees of the best on four draws in five — so that on scattered data the averaged rule is the safe one by a wider margin than on a grid.

A score that reads the spread first. If the two rules differ only through the spread of the leverages, a code can compute the ratio of the largest leverage to the average at each candidate degree, which costs nothing in an orthonormal basis, and use leave-one-out only while it stays below some bound. The prediction is that a bound of three reproduces leave-one-out’s choice on Chebyshev points on every draw and generalised cross-validation’s on equispaced points above degree 20, at no cost on either set — and that no single bound does better than switching to the averaged rule outright.