The iteration pays the square

Unique, and not determined took a 4 × 4 × 4 tensor of rank three and turned two columns of its third factor toward each other, to an angle $\theta$ from one radian down to $10^{-3}$. Kruskal’s condition kept saying the decomposition was unique at every angle above zero — k-ranks 3, 3 and 3, one to spare — while the Jacobian of the map from factors to tensor lost its smallest singular value in proportion to $\theta$, and the exact decomposition of a tensor perturbed by one part in $10^8$ moved by 1.6 parts at $\theta = 0.1$ and by 200 at $10^{-3}$. Alternating least squares, started at the exact factors, slowed as the angle closed and then stopped on its own test, hundreds of perturbations short of where the decomposition had moved. The essay ended on how long it would have needed.

“The sweeps to reach the moved decomposition rose from about thirty at $\theta = 1$ to several hundred at 0.1. The prediction with a sign is that they grow like $1/\theta^2$ — the square of the decomposition’s condition, as for any iteration whose contraction is set by the ratio of a Gram matrix’s extreme eigenvalues — so that at $\theta = 0.01$ ALS from the exact start needs between twenty and a hundred thousand sweeps, and a cap of three thousand misses by more than a factor of five.”

The prediction holds, on every count. What the measurement adds is where each factor of the count comes from — the distance and the rate are both set by the angle, in different powers — and a reason no stopping test that reads the residual can see the arrival coming.

Running without a stop #

The tensors are the earlier essay’s: three random choices of the three 4 × 3 factors, the third factor’s third column turned to $\theta$ from its first, perturbed by a random tensor scaled to $10^{-8}$ of the whole. The moved decomposition — the exact decomposition of the perturbed tensor — is found by Gauss–Newton from the exact factors, which converges in a few steps however small the angle, because it uses the Jacobian the angle makes ill conditioned rather than suffering from it. Alternating least squares then starts at the exact factors and runs with no stopping test and no ridge on its subproblems, and every few sweeps the distance from the moved decomposition is read: the largest relative difference between corresponding rank-one terms, which ignores how the scale of each term is shared among its three factors, divided by the size of the perturbation. It stops when that distance is one: the iterate is then within one perturbation of the answer, which is as close as the data can say anything.

The earlier run used a ridge of $10^{-14}$ on every subproblem, the standard cure the repair that costs exactly itself measured, and a cap of 3,000 sweeps. Both are gone here, so that the count is the iteration’s own and nothing else’s.

Tens of thousands at a hundredth #

At $\theta = 1$ the iteration arrives at once — one sweep on two tensors, three on the third — because the perturbation moved the decomposition by less than two perturbations’ worth and one sweep closes most of that. At 0.1 it takes 30, 243 and 181 sweeps; at 0.03, 1,480, 5,520 and 3,180; at 0.01, 35,720, 73,020 and 40,640. The prediction’s range for $\theta = 0.01$ was twenty to a hundred thousand, and all three land inside it. The earlier cap of 3,000 falls short by factors of 12, 24 and 14, where the prediction said more than five; at $\theta = 0.03$ it already cuts off two of the three runs.

From $\theta = 0.1$ to 0.01, a factor of ten in the angle, the counts rise by factors of 1,190, 300 and 225 on the three tensors — more than the hundred the square alone would give, on every tensor, for a reason the next two sections take apart. The first tensor’s large factor is partly its small start: at 0.1 it began only 1.6 perturbations away and arrived in 30 sweeps, before the iteration had settled into its slow rate at all.

The rate is the square of the angle #

Plotted on a logarithmic scale against the sweeps, the distance falls in a straight line once the iteration has settled, which is what a fixed contraction per sweep looks like. Reading the slope gives one minus the contraction: about $5 \cdot 10^{-3}$ to $8 \cdot 10^{-3}$ at $\theta = 0.1$, $4.5 \cdot 10^{-4}$ to $1.2 \cdot 10^{-3}$ at 0.03, and $4.9 \cdot 10^{-5}$ to $8.4 \cdot 10^{-5}$ at 0.01. Divided by $\theta^2$ every one of those lies between 0.49 and 1.3, from $\theta = 0.3$ down, on all three tensors. The fraction of the remaining distance a sweep closes is $c\,\theta^2$ with $c$ of order one.

