Numerical Linear Algebra
where the algebra stops being the arithmetic
When the index is a tuple

A still error is not a settled one

A CP fit with one term too many on a noisy tensor never meets the usual stopping test, and its error has settled by sweep 150. A test that asks only whether the error has moved by less than δ of itself over ten sweeps stops those fits by sweep 25, and over twenty-four noisy tensors it names the same rank as the usual test every time, at δ = 10⁻² for 30,250 sweeps against 311,458. But δ = 10⁻² is the tolerance a rank decision states, and on a slow fit that converges it stops five starts of six on a plateau ten orders above the answer and names the wrong rank for four tensors of six. A tenth of the decision's tolerance keeps every decision on both families.
20 min read 5 figures Measured, not assumedWhose fault is itClaims that can fail

Worth reading first: An iteration that walks out of the set · A parameter that counts steps.

Alternating least squares fits a tensor with a sum of rank-one terms by solving for one factor at a time, and every sweep lowers the error. An iteration that walks out of the set showed that it can lower it forever without arriving, when the nearest point of that rank does not exist. The test that is a deadline looked for a quantity that separates that swamp from slow convergence and found one that fires on both, at very different sweeps. The rank a sweep can vouch for decided a tensor’s rank by fitting at one rank after another and found that the simplest rule — stop at the first rank past which one more term improves the error by less than a fifth — was right on all twenty-four tensors it was given.

Then a fit that has an answer and cannot stop found where that rule’s cost goes. Fitted with one term too many, a noisy tensor produces a fit whose error is within five per cent of its final value by sweep 150 and which never meets the usual stopping test: that test waits for the error to stop changing in its sixteenth digit, and the fit’s near-cancelling pair of terms slides along a nearly flat valley for thousands of sweeps, moving the error by parts in a million. The rank sweep capped those fits at 1,500 sweeps and spent most of its budget there.

That essay’s open question was whether a test stated in the tolerance of the decision the fit serves — a few per cent for a rank — could stop those fits early without knowing the decision in advance. The obvious test reads only the error: stop when the error has fallen by less than δ of itself over the last ten sweeps. This essay measures it on the fits it was proposed for, and on a second family it was not: fits that have an answer, reach it, and are merely slow getting there.

The test works on the first family at any tolerance. On the second it cannot tell a plateau from a floor, and at the tolerance a rank decision would state it gives the wrong rank.

The window test

At sweep s the test compares the error with its value ten sweeps earlier. If the fall is less than δ times the current error, the fit stops. It needs no parameter but δ and the window, and it reads nothing the iteration does not already compute.

Because it reads only past errors, it can be applied to a run already made: the run the test would have made is the stored run cut off at the sweep where the test fires. Every measurement below does exactly that, on runs made with the usual test — whose stored traces are the runs the window test would have produced up to its own stopping sweep.

Four tolerances are measured: 10−210^{-2}, the few per cent a rank decision needs; 10−310^{-3}; 10−410^{-4}; and 10−510^{-5}. The window is ten sweeps throughout.

On the fits it was proposed for

A four-term fit to a rank-three tensor with 1% noise: its error against the sweep, and where a test in the decision's tolerance stops itOn logarithmic axes, the relative error of one alternating fit run for 6,000 sweeps, where the usual test never fires. The window test stops at the first sweep at which the error has fallen by less than δ of itself over the last ten sweeps: δ = 0.01 at sweep 19, error 0.00851, 0.29% above the error at sweep 6,000; δ = 0.001 at sweep 21, error 0.00851, 0.29% above the error at sweep 6,000; δ = 10⁻⁴ at sweep 22, error 0.00851, 0.29% above the error at sweep 6,000; δ = 10⁻⁵ at sweep 25, error 0.00851, 0.29% above the error at sweep 6,000. The error at sweep 6,000 is 0.008485.the window testδ = 0.01: stops at sweep19δ = 0.001: stops at sweep21δ = 10⁻⁴: stops at sweep22δ = 10⁻⁵: stops at sweep25110¹10²10³10⁻²10⁻¹sweeprelative errorall four stops, sweeps 19, 21, 22, 25the usual test never fires on this runten sweeps, and a tolerance the decision can state
Fig. 1 One planted rank-three tensor with 1% noise, fitted with four terms for 6,000 sweeps, where the usual test never fires: the relative error against the sweep on logarithmic axes, with the sweep at which the window test stops it marked for each of four tolerances. The dial changes the noise.

