Concept

Exchange algorithm — where it appears

Building a subset by adding the best next element and then trying every single swap until none improves. It has no optimality guarantee on a maximin objective, and its warrant is agreement with the exhaustive answer at the sizes where the exhaustive answer can still be computed.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

One curve is a binomial coefficient and the other is a line. The number of subsets a maximin over this dictionary would have to score, against the number the exchange algorithm actually scores. At three functions the walk is 2,024 subsets and is the honest answer; at eight it is 735,471 and the exchange algorithm has looked at 421. The warrant for the second curve is the four sizes where both exist and agree, which is a weak warrant — it says the algorithm has not yet been wrong, not that it cannot be — and it is the only one available past the point the first curve leaves the page.

Where the enumeration stops

A maximin over an eight-function dictionary is a walk over seventy subsets. Over twenty-four it is 735,471 at eight functions, and the exchange algorithm that replaces the walk scores 421. What licenses the second curve is four sizes where both exist and agree, which is a weaker warrant than it looks.

product · Optimum

Adding a run can make the design worse. The D-efficiency of the best N-run design at each size, against the optimal measure. It is not a rising curve. 13 runs reaches 99.77% and 14 falls to 99.44%, because the optimal weights are real numbers and N runs is an integer approximation to them, so how good a design can be depends on how well N divides. A Wald interval behaves the same way: a larger sample sometimes makes its coverage worse, for exactly this reason.

The design that has to be integers

The optimal design is a set of real weights and an experiment is a set of runs, so the theory's answer is never available. Thirteen runs reach 99.77% of it and fourteen reach 99.44% — adding a run makes the design worse per run, and the search that finds it does not always find the same one.

optimality · Criterion

Named alongside it

The objects these essays reach for when they reach for this one.

Optimal design Allocation Basis Blocking Closed form Combinatorial search Covariate balance D-optimality Design measure Experimental design Factorial design Greedy algorithm

All concepts