A fit that has an answer and cannot stop

One term too many fitted a tensor built from three rank-one terms with four and found two of the four terms nearly parallel, subtracting each other, at an error of $10^{-13}$. It ended on a prediction for noisy data. If the cancelling pair is the fit’s way of moving a residual that is already at rounding level, then overfitting a tensor with noise in it should behave differently: the extra term would have real structure to find — the noise — and would be spent fitting it rather than pairing off, so the collinearity would be lower and less diagnostic. “That would mean the diagnostic is sharpest exactly where the model error is smallest, which is a convenient place for it to be sharp and is not where a practitioner works.”

The rank a sweep can vouch for needed the same fits for a different purpose and found them misbehaving in a way the prediction did not anticipate. Both halves can be measured on the same six planted rank-three tensors, six by six by six, at 0.1%, 1% and 3% relative noise.

The prediction, measured #

The four-term fits’ collinearity does not fall with noise. Its median over six tensors is 0.975 without noise, 0.992 at 0.1%, 0.977 at 1% and 0.997 at 3%, and the spread at every level runs from about 0.87 to 0.999. The three-term fits sit where they sat, at a median near 0.65, with one tensor whose own terms reach 0.96 at every level. The noise changes nothing about how the extra term arranges itself: it still pairs with one of the three.

So the prediction’s premise — that the pair was there to move a rounding-level residual — was the wrong reading of the noise-free case. With noise there is a residual of real size to fit, and the fit still spends its extra term on a near-cancelling pair. The pair is not a response to having nothing to fit; it is what a four-term decomposition of a tensor that is nearly rank three looks like, at the precision the fit can see.

What the extra term does fit #

The error says where the fourth term’s effort goes, and it says it with a number that can be predicted in advance.

A rank-one term in a six by six by six tensor has sixteen free parameters: six for each of three columns, less two for the scale that can move between them. The tensor has 216 entries. A least-squares fit with k terms that has captured all of the structure has only noise left to fit, and a generic fit absorbs noise in proportion to its parameters: it leaves $\sqrt{1 - 16k/216}$ of the noise behind. At three terms that is 0.882, at four 0.839, at five 0.793. The medians measured over eighteen noisy fits are 0.885, 0.833 and 0.781.

The three-term fit takes exactly its share; the four-term fit takes its share and a hair more; the five-term fit a little more again. An overfitted term, in other words, fits noise the way any sixteen parameters would, and in doing so it moves the error by a factor of 0.951 — which is the fact the rank-sweep essay turned into a rule that needs no noise level. The same count governs the dimensions a regularised solve admits past what the data carry: every direction added beyond the signal buys its share of the noise and nothing else.

The reason a count of parameters predicts it is geometric. Near its answer, a fit with $p$ free parameters can move only within a $p$-dimensional set of tensors, and a least-squares fit takes the part of the residual that lies along that set. Noise that is Gaussian and has no preferred direction puts, on average, a share $p/N$ of its energy along any $p$-dimensional set of the $N = 216$ entries, so the fit removes that share and leaves the square root of the rest in the error’s norm. Nothing in the argument knows which terms are the true three: the fourth is sixteen more dimensions of the same kind, and it takes sixteen dimensions’ worth of noise. That is why the measured four-term share sits on the prediction to within a per cent, and why the five-term share does too.

The argument has one assumption the measurement tests rather than grants: that the fit’s set of tensors is locally a smooth thing of dimension $p$ where it sits. A near-cancelling pair is close to a place where two terms can merge and the set folds, and there the local dimension a fit can use is not a plain count. The measured share is a hair larger than predicted at four and five terms, not smaller, which is the direction a fold that gave the fit a little extra room would push it.

That share is small, and the collinearity measured above says the term does not come cheap in another way: to take its twentieth of the noise it has to be arranged against another term, and the arrangement is degenerate.

The fit that cannot stop #