The four-term fit at 1% noise falls from an error of 0.27 after one sweep to 0.0085 by sweep ten, and then barely moves. The window test stops it at sweep 19 with δ = 10−210^{-2}, at 21 with 10−310^{-3}, 22 with 10−410^{-4} and 25 with 10−510^{-5}. The four stops are within six sweeps of one another, because the error’s fall ends abruptly: by sweep 25 it is falling by less than a part in a hundred thousand per ten sweeps, and every tolerance measured is met within a few sweeps of the others.

The dial shows the same thing at the other two noise levels, with one exception that is worth noticing. At 0.1% noise the four tolerances stop the fit between sweeps 22 and 27, at an error four thousandths of a per cent above the error at sweep 6,000. At 3% the three loosest stop it between sweeps 18 and 22, 2.3% above; the tightest, 10−510^{-5}, does not stop it until sweep 5,914. At that noise level the crawl along the valley is itself fast enough to move the error by more than a part in a hundred thousand every ten sweeps — which is the 2.3% the other three leave behind, spread over six thousand sweeps. A tight enough window test is the usual test again, and at 3% noise 10−510^{-5} is tight enough.

That is the behaviour the previous essay predicted from the settling times, and it holds across the whole rank study: six planted rank-three tensors at four noise levels from none to 3%, each fitted at ranks two to five from five starting points, the rank named by the ratio of consecutive errors.

Sweeps spent deciding the rank of twenty-four noisy tensors, with the usual stopping test and with a test in the decision's toleranceSix planted rank-three tensors at four noise levels from none to 3%, each fitted at ranks two to five from five starts, and the rank named by the ratio of consecutive errors. the usual test, capped at 1,500: 311,458 sweeps, 24 of 24 right; window test, δ = 0.01: 30,250 sweeps, 24 of 24 right; window test, δ = 0.001: 36,475 sweeps, 24 of 24 right; window test, δ = 10⁻⁴: 69,261 sweeps, 24 of 24 right; window test, δ = 10⁻⁵: 150,591 sweeps, 24 of 24 right. At every δ the error at the stopping sweep is within 8.5% of the usual test's.the usual test, capped at 1,500311,458window test, δ = 0.0130,250window test, δ = 0.00136,475window test, δ = 10⁻⁴69,261window test, δ = 10⁻⁵150,59124 of 24 right24 of 24 right24 of 24 right24 of 24 right24 of 24 rightevery rank named is threea tenth of the sweeps at the loosest tolerance
Fig. 2 Sweeps spent over the whole rank study — twenty-four tensors, four ranks each, five starts at each rank — with the usual stopping test capped at 1,500 sweeps and with the window test at four tolerances, and how many of the twenty-four tensors each names rank three.

The usual test spends 311,458 sweeps and names rank three on all twenty-four. The window test names rank three on all twenty-four at every tolerance, and spends 30,250 sweeps at 10−210^{-2}, 36,475 at 10−310^{-3}, 69,261 at 10−410^{-4} and 150,591 at 10−510^{-5}. The loosest tolerance costs under a tenth of the usual test; the tightest costs half.

And the errors it stops at are close to the ones the usual test reaches. Over every tensor, rank and tolerance the best start’s error at the window test’s stop is at most 8.5% above the usual test’s, and the rule it feeds only needs to tell a factor near 0.95 from a factor of seven or more. On the noisy tensors the savings are almost all at ranks four and five, where the usual test runs to its cap: a noisy tensor that cost the usual test around fifteen thousand sweeps costs the window test at 10−210^{-2} between four hundred and sixteen hundred. On the noise-free tensors, whose fits converge to rounding and then stop, the window test saves between a tenth and two fifths.

So far the proposal looks finished: state the test in the decision’s tolerance, and the fits that could not stop do.

On a fit that is slow and does finish

The test that is a deadline kept a second kind of hard fit beside the swamp: a genuinely rank-three tensor whose factor columns lean towards one another, so that the small system each sweep solves is badly conditioned. Alternating least squares on such a tensor sits on a plateau for hundreds or thousands of sweeps and then converges, and that essay’s elasticity test fired on every one of them at sweep 758 — mistaking slowness for a boundary.

The window test has the same problem in a sharper form.