That is the prediction’s mechanism, measured. Alternating least squares is a block nonlinear Gauss–Seidel iteration — each sweep solves exactly for one factor with the other two held — and near a solution its contraction is governed by how nearly the blocks are dependent — here, by the two columns of the third factor that the angle brings together. Their Gram matrix has eigenvalues $1 \pm \cos\theta$, the smaller about $\theta^2/2$, and the iteration crawls along the direction that eigenvalue belongs to. The Jacobian’s smallest singular value, which the earlier essay found proportional to $\theta$, is the square root of the same quantity, and an iteration that walks out of the set met the extreme case of it, where the two directions coincide and the crawl never ends.

The count is the distance over the rate #

The starting distance is the other half. The exact factors are where ALS starts, and the moved decomposition is where it has to go, and that distance is how far the decomposition moved: 1.6 to 3.9 perturbations at $\theta = 1$, 1.6 to 4.6 at 0.1, 6.1 to 14.0 at 0.03, and 19.5 to 42.0 at 0.01 — growing like $1/\theta$, as the earlier essay found. A fixed contraction needs $\ln(d)/(1 - \rho)$ sweeps to shrink a distance $d$ to one, so the count should be the logarithm of a quantity that grows like $1/\theta$ divided by a quantity that shrinks like $\theta^2$.

From $\theta = 0.1$ down, the sweeps are within fifteen per cent of $\ln(d)/(1 - \rho)$ on every tensor: 243 against 276, 181 against 184, 1,480 against 1,555, 5,520 against 5,824, 3,180 against 3,189, 35,720 against 40,417, 73,020 against 76,030 and 40,640 against 41,067. At the two largest angles the counts are too small to have a tail and the formula overshoots. So the count is $\ln(1/\theta)/\theta^2$ up to constants, and the logarithm is why each decade of the angle costs a little more than the square: at $\theta = 0.01$ the logarithm of the start is about 3.5, at 0.1 about 1.4.

Turn the dial on the trace and the three lines show the two effects together. At 0.1 they start a few perturbations out and come down steeply. At 0.03 they start three times further out and fall ten times more slowly. At 0.01 they start three times further again and fall another ten times more slowly, and the cap at 3,000 cuts them off less than a tenth of the way down.

The residual stops first #

The earlier essay found that ALS stopped on its own test hundreds of perturbations short at $\theta = 10^{-3}$, and asked about the cap. Without the cap the test still fires. The test is the one alternating least squares codes use: stop when the relative residual of the fit has stopped changing, here to the last bit of a double. At $\theta = 0.01$ it fires on all three tensors — at sweeps 14,227, 26,859 and 18,446 — before half the sweeps the iteration needs, with the factors still 3.3, 9.3 and 6.2 perturbations from the moved decomposition. At $\theta = 0.03$ it fires on one tensor of three, at sweep 5,515, five sweeps before arrival.

The reason is visible in the shape of the problem. Near its minimum the residual is a quadratic function of the distance from the decomposition, so a sweep that shrinks the distance by a fraction $c\theta^2$ shrinks the residual’s excess over its minimum by about twice that fraction of an amount that is itself the square of a small distance — the square of a few perturbations of $10^{-8}$, against a residual of about $10^{-8}$ itself. Long before the factors arrive, the residual’s change per sweep falls below what a double can represent beside the residual, and a test that reads the residual sees nothing move. A still error is not a settled one found the same thing in a fit with one term too many, where the error stopped changing by sweep 150 while the terms kept moving; the test that is a deadline found a test that fires at a fixed sweep whatever there is left to reach. Here there is a definite answer at a definite distance, and the residual is simply the wrong instrument to see it from.

The same thing happened in a different field. The honest residual is not a stopping test found a conjugate-gradient run whose residual, recomputed in double to be honest, still could not tell a stalled iteration from a converged one, because the residual measured something that had stopped changing while the error had not. There, the repair that worked read the iteration’s progress over several steps rather than one number at one step; five steps is a rate made that a stagnation test.

What a test would have to read #

The measurement says what a test that could see the arrival would have to know. The distance shrinks by a fixed fraction each sweep once the iteration has settled, so the change the factors make in one sweep is that fraction of the distance still to go. The distance to go is then the step divided by the fraction — and the fraction can itself be read off two successive steps, since their ratio is the contraction. A test built that way reads the factors rather than the residual, and from two numbers it already computes it would know both how far it has to go and how long it will take.

That is a reading, not a measurement: this essay records the distance to a known answer, which no real run has, and does not record the steps a test would use. But the straight lines in the trace say that the information is there. On every tensor at every angle from 0.1 down, the distance falls by the same factor sweep after sweep for tens of thousands of sweeps, and a quantity that regular is a quantity a test can extrapolate. The residual is the one place it is not visible, because the residual is quadratic in the distance and sits at the noise.