Without noise the four-term fit reaches an error of $2.5 \times 10^{-14}$ and stops at sweep 49, its largest term 0.670 of the data’s size. With 1% noise the same fit, from the same start, begins the same way: an error of 0.27 after one sweep, 0.015 after five, 0.0085 after ten, its largest term settling at 0.672 by sweep five. By sweep 20 the error is within 0.3% of where it will be at sweep 6,000. And then it keeps going. After sweep 1,000 its error changes by a median of $4.6 \times 10^{-7}$ of itself per sweep, nine orders above the $10^{-16}$ at which the stopping test fires, and from sweep 500 to 6,000 it moves by 0.26% in all. None of the eighteen noisy four-term fits stops within 6,000 sweeps. The rank-sweep essay capped them at 1,500 and spent 45,000 sweeps at rank four at 1% noise — every fit to its cap — against 4,300 at rank three.

The dial on the figure moves the noise, and the crawl moves with it. At 0.1% the median change per sweep after sweep 1,000 is below $2 \times 10^{-8}$ on all six tensors; at 1% it is between $10^{-7}$ and $4 \times 10^{-6}$; at 3%, between $10^{-7}$ and $4 \times 10^{-6}$ again but with the error moving by 1.4% to 2.7% over the long run on five of six. The rate grows faster than the noise does — seventyfold from 0.1% to 1% on the tensor drawn — which is what a fit would do if what it were sliding along were built out of the noise itself. Without noise there is nothing to slide along and the fit stops.

It is tempting to call this the swamp that the first essay on alternating least squares described: a plateau at a small error while the terms grow without bound, because the target’s nearest point of that rank does not exist. On most of these fits it is not that. Between sweep 500 and sweep 6,000 the largest term of fourteen of the eighteen moves by less than 0.03 of the data’s size. Two at 3% noise shrink — from 0.77 to 0.64, and from 0.74 to 0.65 — and one at 1% grows by 0.05. And one, the third tensor at 1%, does what a swamp does: its largest term climbs from 0.81 to 0.97 while its error falls by 5.2%, the most of any run. The crawl is not one shape. It is a fit whose terms can drift in any direction along which the error hardly changes, and the direction is set by the tensor, not by the method.

It is the third shape the test that is a deadline named and left without a test: “a run whose terms shrink and whose error crawls.” Its terms shrink on two runs, stand still on fourteen and grow on two, and its error crawls on all eighteen. It is a fit that has an answer, in the sense that it has reached the error of its answer, and whose terms are still sliding along a direction in which the error barely changes: the near-cancelling pair can rotate against each other at almost no cost, and the fit has no reason to stop anywhere in particular along that rotation. A stopping test that asks for the error to stop changing in its sixteenth digit is a test for a fit with a unique minimiser, and this fit’s minimiser is a long, nearly flat valley. A stopping test is a race described the test as a race between the error’s progress and the threshold; here the error has won the race by sweep 20 and the threshold never finishes.

Where the error settles #

That has a practical consequence the crawl hides. What a rank decision reads from a fit is its error. What the stopping test waits for is its terms. They settle at very different times.

Across eighteen noisy four-term fits, the error is within 5% of where it will be at sweep 6,000 by sweep 5 to 133 on seventeen of them, and by sweep 945 on the last — the tensor whose terms grow. Within 1% is slower. At 0.1% and 1% noise eleven of twelve get there by sweep 150, the twelfth at 2,666; at 3% five of six take between 640 and 3,700 sweeps, because the crawl itself is worth one or two per cent there over thousands of sweeps. The ratio rule for the rank needs the error only to within a few per cent, since it separates a factor near 0.95 from a factor of seven or more; the fits could be stopped by sweep 150 with the decision already made.

So the cost the rank sweep paid at the rank past the answer was a cost of the wrong stopping test. A fit whose error is all a decision needs can stop when its error stops moving by more than the decision’s own tolerance, and at that tolerance these fits stop within a few hundred sweeps. What they cannot provide at any number of sweeps is a unique set of terms, and a procedure that needs those — the agreement rule of the rank-sweep essay — needs them from fits that will never finish.

Against the noise-free case #

Set beside the one-term-too-many essay’s own figure, the noisy measurements change one conclusion and keep the rest. The collinearity of an overfit is as high with noise as without, and on one tensor at a time it is as good a sign that a term is spare. What it is not is a threshold that works across tensors, since a tensor whose own terms are nearly parallel reads as overfit at its true rank; the rank-sweep essay measured that. The residual says nothing about the spare term with noise or without, except through its ratio to the rank below. And the new fact is the solver’s: without noise a spare term costs nothing to fit, and with noise it costs as many sweeps as the cap allows.