A rank-three fit to a noise-free rank-three tensor whose factors lean together at cosine 0.9: its error against the sweep, and where the window test stops itOn logarithmic axes, start 1 of six, every tenth sweep drawn. The run reaches 2.78·10⁻¹³ after 3456 sweeps. δ = 0.01 stops it at sweep 25, error 0.00986; δ = 0.001 stops it at sweep 41, error 0.00983; δ = 10⁻⁴ stops it at sweep 3444, error 2.59·10⁻¹³; δ = 10⁻⁵ stops it at sweep 3444, error 2.59·10⁻¹³.start 1, errorreaches2.8·10⁻¹³stopped by δ = 0.010.0099stopped by δ = 0.0010.0098stopped by δ = 10⁻⁴2.6·10⁻¹³110¹10²10³10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²sweeprelative errorδ = 0.01δ = 0.001δ = 10⁻⁴δ = 10⁻⁵a plateau is a still errorand a still error is what the test asks for
Fig. 3 A noise-free rank-three tensor whose factor columns lean together at cosine 0.9, fitted at rank three: the error against the sweep on logarithmic axes, every tenth sweep drawn, with the window test’s stop marked for each tolerance. It is the first of six starting points; the next figure gathers all six, beside six more on a tensor with flatter plateaus.

From the first starting point the error falls to about 10−210^{-2} within twenty sweeps, sits there until about sweep 300, steps down near sweep 500, and then falls ten orders over the next three thousand sweeps to 2.8×10−132.8 \times 10^{-13} at sweep 3,456. The window test at 10−210^{-2} stops it at sweep 25 with an error of 9.9×10−39.9 \times 10^{-3}; at 10−310^{-3}, at sweep 41 with 9.8×10−39.8 \times 10^{-3}. Only at 10−410^{-4} does it wait for the answer, stopping at sweep 3,444 at 2.6×10−132.6 \times 10^{-13}.

On a plateau the error is still. The window test asks whether the error is still, and has no way of asking whether it will stay still. What made the noisy overfit safe to stop — its error had reached the value it would keep — is exactly what a plateau imitates.

Where the window test stops twelve slow fits that converge, as a multiple of the error each run reaches, for four tolerancesSix starts on each of two noise-free rank-three tensors whose factors lean together at cosines 0.9 and 0.99, fitted at rank three. On a logarithmic axis, the error at the stopping sweep over the error the run reaches by its end (at most 6,000 sweeps). Cosine 0.9: stopped more than ten times above it by δ = 0.01 on 5, δ = 0.001 on 2, δ = 10⁻⁴ on 0, δ = 10⁻⁵ on 0. Cosine 0.99: stopped more than ten times above it by δ = 0.01 on 3, δ = 0.001 on 3, δ = 10⁻⁴ on 1, δ = 10⁻⁵ on 0.110²10⁴10⁶10⁸10¹⁰the decision's tolerancestopped error ÷ error reached0.010.00110⁻⁴10⁻⁵cosine 0.9cosine 0.99a point at the bottom stopped where the run endsa point at the top stopped on a plateau
Fig. 4 Twelve slow fits — six starts on each of two noise-free rank-three tensors whose factors lean together at cosines 0.9 and 0.99 — with the error at the window test’s stop as a multiple of the error the run reaches by its end, for each tolerance, on a logarithmic axis.

At cosine 0.9 the window test at 10−210^{-2} stops five starts of six on the plateau, at errors between 6×1076 \times 10^{7} and 4×10104 \times 10^{10} times the answer each run goes on to reach. At 10−310^{-3} it still stops two of six there. At 10−410^{-4} and 10−510^{-5} it stops none early: every start runs to its answer. At cosine 0.99 the fits are slower still and none has converged by sweep 6,000, so the multiple is against an error that is itself not the answer; even so, the loosest tolerance stops all six at between two and twenty-two times the error they reach, and 10−410^{-4} stops two of them early.

That is the claim this essay refuses: that an error which has stopped moving by a per cent over ten sweeps is within a tenth of where the fit will end. On the noisy overfits it is, by construction of the valley they crawl along. On the slow fits it is wrong by ten orders of magnitude.

Whether the rank survives it

A single stopped start is not a rank decision. The rank sweep takes the best of five starts at each rank, and if any start escapes its plateau before the window test fires, the best of five is right. So the question that matters is whether the rank named changes.

