The theorem that says when to stop

A search that climbs uphill has a problem nobody usually mentions: it does not know where the top is.

The multiplicative algorithm of the previous essay improves the determinant of the information matrix at every step and converges to the design that maximises it. What it cannot do is tell, from the inside, whether it has arrived. The determinant is still creeping up in the sixth decimal place; is that the last of the climb, or is there another support point it has not found yet? Every iterative optimisation has this difficulty and the usual answer is a shrug dressed as a tolerance: stop when the change per step falls below 10⁻¹⁰, and hope.

This field does not have to do that, and the reason is a theorem with an equals sign in it.

The statement #

Let d(x) = f(x)′M⁻¹f(x) be the prediction variance at a setting x, per run, in units of σ². Let p be the number of parameters, which is six for the full quadratic in two factors.

Kiefer and Wolfowitz: a design measure is D-optimal if and only if the largest value of d(x) anywhere in the region equals p.

Not “is approximately p”. Not “tends to p”. Equals.

Three things about that sentence are load-bearing.

It is an equality, and equalities can be gated. This site learned the hard way what a loose tolerance does to an exact claim: a figure in the response-surface field asserted a rotatable design’s prediction variance was flat around a ring to within 2 × 10⁻³, and shipped it flat to 1.4 × 10⁻⁴, ten orders of magnitude worse than the property it existed to draw, because the design’s α had been written as 1.414 rather than √2. Where a claim is exact, gate it at machine precision. The assertion here requires max d − p below 10⁻⁹; what it reaches is 6.000000000059 against p = 6, an excess of about 6 × 10⁻¹¹.

It is an “if and only if”, so it is a certificate. One direction says the optimum satisfies the condition — mildly interesting. The other says anything satisfying the condition is the optimum, and that is what makes it a stopping rule. A search can check max d against p at every iteration and know, without ever being told the answer, whether it has arrived.

And it never mentions the determinant. The criterion being maximised is |M|. The condition that certifies the maximum is about the largest prediction variance in the region. Those are different quantities, computed from different parts of M, and the theorem says they meet at one design.

Why that is more surprising than it looks #

Take the second point seriously and it says something about a different criterion entirely.

G-optimality is the criterion that minimises the worst prediction variance in the region — a minimax objective, chosen by someone who cares about the region’s poorest-served corner rather than about the coefficients. Written as an efficiency it is p / max d, which is at most 1 exactly when max d is at least p.

So the theorem has a second reading. The best attainable value of max d over all designs is p. And the design attaining it is the D-optimal one. The D-optimal design is also the G-optimal design, with G-efficiency exactly 1, and nothing in the two definitions suggests it.

One maximises a volume of information about six parameters. The other minimises a worst case over a continuous region. They were formulated by different people for different reasons and they have one answer.

That is why G-efficiency needs no reference design anywhere in this field, where D-efficiency, A-efficiency and I-efficiency all do. The best attainable max d is known in closed form to be p, so p / max d is already an efficiency. The theorem shows up as a convenience before it shows up as a result.

The condition, drawn #

The picture is the argument, and it is worth reading slowly.

Along a cut through the region, d(x) rises and falls. At the nine support points of the optimal measure it reaches exactly 6. Between them it is below 6. Outside — there is no outside; the region is where the experiment can go.

Tangent, and never crossing. That is the whole theorem in a shape. A design whose curve dips below 6 everywhere would be leaving information unused, and there is nowhere it could be doing that from. A design whose curve goes above 6 somewhere has a setting where prediction is worse than it needs to be, and moving weight there would improve the determinant — which is exactly what the update rule does.

The multiplicative algorithm can now be read as a machine for enforcing the condition. It moves weight to wherever d exceeds its average, so the fixed point is where d is equal at every supported setting and below it elsewhere. The theorem says that equal value has to be p, and the algorithm reaches it without knowing.

Every design in the catalogue fails it, by an amount #

An equality everything satisfies is not a test. So the condition is applied to the designs a book would offer, where it must fail, and how badly is a measurement rather than a warning.

On the square region, with each design scaled to just fit it, the largest prediction variance anywhere is:

• the 3² factorial with equal runs: 7.250
• the thirteen-run design found by search: 6.882
• the face-centred composite: 10.273
• the rotatable composite: 28.600

Against p = 6 in every case.

