The test that is a deadline

An iteration that walks out of the set ends with a number. The logarithm of how much the largest rank-one term grew, over the logarithm of how much the error fell, reads 1.00 on the sequence that defines the border-rank infimum, 0.49 on a run of alternating least squares that is walking out of the rank-two set, and 0.0001 on a fit that is converging. Three regimes and one quantity, computed from two columns a trace already records — the habit an exact answer to a measured problem makes of measuring against something known rather than against a run.

What that essay does not do is use it. The number is computed over a whole run, after the run, on three runs chosen to be different from each other — which is a summary and not a test. A test has two properties a summary does not: what it fires on, and how long it takes to fire.

What it catches, and how early #

On the border-rank tensor — where there is no rank-two answer and the iteration is walking towards a limit outside the set — the test fires on all six runs, at a median of twenty-one sweeps out of a budget of four thousand.

Twenty-one sweeps is worth putting beside what the run would otherwise cost. The first essay on this ladder draws its swamp at two hundred, a thousand, five thousand, twenty thousand and forty thousand sweeps and reports that at every one of them the error is still falling and the terms are still growing — which is the correct diagnosis and takes forty thousand sweeps to reach with confidence. The window has it at twenty-one, and the remaining 3,979 sweeps of the budget buy nothing but the same verdict at greater length.

That is the result the quantity was proposed for and it is better than it needed to be. A run that would otherwise have been given four thousand sweeps, and would have spent them producing a curve that looks like slow convergence, is identified in twenty-one — a saving of a factor of nearly two hundred, on a diagnosis that no stopping rule in use computes.

On an ordinary rank-three fit it fires on none of six. Those runs finish in fifty-odd sweeps at an error of 10⁻¹⁴, their terms do not move at all, and the largest elasticity any window of them ever shows is 0.018 — two orders below the threshold.

So on the two cases the first essay draws, the test is clean.

And what it stops that it should not #

The two cases the first essay draws are not the two cases a test has to distinguish.

A plateau at a small residual has two causes and only one of them is a boundary, which is the same separation a small residual is not a small error makes one field over. The other is conditioning: each sweep of alternating least squares solves an r × r system whose matrix is the entrywise product of the other modes’ Gram matrices, and that matrix becomes singular as two terms line up. A fit whose factors are nearly parallel is solving a nearly singular system every sweep, and it converges — slowly, and to an answer that is there.

The badly conditioned run climbs first and then comes down. For its first several hundred sweeps it is shaped exactly like the boundary run — terms growing, error falling — and then it turns and finishes, reaching 4.02·10⁻¹² at sweep 3,388 with its terms back where they started.

The test fires on all six of those, at a median of 758 sweeps.

That is the cost nobody measured, and it is not a small one. A rule that stops a run when the elasticity crosses a threshold stops every one of these — six runs that had an answer and were on their way to it, discarded as boundaries at about a fifth of the way through.

The threshold does not separate them #

The obvious repair is to raise the threshold, and it does not work.

Raising the threshold delays detection and removes no false alarms. The boundary runs’ median firing sweep goes from 21 to 35 — a two-thirds increase in the cost of the diagnosis — and the convergent runs’ does not move at all, because they reach an elasticity of 0.49 and 1.37 and 17.7 eventually, and every threshold in the usable range is below those.

The reason is in the first essay’s own numbers. The border-rank sequence sits at an elasticity of 1.00 and the alternating run at 0.49, so a threshold above about 0.5 rules out the very thing the test is for; and a badly conditioned run passes through every value on its way up. There is no level that one crosses and the other does not.

What does separate them is the sweep #

The two columns of the table above are twenty-one against seven hundred and fifty-eight, at every threshold drawn. A factor of thirty-six, and it is stable.

That is the rule, and it is a different kind of rule from the one the quantity invites. It is not stop when the elasticity exceeds x. It is:

An elasticity above a quarter within the first fifty sweeps is a boundary. The same elasticity after several hundred is a badly conditioned fit, and it will converge.

