Where the enumeration stops

Choosing a balancing basis by its worst case is a finite optimisation with an exact answer. Score every k-subset of the dictionary against every shape worth protecting, keep the subset whose worst shape is best off. On eight functions that is at most seventy subsets, and the answer is the answer — no algorithm, no convergence, no starting point.

Two covariates make the dictionary twenty-four terms, and the walk stops being affordable somewhere in the middle of the range anybody would want. This essay is about what replaces it and what the replacement is worth, and it has a second finding that the one-covariate field could not have: the first thing a maximin buys is an interaction, and it is not optional.

Two curves #

The walk over C(24, k) is 24 subsets at one function, 276 at two, 2,024 at three, 10,626 at four, 42,504 at five, 134,596 at six and 735,471 at eight. The whole power set is 16,777,216.

The replacement is forward selection with exchanges: add the function that most improves the worst case, repeat to size k, then try every single swap until none improves. It is deterministic, so the same dictionary gives the same answer, and it scores 47 subsets at one function, 132 at three, 170 at four, 346 at six and 421 at eight.

At eight functions that is 421 against 735,471 — 0.06% of the work. The curves diverge because one of them is a binomial coefficient and the other grows roughly with k times the dictionary size.

What the second curve’s warrant actually is #

The exchange algorithm agrees with the walk at every size the walk is affordable at: 0 and 0 at one and two functions, 0.42441 at three, 0.63662 at four. Four sizes, four agreements.

It is worth being precise about what that licenses, because it is easy to overstate. It says the algorithm has not yet been wrong on this dictionary against this list of shapes. It does not say it cannot be. The maximin objective is a minimum over shapes, which is not concave in any useful sense on a discrete set, and a forward-selection procedure on such an objective has no optimality guarantee at all — there is no submodularity argument available here, and the field does not pretend there is.

A warrant of the form it agreed wherever the walk was affordable is the only one available past that point, and stating it plainly is the alternative to letting an algorithm’s output inherit the authority of the exact answers it sits beside in the same table. The hollow points in the figure mark the sizes where the walk was actually run; the filled ones are the algorithm alone, and the distinction is drawn rather than described.

One thing does mildly strengthen the case. The exchange pass is run to convergence rather than for a fixed number of rounds, so the answer is at least a local maximum under single swaps — no one function can be replaced by any other and do better. On a problem this small that rules out a great many ways of being wrong, and it rules out none of the ways that involve two functions at once.

The second curve is not “roughly a line” — it is two exact terms #

The algorithm’s counts have a closed form, and recovering it is worth the paragraph because it says how the cost will behave on a dictionary this field has not tried.

Forward selection from a dictionary of D functions scores $D, D-1, \ldots, D-k+1$ candidates on its way to size k, which is $kD - k(k-1)/2$. One round of exchanges then tries every chosen function against every unchosen one: $k(D-k)$ more.

At D = 24 that gives 24 + 23 = 47 at one function, 69 + 63 = 132 at three, and 90 + 80 = 170 at four — the three measured counts exactly.

At six and eight it gives 237 and 292 against the 346 and 421 measured, and the difference is one more exchange round apiece: 129 + 2 × 108 = 345, and 164 + 2 × 128 = 420. So the algorithm runs a single exchange round up to four functions and two rounds at six and eight, which is the count telling the reader something about how the search behaved rather than merely how much it cost.

Which says where the two curves cross, and where they go next #

The formula settles a question the log-scale picture cannot: at what size the replacement starts being the cheaper one.

At k = 1 the exhaustive search scores 24 subsets and the algorithm scores 47, so the algorithm is nearly twice as expensive — it does the same work and then checks every swap. From k = 2 on, 276 against 91, the exhaustive search never catches up again.

More usefully, it says what happens on a dictionary this field cannot try. At three covariates the dictionary is 124 terms. Choosing four of them exhaustively is $\binom{124}{4} = 9.4$ million subsets; the algorithm scores $4 \times 124 - 6 + 2 \times 4 \times 120 = 1{,}450$ — a ratio of 6,500 to 1. Choosing eight is on the order of $10^{11}$ subsets against 2,820.

