A rule that reads only its own probes

Every budget in these essays has been fixed in advance. Counting what cannot be looked at fixed the number of probes, a rate that belongs to the matrix swept it to measure a convergence rate, and the earlier measurement divided it between a sketch and probes. None of them asked when to stop, because the error against which everything is scored requires the exact trace and an estimator has no access to it.

It has access to something else. Hutchinson’s estimate is the mean of t independent samples zᵀAz, and the standard error of a mean of independent samples is $s/\sqrt{t}$ with $s$ the samples’ own standard deviation. So the estimator can report its own precision without knowing the answer, and a rule that stops when the relative standard error reaches a target needs nothing that is not already on hand.

The question is whether it is calibrated. It is, in the middle.

What the rule does #

Four knobs and one floor is where this field sets out what a rule scored against an oracle can and cannot claim, and the same standard applies here. Draw probes, keep a running sum and sum of squares, and after a warm-up of eight compute the sample standard deviation and the standard error. Stop at the first probe where the standard error divided by the current estimate’s magnitude is at or below the target.

On a 60×60 matrix whose eigenvalues decay by 0.9 per step, over forty independent probe streams:

The median column is the calibration and it is good: 0.63, 0.70 and 0.53 times the target. A rule promising one per cent delivers about half of one per cent on the typical draw, which is the conservatism a standard-error criterion should have, since the standard error is a standard deviation rather than a bound.

The warm-up is not decoration. Without it the rule computes a standard deviation from two samples on its second probe, and two samples of a quantity whose distribution has a tail will occasionally be close together — so the rule would stop at t = 2 on a handful of streams with a standard error it has no business reporting. Eight is the smallest number at which the sample standard deviation is worth anything, and the 10 per cent row below shows that even eight is the binding constraint at a loose target rather than the criterion.

And what it does not do #

The last column is the reason the rule is not a guarantee. At a 1 per cent target the worst of forty draws is 2.9 per cent — three times what was asked for — and 20 per cent of draws are outside the target.

There are two ways to be outside it and the rule suffers from both. The obvious one is that a standard error is a one-sigma quantity: even with s known exactly, the error of a mean exceeds one standard error on about a third of draws, which is why 68 to 80 per cent inside is what a correctly calibrated rule of this kind would produce rather than a failure of it.

The second is specific to estimating s from the same samples that produced the mean. At eight probes the sample standard deviation is itself uncertain by roughly $1/\sqrt{2\cdot 7} \approx 27$ per cent, so a stream whose first eight probes happened to be unusually similar reports a small standard error, stops, and is wrong about both quantities at once. That is the mechanism behind the 10 per cent row, where the median probe count is eight — the warm-up — and the rule is stopping at the first opportunity on a standard deviation it has barely measured.

So the rule is a median guarantee and it is worth having as one. What it cannot be read as is a bound, which is what its refusal is fed.

It is worth putting the two failure modes in order of size, because a reader deciding whether to use the rule needs to know which one to worry about.

The one-sigma effect is the larger and it is not a defect. A criterion built on one standard error will be exceeded on roughly a third of draws whatever else is true, so 70 to 80 per cent inside is the design of the rule rather than its failure — and the fix is a multiplier, not a better estimator.

The estimated-standard-deviation effect is smaller and is the one that can be fixed by spending. At 696 probes the sample standard deviation is known to about 3 per cent, so at the 1 per cent target the rule’s own precision about its own precision is not the issue; at 8 probes it is 27 per cent and it is. So the rule is worst calibrated exactly where it is cheapest, and the loose targets are the ones to distrust.

That ordering is the opposite of what intuition suggests. A tighter target sounds like a harder promise, and it is a more reliable one.

The cost of the target is the estimator’s own square root #

The probe counts are the other half of the table and they are the reason a trace is expensive.

Tightening the target from 3 per cent to 1 per cent — a factor of three — takes the median probe count from 75 to 696, a factor of 9.3. That is the estimator’s $1/\sqrt{t}$, exactly: three times the accuracy costs nine times the samples, and the rule is simply reporting it.