What uniqueness is worth now #

A factorisation that is unique for once introduced Kruskal’s condition as the thing that makes a tensor decomposition mean something a matrix factorisation cannot: its factors are determined, not just its product. The two essays since have measured what “determined” costs when the condition holds by a margin of one and the columns are nearly parallel. The answer moves by $1/\theta$ when the data move. The standard algorithm reaches it in about $\ln(1/\theta)/\theta^2$ sweeps, from the best possible start. And the algorithm’s own sense of having arrived comes earlier than the arrival by a factor of two to three.

None of that is a failure of the theorem, which never said anything about how well a unique decomposition is determined or how fast anything reaches it. It is a reason to report, beside the factors, the number the theorem does not: the smallest singular value of the Jacobian, or equivalently the smallest angle between any two columns of a factor. That number predicts both the factors’ sensitivity and the iteration’s cost before a single sweep is run, and a fit reported with it can be read for what it is.

The second half of that is measured, not assumed. The Jacobian’s smallest non-trivial singular value over its largest is a number the earlier essay computed at every angle before any iteration ran. From $\theta = 0.1$ down, one minus ALS’s contraction per sweep is between 41 and 114 times its square on every tensor: 59 and 113 at 0.1, 73, 54 and 114 at 0.03, 41, 52 and 112 at 0.01. A factor of three in the constant is a factor of three in the count, against the factor of a hundred per decade the angle itself imposes — so the singular value, squared, is a forecast of the bill to within a factor of three, made from the exact factors before paying it. With the factors only approximately known, as in a real fit, the same number computed from the current iterate after a few hundred sweeps would serve, since the Jacobian changes little over a distance of a few perturbations.

On logarithmic axes the forecast is a band of constant width, and every point from $\theta = 0.1$ down falls inside it, over three and a half decades of the singular value’s square. The three points at the two largest angles sit at its upper edge — 85, 109 and 128 times, the last just above it — where the iteration arrives in a handful of sweeps and a rate read from a short tail is a rough number. Nothing about the band depends on which tensor drew it: the three tensors’ points interleave all the way down. The spread inside the band is the part of the rate the Jacobian does not decide, and at a factor of three it is small beside the nearly four decades the angle moves the rate by across this measurement.

What a code can take from it is concrete. Gauss–Newton, which the measurement used to find the moved decomposition, is run here for eight steps at every angle, because it inverts the ill-conditioned Jacobian rather than iterating against it, and the rate that slows ALS does not enter its convergence. What each of its steps costs against a sweep of ALS, at this size or a larger one, is not measured here. What is measured is that ALS’s price is $\ln(1/\theta)/\theta^2$ sweeps, so a cap set without knowing the angle is a guess about the angle, and on these tensors a cap of 3,000 guesses that it is above about 0.03.

What three small tensors do not show #

Three tensors of one size and rank, with one pair of nearly parallel columns in one factor. Two pairs, or a near-collinearity spread over three columns, would put more than one small eigenvalue in the Gram matrix and could compound the rate; a larger tensor would make each sweep dearer and every count above more expensive in time. The start is the exact factors, the most favourable start there is, so the counts are lower bounds on what a random start needs once it has found the right basin — and a random start can fail to find it, which the earlier essays measured separately. The measurement stops at $\theta = 0.01$, where the counts reach tens of thousands; at $10^{-3}$ the formula says several million, which is not measured.

Still open: an extrapolation that knows the rate, and a Kruskal test with a tolerance #

Line search along the crawl. A fixed contraction per sweep is exactly what an extrapolation step can exploit: ALS with a line search along the change of its last few sweeps, as many codes offer, should take long steps down the slow direction. The prediction with a sign is that a line search extrapolating along the previous sweep’s change, with the step growing as the cube root of the sweep count and accepted only when the residual falls, cuts the sweeps at $\theta = 0.01$ by at least a factor of ten on all three tensors — and that its own count grows like $1/\theta$, not $1/\theta^2$.

A Kruskal test with a tolerance. The earlier essay’s second prediction still stands: that the tolerance at which the third factor’s numerical k-rank drops from three is within a factor of two of $\theta$ on every tensor, and that setting the tolerance to the data’s relative noise gives a test whose failures are exactly the fits that move by more than a hundred perturbations. With the sweep count measured, it can be sharpened: the same tolerance, squared, predicts the iteration’s rate to within a factor of three.