Those excesses have a direct reading. A design with max d of 10.273 predicts its worst point as badly as the optimal design would with 6/10.273 = 58.4% of the runs. Put the other way, an experimenter using that design and caring about the region’s worst-served corner is throwing away over forty percent of their budget, at that corner, relative to a design nobody had to invent.

The certificate audits a design nobody searched for #

There is a practical consequence here that is easy to miss because the theorem is usually presented as an algorithmic device.

The condition can be evaluated on any design, by anybody, without running a search and without knowing what the optimum is. Compute M from the design’s own settings, invert it, evaluate d(x) over the region, take the largest value, divide p by it. What comes back is a number in (0, 1] that says what share of the attainable this design gets on the worst-case criterion — and it is exact, not a comparison against a reference somebody had to compute first.

So an experimenter handed a design in a protocol can ask “how good is this?” and get an answer in a few lines of arithmetic. The four numbers above become 82.8%, 87.2%, 58.4% and 21.0%, and none of them required the optimal design to be found.

That is unusual. Every other efficiency in this field — D, A, I — is a ratio against an optimum that has to be computed, so evaluating a design means solving the design problem first. G is the one where the denominator is known in advance, and the reason is precisely the theorem: the best attainable max d is p, and p is the number of parameters in the model, which the experimenter already knows.

It also means the certificate can convict a design without proposing a replacement. “The worst-served setting is being predicted four times worse than it needs to be” is a complete statement, and it does not require anybody to agree about what should have been run instead.

The audit has one more property worth having, which is that it points as well as scores. The setting where d attains its maximum is a location, and it says where the design is thin. For all three catalogue designs above that location is a corner of the region, at (−1, −1) and its three reflections — and the corners are settings every one of those designs actually runs.

That is the useful part. The worst-predicted point is not somewhere the design neglected to visit; it is where the model is working hardest, because a corner is where the interaction and both squared terms are simultaneously at their extremes, so a prediction there loads on every parameter at once. A design’s weakness is not in the gaps between its runs. It is at the place where the most estimates have to be added together, and the composite designs make it worse by spending five of their thirteen runs at the dead centre, where the quadratic terms carry no information at all.

An experimenter who cannot change the design can at least know not to make a decision at that corner, which is a use for the theorem that has nothing to do with optimisation.

The same theorem on a different region #

The region appears in the condition — max d is taken over it — and nowhere else. So the theorem holds whatever the region is, and the design it certifies changes.

That last figure needs its context or it is unfair. The rotatable composite is a design built for a circular region, where its prediction variance is famously constant around any ring — flat to 1.1 × 10⁻¹⁵ at α = √2, which this site measured. Scored on a square, where its axial runs at ±√2 fall outside the settings an experiment can reach and it has to be shrunk to fit, it is the worst design here by a wide margin.

Nothing has gone wrong with the theorem. The region changed, so max d is taken over a different set, so the certificate certifies a different design. Which is a large enough consequence to be an essay of its own, and the reason the region is a parameter everywhere in this field’s code rather than a fixed assumption written once.

Three criteria, three theorems, one shape #

The equality is usually stated for D-optimality alone, which makes p look like a special number. It is not. Every criterion in this field has a version of the same theorem, and writing all three down is what shows the shape.

Each criterion has a directional derivative δ(x) — how much the criterion improves when a little weight is moved to setting x — and an average of that derivative under the current measure, which turns out to have a name in each case:

where B is the moment matrix of the region itself. In every case the optimum is where max δ equals that average, with equality at every supported setting.

The three optima reach it to 5.9 × 10⁻¹¹, 1.8 × 10⁻¹⁰ and 3.7 × 10⁻¹¹ respectively. Their averages are p = 6, tr(M⁻¹) = 17.8922 and tr(M⁻¹B) = 3.7097 — three different numbers, and only the first happens to be an integer a reader recognises.

So D is not the criterion with a theorem. It is the criterion whose theorem’s right-hand side is the parameter count, which made it look like a fact about D and is a fact about the number six.

What the D-optimal design does not certify #

One consequence of the table above deserves stating, because the D–G coincidence invites over-reading.

The D-optimal measure has max d = 6, so its G-efficiency is 1. Its A-efficiency is not 1 and its I-efficiency is not 1, because those criteria have their own optima with their own conditions, and the D-optimum does not satisfy them. Its prediction variance averaged over the region is worse than the I-optimal design’s, and by a margin worth having.