The rank the error-ratio rule names for six slow noise-free rank-three tensors, with the usual stopping test and with the window test at four tolerancesSix planted rank-three tensors whose factor columns lean together at cosine 0.9, fitted at ranks two to five from five starts, each run to at most 6,000 sweeps. Usual test: ranks 3, 3, 3, 3, 5, 3, 586,347 sweeps; δ = 0.01: ranks 4, 4, 3, 4, 5, 5, 72,402 sweeps; δ = 0.001: ranks 3, 3, 3, 3, 5, 3, 290,226 sweeps; δ = 10⁻⁴: ranks 3, 3, 3, 3, 5, 3, 479,432 sweeps; δ = 10⁻⁵: ranks 3, 3, 3, 3, 5, 3, 524,630 sweeps.rank named, with the sweeps spentusualδ 0.01δ 0.001δ 10⁻⁴δ 10⁻⁵tensor 13 · 109k4 · 19k3 · 49k3 · 78k3 · 87ktensor 23 · 83k4 · 7k3 · 42k3 · 70k3 · 71ktensor 33 · 87k3 · 12k3 · 47k3 · 73k3 · 78ktensor 43 · 90k4 · 16k3 · 67k3 · 84k3 · 84ktensor 55 · 104k5 · 16k5 · 53k5 · 83k5 · 96ktensor 63 · 113k5 · 2k3 · 33k3 · 92k3 · 108keach cell: the rank named · thousands of sweepsthe loosest tolerance changes four answers
Fig. 5 Six noise-free rank-three tensors whose factor columns lean together at cosine 0.9, each fitted at ranks two to five from five starts, run to at most 6,000 sweeps. In each cell, the rank the error-ratio rule names and the thousands of sweeps spent, with the usual test and with the window test at four tolerances.

With the usual test the rule names rank three on five of the six. On the fifth, even 6,000 sweeps do not bring the rank-three fits below 3.6×10−73.6 \times 10^{-7}, while rank five reaches 2.3×10−112.3 \times 10^{-11}, and the rule names five — a failure of the sweep budget rather than of the rule, and one that every tolerance of the window test repeats.

With the window test at 10−210^{-2} the rule names rank three on one tensor of six. On three it names four and on two it names five. On the first tensor the five rank-three starts are stopped with a best error of 2.0×10−32.0 \times 10^{-3}, while a rank-four start escapes its plateau and reaches 1.1×10−111.1 \times 10^{-11}; the ratio of the two says a fourth term improves the fit by a factor of two hundred million, and the rule believes it. The fourth term is not fitting structure. It is fitting the time the rank-three starts were not given.

At 10−310^{-3} the rule names what the usual test names on all six tensors, although single starts are still stopped on plateaus: the best of five is enough to carry one start past it at each rank. At 10−410^{-4} and 10−510^{-5} it names the same again. The sweeps tell the rest: the usual test spends 586,347 over the six tensors, the window test at 10−210^{-2} spends 72,402 and gets four wrong, at 10−310^{-3} it spends 290,226 and gets none wrong, and at 10−410^{-4} 479,432.

A tenth of the decision’s tolerance

Put the two families side by side. On the noisy overfits every tolerance measured keeps every decision, and the loosest saves a factor of ten. On the slow fits the loosest changes four decisions of six, and a tolerance ten times tighter keeps all of them while still halving the cost. The tolerance that serves both is 10−310^{-3}: it keeps all thirty decisions, costs 36,475 sweeps against 311,458 on the noisy family and 290,226 against 586,347 on the slow one.

So the test can be stated without knowing the decision in advance, which was the open question, but not in the decision’s tolerance. The decision needs the error to a few per cent. The stopping test needs δ a factor of ten below that, and the factor is not about the decision’s accuracy at all. It is the depth of the plateaus: a slow fit’s error on its plateau falls by between a part in ten thousand and a part in a thousand over ten sweeps, and a δ above that stops it there.

There is nothing universal in the number ten. It is what these plateaus measure, on these tensors, at this window. A flatter plateau — more nearly parallel factors — would need a smaller δ, and at cosine 0.99 even 10−410^{-4} stopped two starts early. What the measurement establishes is the direction: a window test tuned to the tolerance of the decision is tuned to the wrong thing, and needs a margin set by the slowest fit the procedure will meet.

What the window cannot see, and what could

The window test fails on slow fits because it looks only at how much the error moved. A stopping test is a race described a stopping test as a race between the iteration’s progress and a threshold, and a tolerance that reads its own residual found inexact Newton’s forcing rule doing better by reading the ratio of successive residuals than by reading any single one. Something similar is available here and is not measured: a plateau is not only still, it is still while the fit’s terms are growing towards each other, and the collinearity of the terms, which one term too many used to see a degenerate fit, rises on a plateau and falls when the fit leaves it.

A different route changes the fit rather than the test. The repair that costs exactly itself put a ridge on every subproblem and found that it stopped a swamp’s terms from growing and brought a run that never finished to an end in 798 sweeps, at a cost in error equal to the ridge. A plateau is a badly conditioned subproblem as much as a swamp is, and a ridge may shorten it; whether it shortens it enough to change what the window test sees is not measured here.

A second route costs more and needs nothing new. The rank sweep already runs five starts at each rank. A window test that stops a start only when two starts at the same rank agree on the error — the agreement that the rank-sweep essay found never wrong when it could decide — would refuse to stop a lone start on a plateau while its neighbours are below it.

