The criterion with no derivative

Three criteria here have been put through the same argument. Each has a directional derivative, each has an equivalence theorem saying the maximum of that derivative equals its own weighted average, and each is found by a multiplicative update that moves weight towards wherever the derivative is largest. All three converge, all three are certified at machine precision, and the pattern looks general.

There is a fourth criterion and it is not in that table. It is the one a reader who cares about the worst-determined direction actually wants, and it has no derivative.

What E-optimality is for #

The three criteria this field has measured are all averages of a kind.

D maximises the determinant of the information matrix, which is the volume of the confidence ellipsoid inverted — a geometric mean of the precisions along the principal directions. A minimises the trace of the inverse, which is the arithmetic mean of the variances of the coefficients. I minimises the average prediction variance over the region.

Each is a sum or a product over directions, and each can be satisfied by being very good in most directions and poor in one.

E cannot. It maximises the smallest eigenvalue of the information matrix, which is the precision along the worst-determined direction in parameter space. A design is E-optimal when there is no other design whose worst direction is better determined.

That is a minimax criterion, and it is the criterion a reader wants whenever a single badly-determined combination of coefficients would ruin the analysis — which is most of the time, and is why its absence from the field’s first table was a gap rather than an omission.

Where the derivative goes #

The smallest eigenvalue of a symmetric matrix is a continuous function of the matrix and it is not everywhere differentiable, and the place it fails is not obscure.

While the minimum is attained by exactly one eigenvalue, that eigenvalue moves smoothly: its derivative in the direction of a perturbation is $v'(\delta M)v$ with $v$ the corresponding unit eigenvector, and that is the directional derivative the search needs.

Where two eigenvalues sit at the minimum, there is no single $v$. The function is the minimum of two smooth functions, and a minimum of smooth functions has a corner along the set where they meet — the same corner $\min(x, -x)$ has at zero. Any convex combination of the two candidate derivatives is a subgradient, none of them is the derivative, and a search that takes one of them and steps will overshoot in a direction the other eigenvalue does not like.

And the optimum is almost always at the corner. That is not bad luck, it is the structure of the problem. Improving the smallest eigenvalue is worth doing until the second-smallest catches up, at which point any further improvement to the first must come at the second’s expense — so the optimum is where they meet, and the objective is non-smooth exactly there.

The criterion also has a reading in the units the rest of this field uses. How many places a design goes counts support points and the degrees of freedom they leave; E counts something adjacent — how nearly the design’s information matrix is singular, since the smallest eigenvalue going to zero is singularity arriving. A design at its minimum support has six settings spanning six directions with nothing to spare, which is exactly the configuration where one direction can be badly served, and E is the criterion that notices.

What a derivative-based search does #

The field’s other three criteria are found by a multiplicative update, and the natural thing is to write the same update with the smallest eigenvalue’s derivative in it.

That is not a slow convergence and it is not a tolerance. The derivative-based search stops, at a design whose worst direction is determined less than half as well as the optimum’s, and it stops because near the corner it is stepping on one eigenvalue’s gradient while the other one is falling.

The comparison with the D-optimal design is the part that should decide anybody’s opinion of the result. A design chosen for a completely different criterion, with no reference to eigenvalues at all, beats the E-optimal search by a third on E’s own quantity. A search that is worse than not searching is a search that is solving a different problem, and the different problem is the smooth one.

The method that works, and what it costs #

The repair is standard in convex optimisation and it is worth naming because it is not what this field has been using.

A subgradient method takes a step along any subgradient — here, the gradient corresponding to one of the eigenvalues at the minimum — with a step size that decreases like $1/\sqrt{t}$. It does not ask whether the objective is differentiable and it does not need to know the multiplicity. What it gives up is speed: it converges at $O(1/\sqrt{t})$ rather than geometrically, which is why the search here runs forty thousand iterations where the D-optimal measure converges in a few hundred.

Forty thousand iterations of a six-by-six eigendecomposition is under two seconds, so the cost is nothing in this problem and is the reason the non-smooth case is usually treated as a difficulty rather than a barrier.

What it does not give is a certificate. The equivalence theorem in its usual form is an equality between a maximum and an average of a derivative, and there is no derivative here. The corresponding statement for E-optimality exists and is a condition on a set of subgradients — there must be a convex combination of the eigenvectors at the minimum such that a related maximum is attained — which is checkable and is not the one-line equality the other three criteria have.