The exhaustive search grows like $D^k$ and the replacement grows like $kD$. That is the whole reason one of them survives a second covariate and the other does not, and it is also why the replacement’s cost is nearly flat in k while its warrant is not.

The first purchase is an interaction #

The guarantee curve is the second finding, and it is the one that could not appear on a single covariate.

At one function the best guarantee is 0. At two functions it is 0. Not small: zero, because two of the seven shapes on the list are pure interactions and no combination of main effects touches them.

The smallest basis with a guarantee at all is three functions, and it is the covariate, its square, and the covariate above the second’s median — a main effect, a main effect, and an interaction. It guarantees 0.42441.

So the answer to what should the rule read is settled by the list of shapes before any optimisation happens. If the list contains a pure interaction, every basis without an interaction term guarantees zero, and there is nothing for a maximin to choose among. The optimisation only starts doing work above that threshold.

A maximin over a list is a statement about the list, and the list has an interaction in it or it does not. Somebody who writes down only main-effect shapes will get a main-effect basis and a guarantee that is silent about the case they did not write down — which is the same failure the one-covariate field finds when a guarantee over a list is offered over their span, arriving here through a different door.

What the algorithm actually buys, term by term #

The sequence the exchange algorithm builds is worth reading, because it is more informative than the guarantee curve and it costs nothing extra.

At one function it takes the covariate. At two it adds its square. Neither helps the worst case at all — the guarantee is zero at both sizes — so the choice at those sizes is arbitrary in the only sense the objective can see, and the algorithm’s answer is whatever its tie-breaking produces. That is worth knowing rather than hiding: a maximin over a list containing an unprotectable shape has no preference at all among bases below the size that protects it, and any reported basis at those sizes is a fact about the implementation.

At three it adds the covariate above the second’s median — the first interaction, and the first non-zero guarantee. At four it adds the second covariate, taking the guarantee to 2/π. At five it adds the covariate’s cube and the guarantee does not move. At six it restructures: the basis becomes the covariate, its square, the interaction, both median splits, and the product of the two covariates — and the guarantee jumps to 0.81831.

The restructuring at six is the useful part. The algorithm did not merely add a function; the exchange pass replaced two of the earlier choices, which is exactly what forward selection alone would not do and is why the exchange pass is there. A greedy sequence is nested by construction and the maximin optima at consecutive sizes are not, so a procedure that only ever adds is guaranteed to be wrong somewhere on a problem like this.

Four functions, and a number this site has met before #

At four functions the guarantee is 0.63662, and that is 2/π.

It is the same 2/π the one-covariate field arrives at — the share of a median split’s variance that balancing the covariate’s mean removes — and it turns up here as the worst case over seven shapes rather than as a single projection. The binding shape at four functions is a median split of the covariate the basis reads linearly, and once every other shape is protected above that level, 2/π is what the whole basis is worth.

Two things are worth taking from that. The first is a check: a number derived in a completely different setting reappearing to ten digits is evidence that the two-covariate machinery has not quietly broken the one-covariate case it contains. The second is a warning about reading maximin values as achievements. The guarantee stops rising between four functions and five — it is 0.63662 at both — because the fifth function the algorithm adds does nothing for the binding shape. A maximin guarantee is flat wherever the added function does not help the worst case, and a plateau in that curve is not a sign of diminishing returns in general; it is a sign that the same shape is still binding.

A guarantee of exactly one #

At six functions the guarantee is 0.81831, and at eight it is 1.00000.

A guarantee of one means every shape on the list is removed entirely — the seven shapes span a space of at most eight dimensions, and eight well-chosen dictionary terms contain it. So on this list there is a basis that leaves nothing at all, and the maximin problem is solved exactly rather than optimised.

That is the least useful number in the essay and it is worth saying why. A list of seven shapes is a tiny list. Getting to a guarantee of one against seven named shapes says nothing whatever about an eighth, and the one-covariate field’s exactly-zero result is precisely that a guarantee over a list is not a guarantee over the span of the list: the worst case over a subspace is the smallest principal-angle cosine, which is zero whenever the basis has fewer functions than the class has dimensions.