The reason is mechanical rather than statistical. A boundary is what the iteration meets immediately: there is no rank-two point near the target, so the very first sweeps are already trading term size for error and the exchange rate is the geometry’s from the start. A badly conditioned fit has an answer, and its early sweeps make ordinary progress towards it — the terms grow only once the iterate is close enough for the nearly singular subproblem to matter, which takes hundreds of sweeps to arrive at.

So the quantity is the same and the clock is what says which regime produced it. That is worth stating plainly because the whole apparatus of a threshold test — tune the level, trade the two error rates, the shape a stopping test is a race prices — turns out to be the wrong apparatus. There is one level, and the axis to tune on is time.

The window, which is the one thing that has to be chosen #

A sliding window has a length and nothing above says where twenty came from, so it is worth saying what it does and what it costs.

The elasticity is a ratio of two logarithms of ratios, so it needs two readings far enough apart that both ratios are well above the noise in the trace. Too short a window divides two small numbers and produces a quantity that jumps about; too long a window delays every firing by its own length, since the earliest a window ending at sweep k can be evaluated is sweep k.

Twenty sweeps is chosen from that second constraint rather than the first: the boundary runs fire in the low twenties, and a window of twenty is the longest one that still allows a firing that early. A window of fifty would push the earliest possible detection to sweep fifty and would not change which runs fire, so the cost of a longer window is paid entirely in the quantity this page’s rule depends on — the clock.

That is a mild circularity and it is worth admitting: the window was chosen knowing where the boundary runs fire. A code that did not know would choose it from the other end — short enough that the diagnosis arrives before the run’s own budget is spent — which lands in the same place for a different reason, and the measurement above says any window from ten to fifty gives the same verdicts on the same eighteen runs.

The three quantities a run of this kind should record #

The measurements here and in the essay before them add up to a short list, and none of it is expensive.

The error, every sweep. Already recorded, since it is the stopping test.

The largest rank-one term, every sweep. A product of column norms — r terms, d factors each, a few hundred multiplications against a sweep that costs n^d·r. It is the column the first essay in this ladder found was missing, and it is the column the whole diagnosis is built on.

And the sweep number at which the elasticity first crosses a quarter. One number, computed from the other two, and it is the verdict.

A run that records all three can be classified after the fact without being re-run, which is the practical difference between this and the picture the first essay draws. That picture needs four thousand sweeps and a reader; this needs three columns and an arithmetic comparison, and it answers at sweep twenty-one.

The mild case is worth having on the page because it says the false alarms are not a property of the control family. At a cosine of 0.8 the fit behaves like an ordinary one, the elasticity never rises, and the test is silent — so what it is reacting to at 0.9 is the conditioning becoming severe rather than the factors being planted at all.

The case the rule does not cover #

There is a third regime and the deadline does not reach it, which is worth saying before the rule is taken as complete.

At a cosine of 0.99 the fit does not finish inside any budget drawn here. It has an answer — the tensor was built from three rank-one terms — and the iteration cannot reach it, and the elasticity after the first few hundred sweeps is negative, because the terms are coming down while the error falls.

So there are at least three shapes and the quantity reports two of them. A run whose terms shrink while its error crawls is neither a boundary nor a healthy fit; it is a fit whose subproblem is too ill-conditioned to make progress, and nothing here distinguishes it from a fit that is nearly done. The honest scope of the rule is: it identifies a boundary early, it does not identify a stall, and a code that wants both needs a second quantity — the conditioning of the subproblem, which is an r × r matrix, is free, and is what the decomposition’s own condition number is built from.

What this costs to compute #

Nothing, and that is the point of using the trace’s own columns.

The error is already computed every sweep — it is the stopping test. The largest term’s magnitude is a product of column norms, r of them, d factors each: a few hundred multiplications against a sweep that costs n^d·r. The window is twenty sweeps of stored pairs. The whole test is two logarithms and a division per sweep.

Against that, the diagnosis it replaces is run for four thousand sweeps and look at the picture, which is what the first essay in this ladder does and is what a practitioner does. A test at sweep twenty-one against a judgement at sweep four thousand is the entire argument for computing it.

Where this sits beside the field’s other stopping tests #

A stopping test is a race sets out the field’s standing position on these: a rule that reads a quantity the iteration already has, against a rule that reads a quantity it does not. This one is unusual in three ways and each is worth a line.