So this criterion costs the subject its certificate. The criterion that protects the worst case is the one that cannot say when it has arrived, which is the exact reverse of the property that says when to stop.

Two smooth functions, and the set where they meet #

The corner is easier to hold as a picture than as a definition, and the picture is two lines crossing.

Think of the weights as a path and the two smallest eigenvalues as two functions along it. Away from the crossing, one of them is below the other and the minimum is that one — smooth, with a derivative, and a search can follow it. Approaching the crossing, the lower one is rising and the other is falling. At the crossing they swap.

A search following the derivative of whichever is currently lower will, at the crossing, step in the direction that was improving the old minimum — and that direction is the one making the new minimum worse. The next iteration follows the other eigenvalue and steps back. The iterate oscillates across the crossing without making progress along it, which is what the 37.2% is: not a search converging slowly but a search arriving at the corner and being unable to move along it.

The subgradient method’s decreasing step is what fixes that. Steps that shrink like $1/\sqrt t$ let the oscillation damp out while the average direction of travel — which is along the crossing rather than across it — accumulates. It is slow for the same reason it works.

The failure is therefore not about eigenvalues. It is what happens to any derivative-following method at a minimum of several smooth functions, and the smallest eigenvalue is one example of that shape. A maximum over a family — a worst case over a set of parameter values, a minimum over a set of contrasts — has the same corner and the same cure.

What the E-optimal design looks like #

The design itself is worth reading, because it is not a small perturbation of the others.

It puts 0.398 of its weight at the centre — four times the D-optimal measure’s 0.0962 and nearly twice A’s 0.2332 — with the four edge midpoints at 0.100 each and the four corners at about 0.050. It is the most centre-heavy design in the field.

That weight is worth converting. In a design of, say, twenty runs, E asks for eight of them at the centre against D’s two and A’s five. It is not a small reweighting of the same arrangement; it is a visibly different experiment, and an experimenter shown the two run sheets would not guess they came from the same region and the same model.

The reason is what the worst-determined direction is. In a quadratic model on a square, the coefficients that are hardest to separate are the intercept and the two squared terms, because every corner has $x_1^{2} = x_2^{2} = 1$ and only the interior settings distinguish them. Weight at the centre is what buys that separation, and E — which is dominated by the worst direction — buys it heavily.

D, which is a product over directions, cannot afford to let any direction go and also cannot afford to over-serve one, so it spreads. The two designs differ because the criteria weight the same six directions differently, which is the disagreement this field’s last essay is about, arriving here in its sharpest form.

The design a certificate would have to check #

It is worth being concrete about what is missing, because “no certificate” can read as though nothing were checkable and that is not the case.

For the three smooth criteria the condition is an equality between two numbers: the largest directional derivative anywhere in the region, and its own weighted average. Both are computable from the design alone, and a design either satisfies it or does not — which is what lets a catalogue design be audited without finding the optimum.

For E the condition is an equality involving a choice: there must exist a convex combination of the eigenvectors at the repeated minimum such that a related maximum equals a computable average. Verifying it means searching over that combination, which is a small convex problem rather than an evaluation.

So the certificate is not absent, it is one level more expensive — an optimisation to check an optimisation, where the other three need only arithmetic. That is a real difference and it is why the subgradient answer here is reported as a best-so-far. The honest version of the field’s claim is that three of its four criteria can be audited by anybody with a matrix inverse and the fourth cannot, and that is the sense in which the non-smoothness costs something beyond the algorithm.

What it costs on the other criteria #

A design chosen for its worst direction is not free, and the cross-table prices it.

The E-optimal design is 73.7% D-efficient and its trace of the inverse is 15.3% above the A-optimal design’s — and the D-optimal design’s trace is 18.3% above it, which is the larger of the two. Being chosen for a worst direction is not what makes a design expensive on the average one. The E-optimal design is the worst row on two of the three other criteria, and it is the only row that is best on its own.

Read the other way, the D-optimal design’s smallest eigenvalue is 0.099268 against E’s 0.199987 — it is half as good on the quantity E is about. That is the largest disagreement between any two criteria in this field: on D’s own criterion, E is 74% efficient; on E’s criterion, D is 50%.

