The minimum on the right

The data count their dimensions, not the step’s scored three rules for choosing the regularisation parameter λ against a per-draw oracle on eleven grids of a discretised deconvolution, from 16 points to 96, at three noise levels. The discrepancy principle’s worst draw anywhere was within 16 per cent of the oracle. Generalised cross-validation was better on the median draw and, on grids of thirty points and more, had draws thousands of times worse — 33 of 528 more than twice the oracle, eleven more than a hundred times.

That was not the reputation GCV brought to the comparison: on a single grid, choosing without knowing had found it landing on the oracle’s λ exactly. Every one of the eleven bad draws had picked λ of $10^{-6.67}$ or below. On a square system GCV minimises the residual squared over $(n - t)^2$, with $t$ the trace of the influence matrix, and as λ goes to zero the residual and $n - t$ go to zero together. On a coarse grid the resulting dip at small λ is the right answer, because the grid is its own filter. On a fine grid, whose smallest singular value is $10^{-7}$ of its largest, the same dip competes with the real minimum near $\lambda = 10^{-2.3}$, and on some draws wins.

The essay proposed the repair it had not made: refuse λ below the point where the residual has fallen under some fraction of its value at the real minimum. That removes the trap on the fine grids, and the question was whether it also removes the right answer on the coarse ones, where the oracle sits at the dip. It would be one threshold, and it would keep GCV’s one advantage over the discrepancy principle, which is that it needs no statement about the noise.

Which minimum is real #

The repair needs the real minimum identified without the answer, and on these curves there is a natural candidate. The GCV function is evaluated on 121 values of λ, fifteen to a decade from $10^{-8}$ to 1. Its local minima can be listed, and the one at the largest λ is the one furthest from the degenerate end. Call its residual $r_R$. The guarded rule minimises GCV over the λ whose residual is at least $\varphi\, r_R$.

At $\varphi = 0$ this is plain GCV. At $\varphi = 1$ nothing with a smaller residual than the rightmost minimum’s is admitted, and since the residual falls monotonically as λ does, that admits exactly the λ at and above the rightmost minimum — where the rightmost minimum is, by construction, the lowest point. So the guard at full strength is not a threshold at all. It is a different rule, simpler to state: take the local minimum at the largest λ.

Where the function has no interior minimum — a curve falling all the way to the floor of the search — the rightmost minimum is the global one and nothing changes. That is the coarse-grid case, and it is why the guard cannot cost those grids anything if their curves have that shape.

The worst draw on every grid #

At 0.1% noise per sample, plain GCV’s worst draws on the 40-, 48- and 64-point grids are 24, 2,944 and $4.0 \times 10^4$ times the oracle. The rightmost minimum’s worst draw on any grid is 1.63 times, on 34 points. The discrepancy principle’s is 1.13. At 0.01% the rightmost minimum’s worst is 1.24 and plain GCV’s $4.2 \times 10^3$.

On every grid of 28 points or fewer, at every noise level, the rightmost minimum and plain GCV return the same λ on every draw: the coarse grids’ curves fall to the floor and have no interior minimum to prefer. The fear that motivated a threshold — that refusing small λ would refuse the coarse grids’ right answer — does not arise, because on those grids the rule never has a reason to refuse anything.

Turn the dial to 1% and the picture changes in one respect. The thousandfold misses are gone there too, but four draws are still more than twice the oracle — 2.34, 5.01, 7.31 and 3.13 times, on the 30-, 34-, 48- and 96-point grids — where the discrepancy principle’s worst is 1.16. Those four are a different failure, and they are taken up below.

The curves, and where each rule stops on them #

On the 48-point grid at 0.1% noise the sixteen curves show why the rightmost minimum is the right choice here and why plain GCV is not. Every curve has a minimum between $\lambda = 10^{-3}$ and $10^{-2}$, where the oracle’s λ is, and every curve rises steeply to the right of it. To the left they differ. Most rise gently to a shoulder and fall again toward the floor; two fall all the way, to a value below the real minimum, and plain GCV picks them at $10^{-8}$ and $10^{-6.67}$ with errors 2,944 and 1,230 times the oracle’s. The rightmost minimum ignores the left half of the picture entirely, and its worst draw on this grid is 1.29 times the oracle.