It is not a convergence test. It does not ask whether the run is close enough to stop — the question the reading that never moves is about — it asks whether the run is going anywhere. A code wants both, they fire on different quantities, and neither substitutes for the other.

It has no tolerance in it, unlike the rules two machines, one certificate has to reconcile. The threshold is not an accuracy and does not scale with the data — it is a dimensionless ratio of two logarithms, and the whole point of the first essay’s elasticity is that every scale divides out. So it needs no calibration to the problem, which is rare here and is what the tolerance that buys no agreement finds hardest to arrange.

And it fails in the safe direction only if the deadline is used. A threshold test fires late on a convergent run and stops it; a deadline test does not fire at all after its window has passed. The cost of the deadline is that a boundary met late — an iterate that wanders into a degenerate region after a thousand sweeps — is not caught, and whether that happens is not measured here.

The refusals #

The claim worth breaking is the one the first essay’s three numbers invite: a run whose terms grow while its error falls is at a boundary. It is true of the two runs that essay draws and false of a whole family it does not. The assertion that a crossing identifies a run with nothing to converge to is fed six fits to genuinely rank-three tensors — every one of which crosses, and one of which finishes at 4.02·10⁻¹² after 3,388 sweeps — and required to fail.

The second refusal covers the over-correction. Fed the six boundary runs, the claim that the test is useless because it has false alarms has to fail: it fires on all six, at sweep twenty-one, and on none of the six ordinary fits.

And the third is a control on the threshold, because the whole recommendation rests on the threshold not mattering. Fed the four thresholds from 0.10 to 0.40, the claim that raising the level reduces the false alarms is required to fail — it is six of six at every one of them, and all it buys is a later firing on the runs the test is for.

What the field already knew and did not join up #

Three measurements elsewhere in this collection are about the same pair of causes, and putting them beside each other is what makes the deadline a rule rather than a rule of thumb.

A nearest point that is not there is the geometry: for three indices the best rank-k approximation need not exist, so an iteration can approach an infimum it cannot attain, and it does so from the first sweep because the infimum is where the target’s nearest rank-k point would have been. A rank that is not a property of the tensor is why that is not a pathology — the rank-two tensors are not closed and a random one is rank two with probability exactly π/4, so a target near the boundary is an ordinary thing to be handed.

The conditioning half is the road that squares the problem arriving one field over: the subproblem is solved through its normal equations on purpose, the matrix being squared is r × r, and it becomes singular as two terms line up. That is a late effect, because the terms only line up once the iterate is near the answer.

The timing follows from which of the two it is. A boundary is a property of the target and is there at sweep one; a nearly singular subproblem is a property of the iterate and arrives when the iterate does. Nothing in the elasticity knows that, and the clock does — which is why the rule reads the sweep rather than the value, and why it is a rule about causes rather than a fitted threshold.

Still open: the deadline as a function of the problem #

Fifty sweeps is a number read off six runs on one tensor of one size, and the honest form of the rule needs it to be a function rather than a constant.

The boundary runs fire at sweep 21 because the exchange the geometry imposes starts at sweep one. The convergent ones fire at 758 because that is how long their iterate takes to get close enough for the subproblem’s conditioning to bite, which is a property of how nearly parallel the factors are and of the tensor’s size. A cosine of 0.8 would take fewer sweeps and a cosine of 0.95 more, so the gap between the two firing times is not fixed and could in principle close.

What would settle it is a sweep over the collinearity and the mode size, with the firing sweep of both kinds recorded — and the quantity to watch is not the ratio but whether the distributions overlap at any setting. If they do, the deadline has the same problem the threshold has, one axis over.

The second open question is the stall. A run whose terms shrink and whose error crawls is the third shape here and has no test. The conditioning of the r × r subproblem is computable every sweep and is the obvious candidate, and whether it separates a stall from a nearly-finished run — where it is also large — is the measurement this page does not make.

One line #

The quantity that tells a boundary from slow convergence is not a threshold to tune but a clock to read: the same value at sweep twenty means a run with nothing to reach, and at sweep seven hundred it means a badly conditioned fit that will finish.