A spread carried from the trace before

A spread measured on probes it does not average put a trace estimator on the normal table. Draw a pilot of p Rademacher probes $z$, record $z^{\mathsf T}Az$ for each, and use them only to estimate the spread of a single sample; from that spread fix, before another probe is drawn, how many fresh probes t the target needs; draw and average those. Because the number averaged does not depend on the probes being averaged, nothing selects the lucky runs, and with Student’s margin on the pilot’s p − 1 degrees of freedom the rule covered within the noise of 400 draws what the table says: about 68 per cent at one standard error, 95 at 1.96.

The price was the pilot — eight to thirty-two probes that are spent and thrown away — and the essay’s last section asked about the computations that would most like not to pay it. “In a computation that estimates many traces of related operators — the log-determinants inside an optimisation — the spread changes slowly from one to the next. A pilot run once and carried forward would remove the overhead after the first trace, at the cost of the pilot’s spread being stale. Whether the coverage survives a drift in the operator, and how much drift a stale pilot tolerates before Student’s margin stops covering it, is the measurement.”

It does not survive, at any drift worth the name. But the question has a second answer the proposal did not consider, and that one costs nothing.

A sequence that drifts in shape #

The operators are the earlier essays’ kind: 60 × 60 symmetric matrices with eigenvalues $d^k$ for $k = 0, \dots, 59$, the eigenvectors random but fixed for the whole sequence, so that only the spectrum moves. A sequence is sixteen of them, the decay $d$ starting at 0.9 and falling by a fixed step each trace — 0.0025, 0.005, 0.01 or 0.02 — which steepens the spectrum, the way the Hessian of an optimisation sharpens as it approaches a minimum with a few stiff directions.

What a two-stage rule reads from its pilot is not the spread of one probe but its relative spread: the standard deviation of $z^{\mathsf T}Az$ over its mean, which sets how many probes a relative target needs. For a Rademacher probe the variance of one sample is twice the sum of the squared off-diagonal entries — the formula counting what cannot be looked at derived, and the reason a diagonal matrix is estimated exactly by one probe — and the relative spread is its square root over the trace. It is a property of how the operator’s mass is distributed between its diagonal and the rest, not of its size, and that will matter at the end. At decay 0.9 it is 0.264; at 0.8, 0.426; at 0.7, 0.554. The drift steps therefore move it by 1.6 to 6.4 per cent a trace, and by the sixteenth trace it has grown from 0.264 to 0.332 at the slowest drift and to 0.670 at the fastest. A fixed number of probes that was right for the first trace is short by the same factor for the last.

Three rules are run along each sequence, all with the 3% target and Student’s margin, each on 400 seeded sequences:

A fresh pilot every trace — eight probes for the spread, then the fresh probes, at every operator; the earlier essay’s rule, applied sixteen times. The first pilot, frozen — eight probes at the first operator, and its relative spread used to fix the probe count at all sixteen. The last trace’s probes, carried — a pilot at the first operator only; from then on, the spread of the fresh probes the previous trace averaged is this trace’s pilot.

The frozen pilot falls away #

The figure at the top of the page is the sixteenth trace, the one where any drift has accumulated most, at one standard error.

With no drift all three rules are on the table: 66.0, 69.3 and 69.5 per cent, against 68.3. With the gentlest drift, a decay that has fallen from 0.9 to 0.8625 by the end, the frozen pilot’s last estimate is inside the target 52.0 times in a hundred. At 0.005 a trace it is 49.0, at 0.01 it is 39.3, at 0.02 it is 34.3. The fresh pilot stays between 62.5 and 72.0 throughout, and so does the carried spread, between 64.5 and 69.5.

Trace by trace the shape is what the arithmetic says it should be. At a drift of 0.005 a trace the frozen rule starts on the table and loses about a point and a third a trace, 54 at the ninth and 49 at the sixteenth; at 0.02 it is under 40 by the ninth. The other two do not trend. Turn the dial to the drift in size alone — each operator 5 per cent larger than the one before, its shape untouched — and the frozen rule sits on the table with the others to the last trace, because a rescaled operator has the same relative spread and the frozen number is still the right one.