The depth of the dip is not what makes it a trap; the dips that win are only 29 to 36 per cent below the real minimum’s value. It is that GCV compares two minima by one number and has no other way to choose between them. The rightmost-minimum rule breaks the tie with a fact about the problem rather than about the draw: the degenerate minimum is always the one at the small-λ end, because it is made of the singular values that end holds.

Why a threshold short of one does not work #

The threshold was proposed as a dial, and measured as one it is a poor one.

Plain GCV misses by more than twice on 33 draws and by more than a hundred times on eleven. A threshold of one tenth leaves 29 and eight. One half leaves 17 and two, with a worst of 327 times the oracle on the 64-point grid at 0.01%. Nine tenths leaves six and none; one leaves four and none. The count of catastrophes does not fall to zero until φ is nearly one.

The reason is in the residuals at the dips. Across the eleven catastrophic draws, the residual at the chosen dip is between 0 and 0.48 of the residual at the rightmost minimum. On the 40- and 48-point grids, where the dip is at the floor, the solution nearly interpolates the data: $n - t$ is below two and the residual is a few per cent of $r_R$ or less, so any threshold refuses it. On the 64-point grid the dips are not at the floor. They sit at $10^{-7.8}$ and $10^{-6.7}$, where $n - t$ is still 13 to 16.5 and the residual is 0.33 to 0.48 of $r_R$ — a shallower, intermediate dip where the grid’s small singular values begin — and a threshold must be above a half to refuse them. Between a dip that cannot be refused and one that can, there is a continuum of λ with residuals in between, and some of them have GCV values below the real minimum’s too. A threshold of 0.9 refuses nearly everything to the left; only 1 refuses it all.

So the one-number repair works at exactly one value of its number, and at that value it is not a residual threshold. That is worth knowing before anyone tunes φ on a test problem: the tuned value would be a statement about which dips that problem happens to have.

The draws it still misses #

The four misses at 1% have nothing to do with the degenerate end. On each, the rightmost interior minimum is to the left of the oracle’s λ — at $10^{-5.4}$ against $10^{-1.4}$ on the 30-point grid, $10^{-3.07}$ against $10^{-1.53}$ on 34 points, $10^{-2.8}$ against $10^{-1.47}$ on 48, and $10^{-2.4}$ against $10^{-1.6}$ on 96 — and at the oracle’s λ the function is still falling. There is no minimum near the right answer to prefer. GCV’s estimate of the predictive error, on these draws, simply keeps improving past the λ that the true error prefers, which is the milder shape of failure the data count their dimensions already recorded: a λ one to four decades below the oracle’s, costing two to fifty times.

No choice among GCV’s minima can repair that, because the fault is in the function rather than in the choice. It is also why the discrepancy principle keeps its advantage in the worst case. It is told the noise, and a rule told the noise cannot be misled by a draw whose predictive-error estimate is optimistic — the advantage a rule that has to be told how good its answer will be priced from the other side. Noise that spares the answer and fools the rules found the two rules missing in opposite directions under correlated noise; here, with the trap gone, they still do — GCV’s residual misses are all on the small-λ side.

What the typical draw pays #

The price of the discrepancy principle’s safety was always its median. It over-smooths, by design: it stops at the first λ whose residual matches the noise, which is on the safe side of the optimum.

The rightmost minimum keeps GCV’s median. Its median draw is below the discrepancy principle’s on 29 of the 33 grid-and-level cells, and its largest median anywhere is 1.037 times the oracle against the discrepancy principle’s 1.087. On the fine grids at 0.1% the difference is 1.003 against 1.054 on 48 points and 1.005 against 1.052 on 64. So the guarded rule is the better rule on the typical draw and the worse rule on the worst one, which is the same trade GCV always offered — with the thousandfold end of it removed.

A thousand draws on the collection’s own problem #

The grid essays’ problem is one construction. One draw in twenty measured GCV on the collection’s 64-point deconvolution over a thousand draws at each of five noise levels and found it failing by more than ten times on four to six draws in every hundred, with two kinds of failure: a minimum at the floor of the search, made of the dozen noise coefficients below it, and interior dips where a cluster of large noise coefficients looked like the edge of the signal.

The rightmost minimum removes most of both. Plain GCV fails by more than ten times on 40, 49, 57, 43 and 54 draws of a thousand from 10% noise to 0.001%; the rightmost minimum on 8, 5, 2, 2 and none — 17 in five thousand against 243. The worst draw falls from $6.8 \times 10^6$ times the oracle to 28, and at no noise level is it above 81. Floor failures are gone by construction. The interior dips that survive are the ones to the right of the true minimum, or the draws on which, as at 1% on the grids, the function has no minimum at the right place; at most eight draws in a thousand at any level.