Nothing about the rule can improve that. The variance of a single probe is $2(\|A\|_F^2 - \sum a_{ii}^2)$ for a Rademacher probe, a fixed property of the matrix, and the mean of t of them has a variance of that over t. A stopping rule can only decide when to stop paying; it cannot change the price.

Which is what makes that measurement’s knob the one that matters. Deflation changes the variance itself, by removing the directions that contribute most of $\|A\|_F$, and the rule then stops sooner because there is less noise to average away. At a 1 per cent target with an eight-column sketch the median cost is 277 products against 696 — two and a half times cheaper, at a median error of 8.4·10⁻³ against 5.3·10⁻³.

The cost of finding this out was a bug #

The rule above costs 0.9 seconds to sweep over three targets, forty draws and two estimators. The first version cost fifty, and the difference was one line that is worth recording because every number it produced was correct.

The inner loop computed each probe’s quadratic form as

which calls apply once per component — sixty matrix–vector products per probe rather than one. The estimate, the probe count, the reported standard error and the achieved error are all identical either way, because the products are identical and only the count of them is wrong.

That is the shape of defect this field’s cost measurements are most exposed to. Every check in the file is about a value, the values were right, and the quantity that was wrong — the number of matrix–vector products — is the quantity this whole field is denominated in. A trace estimator is interesting because products are the currency, and a routine that spends sixty where it should spend one is reporting a cost that is off by the size of the matrix.

Nothing caught it. It was found by timing a figure, which is not a check and is not reliable — a slow figure on a busy machine looks the same as a wasteful one. The honest conclusion is that a products counter has to be a counter rather than an inference, and hutchPP has one for exactly that reason while the two stopping routines did not until this essay.

What the rule is measuring when there is a head #

Deflation introduces a subtlety in the rule that is worth stating because it is the kind of thing an implementation gets wrong silently.

Inside Hutch++ the estimate is head + tail, where the head is tr(QᵀAQ) computed exactly and only the tail is stochastic. So the standard error of the estimate is the standard error of the tail, and the relative standard error a rule should compare against a target is that divided by the whole estimate — not by the tail.

Dividing by the tail is the natural thing to write, because the tail is what the running sums are about, and it is wrong by exactly the ratio of the whole trace to the deflated one. On a fast-decaying spectrum the head is most of the trace, so the tail is small, so a rule dividing by the tail would demand a relative precision on the remainder far tighter than the target and would run for ever. The routine here divides by head + mean, which is the quantity the target is about.

That is why deflation makes the rule cheaper rather than merely faster per probe. Both effects are present: the tail has a smaller variance, and the denominator the target is measured against is larger than the tail.

That figure is the rule’s trivial case and it is worth looking at, because it is the one configuration where the rule’s two failure modes vanish together. On a diagonal matrix every Rademacher probe returns the trace exactly, so the sample standard deviation is zero, the standard error is zero, and the rule stops at the warm-up with a relative error of zero. Nothing about the rule notices that it has been handed an exact answer rather than a well-estimated one — and nothing needs to, because a reported standard error of zero is the truth.

The near-diagonal case is the one to be careful about. A matrix whose off-diagonal part is small but not zero has a small variance and a rule that stops at eight probes, and the sample standard deviation from eight probes of a small-variance quantity is the same 27 per cent uncertain as any other. So the rule’s confidence is misplaced by the same factor whatever the variance, which is the reassuring version of the finding: the calibration does not depend on the matrix.

Against the other stopping problem in this field #

A stopping test is a race set out the general difficulty: a test that stops whichever quantity reaches a threshold first has no opinion about whether it is the quantity that should have. This rule is a rare case where the difficulty does not arise, and the reason is worth naming.

The quantity the rule reads — the standard error of a mean of independent samples — is an estimate of the very quantity the user cares about, up to a distributional constant. It is not a residual standing in for an error, not a μ standing in for a distance, and not a norm standing in for an accuracy. That is why its median calibration is within a factor of two rather than off by orders of magnitude, and it is unusual enough in this field to be the point.