The proposal’s phrase was “how much drift a stale pilot tolerates”, and the answer is almost none, for a simple reason: the stale pilot does not tolerate drift, it accumulates it. Every trace’s error in the spread is the sum of every step since the pilot, so even a drift of 1.6 per cent a trace has become 26 per cent by the sixteenth, and a quarter too few standard deviations in the margin is 16 points of coverage.

The drift is a factor on the margin #

The mechanism can be read off directly by asking each rule what spread it used and dividing by the true one. At a drift of 0.01 a trace the frozen rule’s ratio falls from 0.91 at the first trace to 0.63 at the eighth and 0.49 at the sixteenth: by the end it is fixing its probe count from half the spread the operator has. The fresh pilot’s median ratio is about 0.9 throughout. That is not drift; it is the small-sample bias that made Student’s margin necessary in the first place — a standard deviation estimated from eight numbers is more often too small than too large, and its median sits below the truth by about the amount Student’s quantile corrects for. The carried spread’s ratio is 0.97, which is one trace’s drift: it is measured on the operator one step back.

Put that ratio into the margin and Stein’s argument predicts the coverage. The rule fixes $t$ so that $k$ times its estimated standard error is the target; the true standard error is larger by the ratio of the true spread to the one used; so the fresh mean is inside the target when a Student variable on the rule’s degrees of freedom is inside $k$ times the inverse ratio.

Every trace of every sequence for every rule is one dot, 240 of them, and they lie along the diagonal: the largest gap between measured and predicted is six points, about two and a half standard errors of a share estimated from 400 sequences. The frozen rule’s predictions run down to 31.6 per cent at the fastest drift’s last trace and the measurements follow; the carried rule’s sit a point or two under the table, predicted and measured alike. Nothing about the drift is beyond the theory that calibrated the rule — it simply enters as a factor the rule cannot see.

The spread that is already there #

The carried rule exists because the probes a trace estimator averages are themselves the best available estimate of the spread for the next operator, and they are free. Every trace draws $t$ fresh probes, typically seventy to five hundred here, and computes their mean; their standard deviation costs one more sum. For the next operator, that spread is one step stale and estimated on $t - 1$ degrees of freedom instead of the pilot’s seven.

And it keeps the property Stein’s rule was built on. The earlier essays traced the sequential rule’s shortfall to selection: a rule that decides how many probes to average by looking at the probes it is averaging stops early on the streams that happen to look quiet. The carried spread comes from the previous operator’s probes, which are independent of this operator’s — a fresh random stream — so the number this trace averages still does not depend on anything this trace draws. The selection stays gone. That distinction is the whole of what the miss a normal table already priced measured: the sequential rule, which reads its spread from the probes it is about to average, misses a few points more often than the table because its early stops are its unlucky ones, while a spread from somewhere else — a pilot, or here the operator before — carries no such bias. A rule that reads only its own probes found the sequential rule’s worst draw three times its target for the same reason. The carried rule could have been written as the sequential rule run across operators, stopping each trace on a running spread that includes the previous trace’s probes, and it would then have re-imported the selection on every trace. Keeping the previous trace’s spread as a fixed number, decided before this trace draws anything, is what keeps it out. What it gives up is exactness under drift, and the ratio figure shows how much: one step’s worth, 0.96 to 0.98 at every drift.

That is why the carried rule’s coverage is flat in the drift while the frozen rule’s falls. Its error is the drift per trace, not the drift since the start, and a drift of 6.4 per cent a trace — the fastest here, a decay that goes from 0.9 to 0.6 in sixteen operators — is worth two or three points of coverage at one standard error. A factorisation kept past its date found the same contrast for a Cholesky factor reused along a drifting sequence: the factor that is never refreshed accumulates the drift until it stops working, and what decides how long it lasts is how fast the operator moves rather than how far it has to go.

What carrying saves #

The carried rule pays the pilot once instead of sixteen times, and it pays a second saving that is less obvious: its margin is Student’s on seventy or more degrees of freedom instead of seven, which is the normal’s to within a few per cent. At one standard error with no drift the fresh pilot costs 1,402 products for the sixteen traces and the carried spread 1,257 — ten per cent fewer, nearly all of it the pilots. At 1.96 the gap is wider, 6,334 against 4,878, twenty-three per cent: Student’s 95 per cent quantile on seven degrees of freedom is 2.36 against the normal’s 1.96, which asks for $(2.36/1.96)^2 = 1.45$ times the probes, and the carried rule does not pay it.

