An extremum is still not a sample

An error found and named and repaired in three places is not an error that has been dealt with. It was live in a fourth place while the essay about it was being written, in the same repository, on a set the essay’s own examples were computed over.

The claim #

The worst surface in the test set is not the worst surface, and the shortfall is exactly the shape the earlier essay predicted.

• The lattice understates its own region’s supremum by 8.0 to 33.9 per cent across the fourteen changes of light in the adaptation census.
• The largest shortfall is on the row whose peak is carried by fewest surfaces, the macular pigment, which is also the row with the largest worst-to-mean ratio at 3.00. Concentration measured the other way the census measures it — the participation ratio — does not order the table, and the row that breaks it is below.
• The mechanism is the one already written down: a sample maximum converges on a population maximum at a rate set by how much of the set is near the maximum, and a narrow peak is narrow because it is a peak.
• The replacement is a search, not a finer lattice. Refining the grid buys a per cent or two per doubling; searching the region gives the answer.
• Four instances now, in four unrelated places, which makes the recurrence the finding rather than any of the four numbers.

The three that were found #

Two rounds ago this collection audited three measurements that had been made by walking over a set of points and keeping the largest thing found.

The axes of a discrimination ellipse, taken as the largest and smallest of forty-eight radii, short by a factor of 2.19 on the worst ellipse. The shape of an optimum, taken from twenty-four random directions, reporting a bowl 8.0 times longer one way than another where the answer is 29.8. The worst change of light, taken as the largest of fourteen changes on a list, where the family those fourteen were drawn from reaches six times further.

The essay that reported them stated the general rule correctly and stated it once: a sample mean converges at a rate that depends only on how many samples were taken; a sample maximum converges at a rate that depends on how much of the set is near the maximum, and in every case here that fraction is small and gets smaller as the extremum gets more extreme.

And then quoted, as evidence, numbers averaged over a set of surfaces whose own maximum nobody had asked about.

The fourth #

The census’s residual for a change of light is a mean over the 125 test surfaces. Reporting the worst case as well as the mean is new this round, and the obvious way to report it is the largest of the 125 values already computed.

That is precisely the error.

Every row is short, and the shortfall spans a factor of four across the table.

Why it is largest where the answer is #

The rule from the earlier essay predicts the ordering of that column, and it does.

The residual over the region is a smooth function of three parameters — a brightness and two modulation depths — and its maximum sits on the region’s boundary, at the deepest admissible modulation. Near that boundary the function’s curvature decides how wide the peak is: a sharply peaked function reaches its maximum in a small neighbourhood, and a lattice with a fixed spacing lands in that neighbourhood only by luck.

And curvature correlates with concentration. The macular row’s distribution is the most concentrated in the census — a narrow absorption inside the eye reaches some spectra hard and most not at all — so its residual rises steeply towards the corner where the surfaces that meet it are, and the lattice’s nearest grid point is well down the slope. The green-wall rows have the flattest distributions, their surfaces are treated more alike, and their lattice maxima are within ten per cent.

So the same property that makes a row’s worst case interesting is the property that makes it hard to find by sampling. That is the earlier essay’s sentence, unchanged, applied to a different set.

Sorting the values shows that there is a peak; ordering them by how much each contributes to the row’s mean shows how few objects the peak is made of. The macular row’s largest single surface carries 2.40 per cent of the total, the largest share anywhere in the census, and the curve falls away from it steeply. The neighbourhood in which the residual is within a few per cent of its maximum therefore contains very few of the 125 members, and a grid whose spacing overshoots that neighbourhood misses the answer by a third.

The other end of the census is the control. A green wall bounced twice is the harshest change of light in the table by mean residual and the flattest by distribution: its largest surface carries 1.37 per cent, its participation ratio is 110.8 effective surfaces of 125, and its lattice maximum is short by 11.1 per cent against the macular row’s 33.9. The row with the biggest number in it is not the row the lattice has trouble with.

And the ordering across the middle of the table is looser than its two ends make it look, which the census’s own statistics say plainly enough. A white LED’s distribution is more concentrated than the macular pigment’s on the participation ratio — 91.9 effective surfaces of 125 against 94.4, the second-lowest in the census — and its shortfall is 14.5 per cent rather than 33.9. The two numbers are measuring different things. A participation ratio asks how many surfaces answer at all; the shortfall depends on how few of them sit near the maximum. On that second question the macular row is alone, its largest single surface carrying 2.40 per cent of the row against the LED’s 1.92, and it is the second question a grid search is at the mercy of.

What refining does not buy #