The theorem certifies one design against one criterion, and the fact that the certificate happens to be readable as a second criterion is a property of that pair rather than a general result. Two criteria coinciding is the exception here; the rule is that they do not.

The four excesses, as runs #

The G-efficiencies are the right scale for comparing designs and the wrong one for deciding whether to run them, because an efficiency is a ratio and a budget is a count. Inverting them says what each catalogue design costs.

At the worst-served corner, the 3² factorial needs 1.21 times the optimal design’s runs, the searched thirteen-run design 1.15, the face-centred composite 1.71, and the rotatable composite brought inside a square 4.77.

The last of those is the number worth carrying. Nearly five experiments to reach, at that corner, what one experiment at the certified design reaches — and the design in question is the one a response-surface catalogue recommends and this site has elsewhere admired for a property it genuinely has on a different region. A design’s efficiency is a statement about a region, and moving the region turns a 1.1 × 10⁻¹⁵ flatness into a factor of five.

The two composite designs are also the two that spend five of thirteen runs at the centre, and the factorial and the searched design are the two that do not. That is the whole ordering of the column: a run at the centre of a square carries nothing about either squared term or the interaction, so a design spending 38% of its budget there is estimating three of its six parameters from eight runs.

Three gates, one precision #

The three equalities are reported as reaching 5.9 × 10⁻¹¹, 1.8 × 10⁻¹⁰ and 3.7 × 10⁻¹¹, which reads as three different qualities of solution and is not.

Divide each by the quantity it is an equality about — p = 6, tr(M⁻¹) = 17.8922, tr(M⁻¹B) = 3.7097 — and the three come out at 9.8 × 10⁻¹², 1.01 × 10⁻¹¹ and 1.00 × 10⁻¹¹. Within two per cent of each other.

All three optima are solved to the same relative precision, and the threefold spread in the absolute gaps is entirely the scale of the criterion. An absolute tolerance would have made A-optimality look three times harder to solve than D-optimality, and it is not harder at all — its right-hand side is simply three times larger.

That is an argument about how the gate should be written rather than about the designs. A condition of the form max δ equals its own average is scale-free in the criterion, so the tolerance on it should be too; an absolute 10⁻⁹ is a relative 1.7 × 10⁻¹⁰ for D and a relative 5.6 × 10⁻¹¹ for A, and a criterion whose average happened to be a thousand would sail through a gate that a criterion whose average is a thousandth could not pass.

The A-optimal measure’s own weights say what the different right-hand sides are buying. It puts 0.2332 at the centre where D puts 0.0962 — two and a half times as much — because a trace of an inverse is a sum over coefficients and is dominated by whichever is worst determined, while a determinant is a product and cannot let any direction go. D buys the corners and A buys the intercept, from the same nine settings.

Two routes, which is this site’s habit #

The stopping condition is a second route to a number that already had one, and that is why it is worth the essay rather than being a footnote in the algorithm.

The first route is the determinant: run the search, watch |M|^(1/p) rise, stop when it stops rising. That route gives 0.474594 and no way to know whether a longer run would give more.

The second route is the equivalence gap: run the search, watch max d fall towards 6, stop when it arrives. That route gives a number with a known target, so “arrived” is a fact rather than a judgement.

The two agree, which is the point. Two routes to every number is this site’s standing method and it is usually a closed form beside a simulation. Here it is a criterion beside a certificate, and the certificate is the stronger of the two because it can fail.

The check, and the refusal that makes it mean something #

The gate in this field’s library asserts the equality at 10⁻⁹ rather than at a comfortable tolerance, deliberately, and it asserts the G-efficiency separately at 10⁻⁶ on a grid four times finer than the one the search used — because a condition checked only at the candidates it was optimised over would be checking the algorithm’s arithmetic rather than the design’s property.

The refusal is every catalogue design in the table. All of them must exceed p, and the assertion requires it of every row rather than of the worst one, so a design that quietly satisfied the condition without being the optimum would fail the check and be worth investigating rather than being absorbed. The second half requires the worst of them to exceed p by more than 20%, so a table of designs that were all near-optimal would also fail — because a refusal that only ever rejects by a hair is a refusal that has not been tested either.