With drift every rule spends more, because the operators get harder to estimate, and the gap holds: at 0.02 a trace and one standard error, 4,317 against 4,006. The frozen rule is the cheapest on every drift — 1,208 products whatever happens — and the reason is that it is wrong. It keeps averaging the number of probes the first operator needed while the later ones need two or three times as many, and its coverage is what that costs.

At 1.96, the same shape #

At 1.96 standard errors the frozen pilot falls more slowly in points and as surely: 92.8 per cent with no drift, then 89.0, 83.3, 75.0 and 63.0 at the four drift steps, against a table of 95. The margin is wider, so a quarter too little spread costs less of the tail; at the fastest drift the frozen rule averages the first operator’s 390 probes on a last operator that needs more than four times as many, and one estimate in three falls outside. The fresh pilot covers 93.3 to 95.3 throughout and the carried spread 93.3 to 96.0, the same flat line as at one standard error.

This is also where carrying pays most. A fresh pilot’s 95 per cent margin on seven degrees of freedom is 2.36, and over the sixteen traces it costs 6,334 products with no drift and 20,238 at the fastest; the carried spread costs 4,878 and 15,490 — a quarter less at every drift, for coverage that is, if anything, a point closer to the table.

A drift in size is not a drift #

The size-only sequence behind the dial shows the other half of what the proposal’s question was really about. An operator that grows by five per cent a trace has a trace that grows by five per cent a trace and a spread that grows by the same factor, and the rule reads only their ratio. Every rule covers within the draws’ noise of the table there, and the frozen pilot is exactly as good as a fresh one for the whole sequence.

So “how much has the operator changed” is the wrong measure of staleness. A Hessian that doubles in scale has not invalidated anything a relative target reads; one that changes the shape of its spectrum by a few per cent has. Where the drift lands made the same point about a preconditioner, where two drifts of the same relative size cost 19 iterations and 5 depending on which part of the spectrum they moved. For a trace estimator the part that matters is the ratio of the off-diagonal mass to the trace, and a code can watch that ratio for free on the carried probes: it is the number it is about to use.

What sixteen operators do not show #

One family of drift — a geometric spectrum steepening at fixed eigenvectors — one size, one target, sixteen traces. A drift that rotated the eigenvectors would change the Rademacher spread through the diagonal as well as through the spectrum, and could move the relative spread faster or slower than the eigenvalues suggest. A sequence whose drift reversed would let the frozen rule recover by accident. And the carried rule here carries one trace back; in a computation whose operators arrive in a different order from the one they drift in — the situation the order a batch arrives in measured for solves — the previous trace in the loop is not the nearest operator, and the staleness is whatever the loop’s order makes it.

Still open: a carried spread that knows its trend, and the contour #

A drift-aware carry. The carried rule’s only loss is one step of drift, and the drift is visible: two consecutive traces’ spreads give its rate. Multiplying the carried spread by the ratio of the last two — extrapolating one step — would remove the loss to first order. The prediction with a sign is that at the fastest drift it lifts the sixteenth trace’s coverage from 64.5 per cent to within a point of the table, and that on the no-drift sequence it costs coverage nowhere but inflates probe counts by the noise of a ratio of two estimated spreads — which, at seventy degrees of freedom each, is a few per cent.

A carried sketch. The split nobody is in a position to choose found that Hutch++'s best division between sketch and probes is readable from the sketch’s own singular values. Along a drifting sequence the sketch of the previous operator is, like its spread, a free and slightly stale object — its range is close to the next operator’s dominant range when the eigenvectors are fixed, as they are here. Whether a carried sketch, refreshed only by the new probes, keeps Hutch++'s rate along the sequence, and how much eigenvector rotation it survives, is the same question asked of the other half of the estimator.

The contour. Counting what is inside a circle estimates a trace whose exact value is an integer, and the earlier essay proposed a two-stage rule there with a target of half an integer. A spectrum that drifts across the contour changes that integer from one trace to the next, and a carried spread would then be carried across a jump; whether the coverage survives the jump, or whether a jump should be detected and answered with a fresh pilot, is where a sequence of contour counts would need this essay’s rule to be told something.