The instinct is to make the lattice finer, and it is worth measuring how bad that instinct is.

The region’s maximum sits on a two-dimensional boundary, so a lattice’s best approach to it improves roughly linearly in the grid spacing. Halving the spacing means eight times the members and closes about half the gap. Getting the macular row’s 33.9 per cent down to one per cent needs the spacing cut by a factor of thirty — a lattice of some three million surfaces, to answer a question a five-start simplex answers in a second and a half.

And a finer lattice changes the mean while it is chasing the maximum, because refining a lattice under a constraint is not the same as adding samples. So the repair for the maximum degrades the quantity that was already right, which is a reason to keep the two computations separate: the lattice for the mean, a search for the supremum.

Why the class recurs #

Four instances in three rounds, in four unrelated pieces of machinery, written by the same discipline that had already diagnosed the fault. That is worth an explanation.

A maximum over a set is the natural implementation, which is why it recurs wherever a set is constructed. The set exists, the values exist, Math.max is one call and returns a number of the right type and a plausible magnitude. The alternative — set up a search, choose starts, decide a feasible region, worry about local optima — is fifty lines and a paragraph of justification. The wrong answer is a hundred times cheaper to write and looks the same.

Nothing downstream can see it. A maximum that is short by a third is a smaller number, not a malformed one. It plots, it compares, it satisfies every gate on this site — the shape a plausible wrong answer always has, and it produces an argument that is qualitatively correct and quantitatively out — the shape a plausible wrong answer has.

And the diagnosis does not transfer by being written down. The earlier essay is in this collection, is linked from the ladder, and names the rule. What it could not do is enumerate the places the rule applies, because the fourth place did not exist yet — the per-surface residuals were only recovered this round, and the moment they existed, the maximum over them was the obvious thing to quote.

The general form is worth putting bluntly: any time a set is constructed and then a max is taken over it, the answer is a lower bound. That sentence, applied mechanically, would have caught all four.

What was done about it #

The worst-case column now comes from a search over the region and the lattice’s own maximum is reported beside it, so the gap is visible rather than assumed away. The search uses five starting points, at the region’s centre and at the four corners of its modulation square, because the residual has a local maximum near each corner and a single start from the middle finds a saddle on several rows.

The lattice maximum is kept rather than removed, which is the decision worth defending. It is the number a reader would compute, it is the number every earlier version of this argument used, and printing the two together is the only way the gap is legible. A table showing only the corrected value would have quietly replaced a wrong number with a right one and taught nobody anything.

The assertion attached requires the gap to be non-trivial on at least one row, which is a check that the search is doing something the lattice cannot — if a future change made the region’s maximum land on a lattice point everywhere, that would be worth knowing rather than worth passing silently.

The rule, as something to apply #

The four instances differ in every detail and share a shape, and the shape is short enough to be used rather than remembered.

Wherever a set is constructed and an extremum is taken over it, the answer is a lower bound on the extremum and the shortfall grows with the answer.

Three questions follow it and each has a cheap answer:

Is the extremum on a boundary of the construction? If it is, the construction’s own limits are what is being reported and the number is a reading of a declaration rather than of the objective. All fourteen rows here are in that state.

How narrow is the peak? The width of the neighbourhood in which the objective is within a few per cent of its maximum, relative to the sampling spacing, is exactly the shortfall’s determinant. It can be estimated by evaluating the objective at the sample maximum’s neighbours, which costs nothing and predicts the gap to within a factor.

And is there a search available? For a smooth objective over a low-dimensional region there almost always is, and it costs seconds. The reason the sample maximum keeps winning is that it is already written, not that the alternative is expensive.

Applied to the three earlier instances, the first question catches the worst-change-of-light case, the second catches the ellipse case, and the third catches the bowl. All four are caught by three questions that fit in a comment.

Where the model stops #

The search is a Nelder–Mead simplex from five starts, which is not a proof of global optimality. Its answers agree to five decimal places across starts on every row, and the region is three-dimensional with a smooth objective, so the risk is small — but small is a judgement, not a bound.

A genuine bound would need the residual’s Lipschitz constant over the region, which is available in principle and has not been computed. The honest report is that the right column is a lower bound too, tighter than the lattice’s by the amounts above, and that the direction of every remaining error is known.

What the search had to get right #

Three details of the replacement, because a search that is wrong in a different way is not an improvement.

Five starts, not one. The residual has a local maximum near each corner of the region’s modulation square, and the corners are four separate places to be saturated in four different spectral directions. A single simplex from the region’s centre lands on a saddle on several rows and reports a value below the lattice’s own maximum, which would have looked like the search failing rather than like the start being wrong.