It is not the discrepancy principle’s record, which over the same five thousand draws has none more than twice the oracle. But it changes what GCV is. A rule that fails by a factor of a million on one draw in twenty is not usable without a second opinion; one that fails by a factor of thirty or so on a few draws in a thousand is a rule with a tail, like every rule told nothing.

A rule told nothing no longer has a floor #

One draw in twenty closed on an uncomfortable finding about GCV’s advertised freedom from parameters: the smallest λ the search is allowed to look at is one. Searched down to $10^{-6}$ on the 64-point problem at 0.1% noise, GCV missed by more than ten times on 42 draws in a thousand; down to $10^{-14}$, on 202. Every extra decade at the bottom adds singular values below the floor whose noise coefficients can conspire into a dip, and the rule has no way to know that the dip is made of them.

The rightmost minimum does not care. At every floor from $10^{-6}$ to $10^{-14}$ it misses on the same two draws, and its worst draw is the same 80.7 times the oracle. That is what the argument for it predicts. Adding decades at the bottom adds possible minima at the bottom, and the rightmost minimum never looks there once it has found one further up. The parameter one draw in twenty found hidden inside the rule is gone, and the rule is again what it was sold as — a rule told nothing.

There is a practical corollary in the same measurement. To find the rightmost minimum there is no need to evaluate the whole curve: walk down from λ = 1 and stop at the first rise. On the thousand draws that walk evaluates the function a median of twenty times before it stops, at every floor, where the full sweep evaluates it 46 to 106 times. The safer rule is also the cheaper one, because it never visits the region where the trouble lives. The grid was the first filter made the point that a coarse discretisation regularises before λ does; a walk from the top is the same courtesy extended to the search, which regularises the choice by the order in which it looks.

Why the right end, and when it would be wrong #

The rule rests on one asymmetry, and it is worth saying what would break it. The degenerate dips are made of small singular values: at the floor, the directions the filter has not yet admitted; in the interior, a cluster of noise coefficients where the singular values are small enough for the noise to dominate. Both live at small λ because small λ is where small singular values are admitted. A minimum made of the signal’s own structure sits where the signal’s coefficients give way to the noise’s, which is at larger λ than any of them.

That fails in one situation measured here and one not measured. The measured one is the coarse grid, where the right answer is the smallest λ on the scale because the grid itself has already discarded everything the noise could use; it is handled, because those curves have no interior minimum and the rule falls back to the global one. The unmeasured one is a signal with content at two scales — a smooth part and a detail whose coefficients sit below a band of noise-dominated ones — where the GCV function could have a genuine minimum at large λ for the smooth part and a better one at small λ that admits the detail. The rightmost rule would take the first and lose the detail. Where the grid hands over to λ is the closest measured case of such a signal, and its step was recovered, but by a representation rather than by a rule; whether a two-scale signal defeats the rightmost minimum is the first thing to try against it.

What this does not settle #

The rightmost local minimum is found on a grid of fifteen values of λ to a decade. A finer grid resolves shallower wiggles and could create minima that are not features of the function at all; a coarser one could merge the real minimum into a shoulder. Neither is measured, and the rule as stated depends on the grid in a way the plain rule, which takes a global minimum, does not.

Square systems only, as before. With more data than unknowns the residual cannot go to zero and the degenerate end of the function changes shape; whether it still produces a dip, and whether the rightmost minimum is still the real one, is not asked.

Still open: more data than unknowns, and the dip that is on the right #

An instrument with more samples than unknowns. Every system here is square. With $m > n$, the residual at λ → 0 is the least-squares residual, which is not zero, and $m - t$ tends to $m - n$ rather than to zero. The degenerate dip should be gone by construction — a prediction with a sign, and the cheapest test of whether the trap was the squareness or the singular values.

The misses on the right. The four draws the rule still misses at 1%, and most of the survivors on the 64-point problem, are draws whose predictive-error estimate keeps falling past the right λ. A parameter chosen on a smaller problem found the rules transferring from a projected problem with a known bias. Whether the misses correlate with a quantity the data can compute — the mean square of the coefficients in the decade around the chosen λ, which one draw in twenty found 1.49 times its expected value on interior failures — would say whether a second test could flag them without being told the noise.