So the eight-function basis guarantees everything about seven shapes and nothing about the space they sit in, and the honest way to report it is as the completion of a list rather than as protection. Whether the list is the right one is not a question any of this machinery can answer, and the field that tries is the one that says so.

The cost of the list, which nobody counts #

There is a second combinatorial explosion in this problem and it is never mentioned, because it is not a computation.

The dictionary has twenty-four terms and the walk over its subsets is what this essay is about. The list of shapes has seven entries, and every one of them was written down by somebody. Seven is not a limitation of the arithmetic — scoring a basis against seventy shapes costs seventy inner products — it is a limitation of what an experimenter is prepared to commit to before the trial runs.

And the guarantee is a minimum over that list, so it can only fall as the list grows. Adding an eighth shape can take a guarantee of 0.63662 to anything down to zero, and the shape that does it is by definition one nobody thought of. The expensive part of a maximin is not the optimisation. It is the list, and the list is where the judgement is.

This is the same observation the one-covariate field makes and it gets sharper with a second covariate, because the space of shapes has grown quadratically too. Seven shapes over one covariate is a respectable sample of what an outcome might look like; seven over two covariates, of which two are interactions, is not obviously a sample of anything. Nothing in this essay’s arithmetic says how many shapes are enough, and nothing in it could.

Where the walk should still be run #

The practical reading of the two curves is narrower than use the algorithm.

Below five functions, walk it. Ten thousand subsets is milliseconds, the answer is exact, and there is no reason to accept a warrant when a proof is available. Most balancing rules in practice read three or four functions.

Above that, the algorithm, and say so. The failure mode is not that the algorithm returns nonsense; it is that a basis reported without its provenance reads as the maximin when it is a local maximum found by a particular procedure from a particular start.

And check the plateau. If the guarantee has not risen between k and k + 1, the binding shape has not changed, and adding functions is buying nothing — which is a fact about the list rather than about the algorithm, and is visible without any optimisation at all.

Why not just take all of them #

The reading that makes all of this unnecessary is balance everything — twenty-four constraints, a guarantee of one against any list at all, and no optimisation. It deserves a direct answer rather than an appeal to taste.

Every function a rule balances is a constraint on the assignment, and constraints are the currency the randomisation is paid for in. The one-covariate field measures this by walking every split of sixteen units and watching the admissible count fall to nothing at six constraints — at which point the rule is deterministic, has no reference distribution, and cannot support a randomisation test at all.

Twenty-four constraints is four times that. So on the small-trial evidence, balance everything is not a conservative choice with a computational cost; it is a choice that empties the assignment space and takes the inferential machinery with it.

That is the argument as it stands at the end of the one-covariate field, and it is the argument the next essay takes apart. The extrapolation from sixteen units turns out to be wrong in a way that changes the recommendation, and the reason it is wrong is that the quantity that falls with constraints and the quantity that grows with the trial are different quantities.

What is claimed here, and what is not #

This essay takes choosing a basis when the subsets cannot be walked, and the claims are the two growth curves, the agreement between the algorithm and the walk at the four sizes where both exist, the zero guarantee below three functions, and the reappearance of 2/π as a worst case at four.

What stays out and is named as a decision: any optimality guarantee for the exchange algorithm, which is not available and is not claimed; randomising the basis, which the one-covariate field measures and which would need a distribution over twenty-four terms rather than eight; and what any of these bases cost in randomisation, which is the next essay.

The boundary against the one-covariate field is the size of the dictionary. That the maximin over a stated list is a finite optimisation, that its optimum need not equalise across shapes, and that a guarantee over a list says nothing about the span of the list are all established there.

The checks, and the refusals that make them mean something #

Two claims are gated in this field’s library. The exchange algorithm is required to reach the walked answer at every size the walk is affordable at, and to do it on under two per cent of the evaluations — which is the whole warrant for the rest of the curve and is checked rather than asserted. And the guarantee is required to be exactly zero at one and two functions and above a tenth at three, with the three-function optimum containing an interaction term, which fails if the first purchase were being described as a matter of degree.

The refusal here is inherited rather than local, and it is the one from the field this extends: a basis reported at the shape it happens to be best against. Every number in this essay is a worst case over a stated list, and a worst case quoted as a typical case is the failure the whole construction exists to prevent.