The figure puts the difference in one pair of numbers. Without noise, thirty four-term fits — six tensors, five starts — take 4,434 sweeps between them, about 150 each, which is what the three-term fits take too. At 0.1% noise the same thirty take 45,000, every one to its cap of 1,500, and they do the same at 1% and at 3%. The cost does not rise with the noise; it switches on. A thousandth of the data’s size in noise is already enough to turn a fit that finds its cancelling pair and stops into one that finds it and keeps sliding, and above that the cap is the only thing that ends the run. The rank-three fits, meanwhile, cost no more than 2,500 sweeps a tensor over five starts at any level, with or without noise: the answer’s own rank is indifferent to the noise, and the rank past it is not.

That last fact is the one a practitioner meets first, because it is the one that shows up as time. A decomposition routine asked for one term too many on real data returns late, and returns whatever terms it had when its cap arrived. Those terms fit the data as well as any four-term fit can — within a per cent of the best — and are one arbitrary point of a valley of equally good fits. Nothing in the returned error distinguishes them from a meaningful answer; the collinearity of two of them does, and so does the fact that it took the cap to return them.

What a routine asked for too many terms should say #

Three things follow for software that fits these decompositions, and none of them needs a new algorithm.

The first is that a fit which runs to its cap is information, not failure. Every noisy four-term fit here ran to the cap and every three-term fit stopped but one start on one tensor, which runs to its cap with or without noise and so says something about that start rather than about the rank. Under noise, the fits that ran out of sweeps were the ones asked for a term the data did not have. A routine that reports “did not converge” as a warning to be silenced throws away the cheapest rank diagnostic it has.

The second is that the answer returned at the cap is good for the error and for nothing else. The error was within 5% of its long-run value by sweep 150 on seventeen of eighteen runs, so a comparison of errors between ranks — the ratio rule — can be made from fits stopped long before the cap. The terms returned are one point on the valley, and on the run whose terms grew they are a different point at every cap.

The third is that the collinearity of the returned terms should travel with them. It costs one inner product per pair of terms, it read above 0.84 on every noisy four-term fit measured, long or short, and it is the only number in the output that distinguishes a spare term from a real one without a second fit. As the rank-sweep essay measured, it cannot be a fixed threshold across tensors; beside the error ratio from the rank below, it is the second witness.

What this does not settle #

Six tensors of one size and rank, with Gaussian factors and Gaussian noise, one start per long run and five per rank in the sweep. The parameter-share law is a statement about generic least-squares fits and is borne out here at ranks three to five; a tensor with structure near the noise level would have a term whose gain sits between the two regimes, and none is measured.

The explanation of the crawl — a nearly flat valley along which the cancelling pair can rotate — is an argument from the measurements, the constant term sizes and the tiny constant rate, not a measurement of the valley itself. The Hessian of the fit along the pair’s rotation would test it and is not computed.

Whether the valley is exactly flat or only nearly so is not settled either. A fit that crawled for a million sweeps and then stopped would be a slow convergence, not a flat valley, and the 6,000 sweeps drawn cannot tell the two apart.

Still open: a stopping test for the decision, and the valley’s floor #

A test stated in the decision’s tolerance. The stopping test here asks for sixteen digits of stillness in the error. A test that asked instead for the error to be still to within the tolerance of the decision the fit serves — a few per cent for a rank, less for a model comparison — would stop these fits within a few hundred sweeps. Whether such a test can be stated without knowing the decision in advance, perhaps as a change per sweep compared with the parameter share of the noise, is the question that would remove the cost measured here.

Whether the valley has a floor. The four-term fits crawl at a relative rate near $10^{-7}$ a sweep. If that rate is constant the fit never stops; if it decays, it stops eventually and the crawl is slow convergence. A run long enough to see the rate change, and the curvature of the error along the rotation of the cancelling pair, would say which — and would say whether a ridge of the kind the repair that costs exactly itself measured on swamps turns the valley into a point.