What replaces the difficulty is a distributional question rather than a proxy one: how many standard errors of margin a user wants. Multiplying the target by a half puts 95 per cent of draws inside where one puts 80, at four times the probes — which is the same $1/\sqrt{t}$ in a different currency, and is a choice the rule can offer rather than a defect it has.

What must fail for any of this to be wrong #

Four claims with refusals attached. That no run hits the probe cap at any target measured, which is what makes the medians medians rather than censored quantities. That the median error is of the target’s order. That the worst draw is outside the target — a claim that the estimated standard error bounds the error fails. And that tripling the target’s tightness costs between four and twenty times the probes, which is the $1/\sqrt{t}$ the estimator has and the rule does not change.

The probe stream is seeded per draw and both estimators see the same seed at the same target, so the comparison between them is over the same noise rather than over two samples of it.

What this does not settle #

One matrix family, three decays, one size. The rule reads only its samples, so it is indifferent to the spectrum by construction, but the cost of every target is a property of $\|A\|_F$ and nothing here maps the cost onto a spectrum.

Forty draws a cell, so “80 per cent inside” is 32 of 40 and the worst is the worst of forty. The share inside settles slowly — it is a binomial proportion at p near 0.75, whose standard error at n = 40 is 7 percentage points — so the differences between 70, 75 and 80 per cent in the table are not differences.

The warm-up is eight probes and is not swept. A longer warm-up would measure s better and stop later, and the trade between the two is the obvious parameter of the rule that this essay leaves fixed.

Rademacher probes throughout. The variance depends on which random vector is used, by a factor that is a property of the matrix, so the cost column would move under Gaussian probes and the calibration column should not.

What a budget and a target are for #

The field now has both, and they are not two ways of saying the same thing.

A budget is what a caller has. A trace inside a larger computation — a log-determinant inside a likelihood, a Hessian’s diagonal inside a step — is one term of many, and the sensible way to spend on it is a share of the whole rather than an accuracy, because the accuracy that matters is the outer computation’s and nobody can attribute it to the terms. Every earlier measurement here is budget-shaped for that reason.

A target is what a caller wants when the trace is the answer. A stated relative accuracy is the natural interface then, and the measurement says it can be delivered as a median rather than as a bound, at a cost the caller cannot know in advance — 8 probes or 696 at the two ends of a factor of ten in the target, on one matrix.

The pair is awkward, and the awkwardness is the practical content. A caller who states a target is writing a cheque against a quantity the estimator discovers: the matrix’s $\|A\|_F$ relative to its trace, which is the very thing the first of these essays identified as the estimator’s difficulty. So a rule with a target needs a cap, the cap is a budget, and a run that hits it has to report that it did rather than return its last estimate silently. The routine here caps at 2,000 probes and the sweep confirms that no run reaches it, which is how the medians in the table are known to be medians rather than the cap.

Still open: the margin, the warm-up, and a rule for the contour #

A rule with a margin. Multiplying the target by a constant to buy a share inside it is a one-parameter family and the sweep above measures one member. What constant puts 95 per cent of draws inside, and whether it is stable across decays and sizes, is one sweep and would turn a median guarantee into a stated confidence.

The warm-up. Eight probes is enough to stop at the 10 per cent target and is barely enough to estimate a standard deviation. Sweeping it would say whether the 10 per cent row’s poor calibration is the warm-up’s fault, and whether a rule that refused to stop before thirty probes is better calibrated at every target or merely dearer at the loose ones.

A rule inside the contour estimator. Counting what is inside a circle integrates a trace around a contour and its answer is an integer, so a stopping rule there could stop when the estimate is within half of an integer — a target with no tolerance to choose, which is a rarer and better shape of rule than this one has.

And whether the sample variance can be shared across targets. Every run here estimates s from scratch. A code estimating many traces of related operators could carry s from one to the next, which would fix the second failure mode above at the cost of an assumption nobody can check.