The asymmetry is the finding. A criterion that averages over directions tolerates a bad one cheaply; a criterion that reads the worst direction cannot tolerate a bad average at all, because the average is made of the directions. So choosing D and hoping the worst case is acceptable is a much worse bet than choosing E and hoping the average is.

Whether an experimenter should use it #

The measurements support a recommendation with a condition attached, which is the most this field ever offers.

Use E when a single combination of coefficients decides the analysis. A calibration where one contrast is the answer; a model where the difference between two squared terms is the hypothesis; any setting where a report is read through one linear combination. There, the worst-determined direction is the analysis, and a criterion that averages over directions is answering a question nobody asked.

Otherwise use D, or the average-prediction criterion, and know the worst case rather than assume it. The D-optimal design’s smallest eigenvalue is 0.099268 against the best available 0.199987, so a reader who computes it knows they are at 49.6% on that criterion. Computing it costs one eigendecomposition and needs no search.

And do not compute E with the field’s own algorithm. Every other criterion here is found by the multiplicative update and it is the wrong tool for this one. Where the objective is a minimum over a family, the step has to be a subgradient step, and the difference between the two is a factor of nearly three in the quantity being maximised.

That last recommendation is the one worth carrying out of the field, because the failure it describes is silent, and it is the same silence a fraction reporting an interaction as a main effect has and an estimator returning the edge of its range has. The derivative-based search converges: it produces a design, reports a value, and the value is a perfectly ordinary number. Nothing in its output says it stopped at a corner, and the only way to find out is to run a method that does not assume the objective is smooth and compare.

What is claimed here, and what is not #

The claim is about the criterion in this field whose objective is not differentiable: that the smallest eigenvalue of the information matrix is attained twice at the E-optimal design and once at the other three criteria’s optima; that a multiplicative search built on a derivative reaches 37.2% of the optimum and is beaten by the D-optimal design, which was not chosen for the criterion at all; that a subgradient ascent reaches 0.199987; and that the E-optimal design is 73.7% D-efficient while the D-optimal design is 49.6% E-efficient.

Every eigenvalue is computed by cyclic Jacobi rotation from the design’s own information matrix. The multiplicity is reported at a relative tolerance of $10^{-4}$, which is stated because the third eigenvalue sits at 0.20214 — about one per cent above the repeated pair — so the minimum is a clean double rather than a near-triple, and a looser tolerance would have called it three.

What stays out: the equivalence theorem for E-optimality in its subgradient form, which exists, is checkable and would need its own derivation and its own figure; exact E-optimal designs with a whole number of runs, where the combinatorial problem sits on top of the non-smooth one; and the whole class of criteria between A and E — the $\Phi_p$ family, of which A is $p=1$ and E is the limit — where the non-differentiability arrives continuously as the family approaches its endpoint.

The subgradient search’s answer is a best-so-far over forty thousand iterations rather than a certified optimum, for exactly the reason the essay is about: there is no one-line certificate to check it against. That it beats every other design in the field on its own criterion is the evidence available, and it is weaker evidence than this field is used to.

Still open: the criterion nobody can certify #

This ends with a gap rather than a result, and the gap is worth stating precisely because it is the kind that closes.

The subgradient condition for E-optimality is a real theorem and it is checkable: at the optimum there is a convex combination of the eigenvectors at the minimum for which a related maximum over the region equals a computable average. Implementing it would give this criterion the certificate the other three have, and would turn the search’s “best of forty thousand iterations” into “arrived”.

Until that is done, E-optimality is the one criterion here whose answer is claimed rather than certified. That is an uncomfortable place for a subject whose whole method is a test each claim could fail, and it is the honest state of it.

The check, and the refusal #

Three claims are gated. That the E-optimal design’s smallest eigenvalue is attained more than once, which is the essay’s premise stated as a count rather than as an observation. That the other three criteria’s optima have a simple minimum, which is the control — without it, a repeated minimum would be a property of the arithmetic rather than of this criterion. And that the E-optimal design has the largest smallest eigenvalue of the four, which is the definition made checkable.

The refusal is the derivative-based search, and it is required to fail: it must reach less than eighty per cent of the subgradient method’s answer. If the two methods agreed, the corner would be doing no work, the essay’s distinction between a differentiable objective and a non-smooth one would be a distinction with nothing behind it, and the whole comparison would be a paragraph about an algorithm’s tolerance. It reaches 37.2%, which is not a tolerance.