The feasible test returns a large cost rather than throwing. The simplex evaluates points outside the region several hundred times per run, and an exception per infeasible step is control flow rather than error handling. Returning a large finite number keeps the search moving and keeps the profile readable.

And the answers are compared across starts rather than trusted. They agree to five decimal places on every row, which is the evidence that the objective is unimodal enough for this to be a supremum rather than the best of five local answers. That agreement is checked and is not a proof — the essay says so above rather than claiming a bound it does not have.

Who found it, and when #

The statistics is extreme-value theory’s and the practical form is standard in optimisation: the maximum of a function over a grid is a lower bound whose quality depends on the function’s modulus of continuity, and grid search is the method of last resort for exactly that reason.

Its fourth appearance here was not found by looking. It was found because reporting a worst case required deciding what a worst case meant, and the earlier essay’s rule was recent enough to be remembered at the moment of deciding. That is a weak mechanism and it worked once. The stronger one is the sentence above about max over a constructed set, which is now the rule this collection applies rather than the example it remembers.

The one place a sample maximum is right #

Worth naming, because a rule with no exception invites being applied where it does not belong.

A sample maximum is the correct answer when the set is the population — when the question is what is the worst member of this collection rather than what is the worst object of this kind. A printer asking which of the twenty-four patches on their chart came out worst is asking the first question, and the largest of twenty-four values is exactly the answer.

The four instances here are all the second question wearing the first one’s clothes. The forty-eight radii were a sample of a continuous ellipse boundary; the twenty-four directions were a sample of a sphere; the fourteen listed changes of light were a sample of a family; the 125 surfaces are a sample of a region. In every case the set was constructed to stand for something larger, and the moment a set stands for something larger its maximum stops being the maximum.

The test is one question: is there anything outside this set that the argument is about? If yes, max is a lower bound.

The gap is widest where the answer is largest, in the units the table does not print #

The hero figure’s caption says the gap is widest where the answer is largest. The table underneath it says otherwise, and the two are reconciled by noticing which quantity each is talking about.

Ranking the nine rows by the region’s supremum and by the percentage in the short by column, the rank correlation between them is +0.20 — which over nine rows is indistinguishable from none. The macular row has the third smallest answer in the table and the largest shortfall in it; the green-wall row has the largest answer and the third smallest shortfall. Those two rows alone falsify the caption as written.

Ranking instead by the gap in ΔE units — the region’s supremum minus the lattice’s, which is what the figure’s bars actually show — the correlation is +0.87.

So the caption is right about the figure and wrong about the column, and the essay’s general rule — the shortfall grows with the answer — inherits the same ambiguity. In absolute units the shortfall does grow with the answer; as a fraction of it, it does not. What the fraction tracks is the property the mechanism section names, the concentration of the row’s distribution, and those two are independent: a change of light can produce a large residual on every surface, in which case the lattice finds the maximum easily and the gap is small next to a large answer.

The distinction matters for the rule’s practical use. Somebody applying it to decide whether to bother searching wants the fraction, because that is what says how wrong the number is. Somebody deciding which row to search first wants the absolute gap, because that is what says how much ΔE is at stake. Here those two orderings disagree almost completely, and the triphosphor row is the one that should be searched first on the second criterion while the macular row is the one the first criterion picks.

What the shortfall is a percentage of #

One more convention worth stating, since the column’s heading does not. Short by is the gap as a fraction of the lattice value, not of the region’s. Recomputing both ways: against the lattice the column reads 33.9, 23.4, 22.9, 19.4, 14.5, 13.7, 11.1, 8.2, 8.0, which is the published column to a tenth; against the region’s supremum it reads 25.3, 19.0, 18.7, 16.3, 12.7, 12.0, 10.0, 7.6, 7.4.

Both are defensible and they are answers to different questions. Against the lattice value it says how much the reported number has to be increased by; against the supremum it says what fraction of the true answer was missing. The essay’s own framing — a sample maximum is a lower bound on something — points at the second, and the second is the smaller number. The macular row is short by a third of what was reported and by a quarter of what is true.

The same rounding runs through the refinement arithmetic. Cutting the shortfall from 33.9 per cent to one per cent needs the spacing cut by 33.9 rather than by thirty, which is 4.9 million lattice members rather than 3.4 — the same conclusion, and half a million surfaces further from being worth doing.

Where the ladder goes next #

The supremum over the region has been found properly. What it is a supremum over is still two numbers somebody typed, and every one of the fourteen answers sits exactly on them.