What this rests on

Planted rank-three tensors of size 6×6×66 \times 6 \times 6: six with Gaussian noise at 0.1%, 1% and 3% and without noise, and six without noise whose factor columns lean together at cosine 0.9, with a second family at 0.99 for the single-fit measurements. Alternating least squares with a ridge of 10−1410^{-14}, five starts per rank, the usual test at a relative change of 10−1610^{-16} capped at 1,500 sweeps for the noisy study and 6,000 for the slow one. A window of ten sweeps and four tolerances; other windows are not measured. The window test’s runs are the usual test’s stored runs cut at the window test’s stop, which is exactly what the window test would have produced.

The claim that has to fail

The claim is that an error which has fallen by less than a per cent of itself over ten sweeps is within a tenth of where the fit will end. On the slow tensor at cosine 0.9, five of six starts are stopped at errors near 10−210^{-2} that go on to reach 10−1010^{-10} to 10−1310^{-13}. The refusal is fed the claim that every start stops within a tenth of its final error, and fails.

Still open: plateaus the window can recognise, and the depth of a plateau

A window that also reads the terms. The collinearity of the fitted terms rises on a plateau and falls when the fit escapes it, while on a noisy overfit it is high and stays high. A test that stops only when the error is still and the collinearity is not changing would separate the two families on this evidence, and whether it keeps every decision at 10−210^{-2} is one pass over the same stored traces.

Agreement among starts as the stopping signal. Stopping a start only when another start at the same rank has reached the same error would prevent a lone start from being stopped on a plateau. Its cost is the waiting of the fastest start for the second fastest, and whether that is less than the tenfold tightening measured here is not known.

How deep a plateau can be. The factor of ten between the decision’s tolerance and the test’s is the fall of the error across ten sweeps of a plateau at cosine 0.9. At 0.99 the plateaus are flatter and 10−410^{-4} was not enough. Measuring that fall against the cosine of the factors would say how the margin has to grow as the tensor becomes harder, and whether any fixed δ can serve a procedure that does not know how nearly parallel its answer’s terms are.

Where this goes next

no noisesweeps to stop49final error2.5·10⁻¹⁴1% noisesweeps to stop6000largest term, ÷ data0.67110¹10²10³10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1sweeprelative change in the error, per sweepthe stopping test1% noiseno noise: stops at 10⁻¹⁴the clean run stops; the noisy one crawlsits terms stay the size they were A fit that has an answer and cannot stop Fit a noisy rank-three tensor with four terms and the prediction was that the spare term would find real structure in the noise and stop pairing off with the others. It does not: the largest cosine between two fitted terms has a median of 0.977 at 1% noise against 0.975 without noise. What changes is the solver. Without noise the four-term fit stops in fifty sweeps; with noise it never stops: its error keeps moving by a part in a million a sweep for six thousand sweeps, while on most tensors its terms stand still. The extra term takes exactly its share of the noise, and the error is settled by sweep 150. 01210¹10²10³the three kinds of runsweep at which the test firesno answer to reachbadly conditionedordinaryhollow: never fired, drawn where the run endedwhat it fires on, and whenthreshold0.25boundary, fired6boundary, median sweep22collinear, fired6collinear, median sweep759ordinary, fired0the value does not separate themand the sweep does The test that is a deadline The quantity that separates a boundary from slow convergence fires on every run that has nothing to reach, at sweep 21 of four thousand, and on no ordinary fit. It also fires on every badly conditioned fit that does converge — at sweep 758. No threshold between 0.10 and 0.40 separates those two, and the sweep it fires at separates them by a factor of thirty-six. at rank threelowest across tensors1highest across tensors1at rank fourlowest across tensors0.056highest across tensors0.25234500.20.40.60.81rank fittedagreement among the starts that reach itsix planted tensorsdashed: the true rankeach line one tensor, fitted at ranks two to fivefive starting points at every rank The rank a sweep can vouch for To decide a tensor's rank, fit it at one rank after another and stop where something changes. Three things can be read off each rank's fits — the error, how nearly parallel the terms are, and whether fits from different starting points agree — and over six planted rank-three tensors at four noise levels they decide it 24, 12 and 15 times out of 24; the ratio of consecutive errors, which needs nothing, decides it 24 times. The error is right every time and has to be told the noise level. The collinearity is a coin toss. Agreement among starts is never wrong and, under noise, cannot decide on nine of the twenty-four — and the rank past the answer, where every decision is made, costs ten times the answer.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Alternating least-squaresConvergence rateCP decompositionDegeneracyStopping criterionSwampTensor rank