The penalty walks the same curve

A stop that knows the distance fitted rank-two decompositions to random 2 × 2 × 2 tensors of rank three — tensors whose slice pencil has a complex pair of eigenvalues, so that no rank-two tensor is nearest to them. Alternating least squares on such a tensor settles at its distance $d$ to the boundary of the rank-two set while its two terms grow without limit, cancelling each other more and more exactly, and the error approaches $d$ along a law: at terms of size $s$ times the tensor’s norm the error is $d + C/s^2$, with $C$ between 0.015 and 0.05 on every draw.

It priced a bounded alternative from that law, on an assumption it marked as such: if a fit constrained to terms no larger than $s$ “can do no better than that — if the fit’s own path is the best trade between size and error, which nothing here proves — then a bound of three times the norm costs an excess of about $C/9$”. Its last section turned that into a prediction. “Add a penalty on the term sizes to the least-squares objective and the fit has a best answer again. The prediction is that the penalised fit’s error at a term bound of three times the norm sits within ten per cent of $d + C/9$, the unconstrained law’s value at that size, so that the law prices the bounded alternative before it is run.”

It does, to a tenth of the margin the prediction allowed. The more useful result is what that says about the assumption, and what it says about how to get a bounded fit.

The tensors are the earlier essay’s: the first twelve of its draws whose fit reached one per cent of the distance, each with its distance $d$ computed from the boundary’s equation rather than from any fit, and its constant $C$ read from where its unbounded fit crossed one per cent. Their distances run from 0.023 to 0.21 of the tensor’s norm and their constants from 0.029 to 0.044. The rank that stops being typical counted how common such tensors are — a random 2 × 2 × 2 tensor has this problem with probability $1 - \pi/4$, about one draw in five — so this is not a corner case of the shape but a fifth of it.

A penalty that makes a best answer #

The objective is the least-squares error plus $\mu$ times the sum of the squared norms of every column of the three factor matrices, with $\mu$ fixed, so the penalised problem has a minimiser: terms that grow without limit pay without limit. Alternating least squares descends it exactly, each mode’s update solving its small normal equations with $\mu$ added to the diagonal. At a minimiser the three columns of each term have equal norms — any imbalance could be removed by rescaling at a saving — so a term of size $s$ pays $3\mu s^{2/3}$, and two terms of nearly equal size, as a diverging fit’s two always are, pay $6\mu s^{2/3}$.

That gives the penalty’s strength for a target size before anything is run. Near the boundary the squared error is about $d^2 + 2dC/s^2$; adding the penalty and setting the derivative in $s$ to zero balances $4dC/s^3$ against $4\mu s^{-1/3}$, so

$$s^{8/3} = \frac{dC}{\mu}, \qquad \mu_3 = \frac{dC}{3^{8/3}}$$

is the penalty that should give terms three times the norm. On the twelve tensors it runs from $4.8 \times 10^{-5}$ to $4.1 \times 10^{-4}$, set by each tensor’s own $d$ and $C$ from the earlier essay. Each fit is run at four, two, one, a half and a quarter times that $\mu_3$, started from the unbounded fit’s factors at the sweep where its terms first reach three times the norm.

The error at three times the norm #

Interpolated between the two penalised fits either side of size three, the error is between 0.9987 and 1.0108 times $d + C/9$ on all twelve tensors. The prediction allowed 0.9 to 1.1. Measured as excess over the distance — the price of the bound itself, $C/9$ by the law — the penalised fits pay between 0.94 and 1.13 times what the law charges, which is the same agreement seen at higher magnification, since the excess is a few per cent of the error.

The closest tensor to the boundary measured, at distance 0.023, pays an excess of 0.0046 of the norm, a fifth of its distance; the farthest, at 0.21, pays 0.0035, under two per cent of it. That is the earlier essay’s observation in a second currency: the same quantity, $C/d$, prices a near-boundary tensor’s bound in error as it priced its stop in size.

Every fit on one curve #

The figure at the top of the page puts all sixty penalised fits on one pair of axes by dividing each tensor’s excess by its own constant. The unbounded law is then the single line $1/s^2$, and the fits lie along it. Past two and a half times the norm every one of them is within fifteen per cent of the line in excess, which is within about one per cent in error; the strongest penalties, which hold the terms under two, sit above the line by up to a third. The law was fitted on the unbounded path at sizes of three and more, and it is an asymptote: below two it under-prices the penalised fits’ excess.

On a single tensor the picture is plainer, and it shows one thing the collapsed figure cannot. The unbounded path’s first samples, ten and thirty sweeps in, sit far above the law: the fit has not yet found the boundary, and its terms are already more than twice the norm. From there it joins the law and runs down it as its terms grow. The five penalised fits sit on the law at the sizes their penalties hold them to — the larger three on the path itself, the two strongest below the path’s early sweeps, on the law’s continuation where the path never was. The dial moves between a tensor far from the boundary, one at middling distance and one close to it. They differ in how high the curve sits — the closer tensor’s excess is larger at every size, by the factor $1/d$ — and not in whether the penalised fits lie on it.

That is the assumption the earlier essay could not prove, tested in the only way a penalty can test it. A penalised minimiser at strength $\mu$ is the best trade between error and size that the penalty can find near where it was started: if a point of smaller error at the same size existed nearby, the penalty would go there. It finds the path. Within the reach of this search, the unbounded fit’s own trajectory is the best trade between size and error once it has joined its law, and a bound on the terms past that point buys exactly the error the trajectory had at that size. Before it has joined — at the first few dozen sweeps on some tensors — the trajectory is worse than the best trade, and a penalty does better than stopping there would.

What the balance argument gets right #

The balance predicts the size from the penalty to within about a quarter: measured over predicted between 0.74 and 1.06 at every strength. It runs high at the weaker penalties — the fits at the balance $\mu_3$ itself reach 2.4 to 3.0 times the norm rather than 3 — and the sizes fall as $\mu$ to a power between $-0.30$ and $-0.35$ per tensor rather than the $-3/8$ the argument gives. Both departures have the same source: the balance used the law, which under-prices the excess at small sizes, so it over-states how much error a little more size would save. That is also why the error at size three was interpolated between fits rather than read off the fit at $\mu_3$.

The price in sweeps #

A bounded fit has a best answer, and on these tensors it is expensive to find. The unbounded fit reaches terms three times the norm within 144 sweeps on every tensor — on two of them within the first sweep. The penalised fit started from that point, at the balance penalty, settles on three of the twelve, after 21,096 to 31,288 sweeps, and on the other nine is still moving after 40,000. It moves slowly because it is in the swamp the earlier essays measured: two nearly cancelling terms, a nearly singular normal matrix in every update, and a penalty small enough not to spoil the fit, which is also small enough to give the iteration almost no curvature to descend.

An iteration that walks out of the set made the point that every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall, and that a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it. The penalised runs are the converse case: an objective that has a minimum, approached so slowly that after 40,000 sweeps the runs that have not settled are still changing their objective by more than a part in $10^{15}$ a sweep — the test this essay used to call a run settled — and nothing in the objective’s history says how much further they have to go. A fit that has an answer and cannot stop found the same thing with a spare term on a noisy tensor: an answer exists, the iteration cannot certify it has reached it, and the stopping test has to be about the quantity the caller wants rather than about the objective.

That makes the practical comparison stark, with one correction the measurement forced. A bounded fit’s error is the unbounded path’s error at the same size once the path has joined its law, and the unbounded path gets there two to four orders of magnitude sooner. But the obvious way to use that — run the unbounded fit and stop at the first sweep whose largest term passes three times the norm — fails on four of the twelve tensors. On those the terms pass three during the first few sweeps, before the fit has found the boundary at all, and the error there is fifteen to seventy-seven times further above the distance than the law’s $C/9$. The size is the wrong thing to watch early in a run.

The error is the right one. Stopped at the first sweep whose error is within $C/9$ of the distance — the earlier essay’s stop, with its tolerance set to the bound’s price — the unbounded fit stops within 157 sweeps on every tensor, with terms between 3.0 and 4.3 times the norm. That is the bounded fit’s answer at the bounded fit’s error, with terms a little larger than the bound on the tensors whose path joined its law late, for one sweep for every few hundred the penalised fit spends deciding where to settle. The penalty is the principled formulation and the error stop is the efficient one, and past the transient they give the same number.

Where the law under-prices #

The strongest penalties hold the terms near one and a half to two times the norm, and there the law is too optimistic: the excess is up to 34 per cent above $C/s^2$, on most tensors by ten to thirty. That is not a failure of the penalised fits, which are the best trade the penalty can find at that size, but of the law, which is the leading term of an expansion in $1/s$ and has nothing to say about where the next term starts to matter. Past two and a half the ratio is within fifteen per cent of one on every fit.

For pricing a bound, the consequence is a floor under the bound itself. A bound of three or more is priced by $C/s^2$ to within a few per cent of the error. A bound of one and a half is priced only roughly, and a fit held that tightly is no longer close to the boundary in any useful sense — its error is half again the distance on the tensors nearest the boundary.

What this says about a fit with no answer #

A fit with no answer to find found that half of random 3 × 3 × 2 tensors and most larger ones have no best decomposition of the rank they are asked for, and a nearest point that is not there gave the reason: the set of tensors of rank at most two is not closed. Every remedy for that — a penalty, a bound, a stop — is a way of choosing a point at a finite distance along a path that would otherwise run off to infinity. This measurement says that on 2 × 2 × 2 tensors the remedies agree about which point: the penalty at a given strength, the bound at a given size, and the stop at a given sweep all land on the one curve the unbounded fit traces, and the only real choice is how far along it to go. How far is a trade between the size of the terms, which the caller may need small for the factors to mean anything, and the error, which the law prices.

A rank that is not a property of the tensor showed that the same eight numbers have rank three over the reals and two over the complexes; in the complexes these tensors would have an exact rank-two decomposition and no swamp. The penalty is the real fit’s way of approaching an answer that exists only one field over, and the curve is how close it can come at each size.

A penalty is a regularisation, priced the usual way #

The construction will be familiar from a different part of numerical linear algebra. A least-squares problem whose answer is unstable, plus a penalty on the answer’s size with a parameter to choose, is Tikhonov regularisation, and the question of what the parameter costs is the one the floor is the part the noise buried and the essays before it asked of deconvolution. The analogy is closer than it looks. There the penalised solution’s error had a floor set by what the data could not say, and every penalty landed on that floor; here the penalised fit’s error has a floor set by the distance to the boundary, and every penalty lands on the curve that approaches it. In both, the penalty does not create a better answer than the unpenalised iteration passes through. It chooses where along that iteration to be, and the parameter is a way of naming the point.

What differs is the cost of finding the point. A linear Tikhonov problem is one solve at each parameter, and the earlier essays swept hundreds of parameters for the price of one factorisation. A penalised CP fit is a nonlinear iteration that has to be run to convergence at each parameter, and near the boundary that convergence takes thousands of times longer than the unpenalised iteration takes to pass the same point. The regularisation is sound and the computation is the wrong way round: the cheap path is to run the unregularised iteration and read the regularised answers off it as it passes.

What twelve small tensors do not show #

Every tensor is 2 × 2 × 2, where the boundary’s distance is a closed-form computation; the law’s constant comes from the earlier essay’s own fits. The penalised fits were started from the unbounded path, so a penalised minimiser far from that path, if one exists, was not looked for; the claim is that the path is the best trade in its own neighbourhood. Nine of the twelve penalised fits at the balance strength had not settled after 40,000 sweeps; their reported points are where they were, on the curve, but not certainly where they would end.

Still open: a start away from the path, and three slices #

Penalised from random starts. Every penalised fit here began on the unbounded path. The prediction with a sign is that from twenty random starts at the balance strength, every run that settles does so within five per cent of the same error as the path-started fit, so that the curve is the only trade there is rather than the nearest one — and that at least half of those runs do not settle within 40,000 sweeps.

Three slices. On 3 × 3 × 2 tensors with a complex pair the earlier essays found the same floor at the distance to the boundary, computed without fitting. The prediction is that the same law holds there with $C$ in the same range, so that a bound of three times the norm costs within two per cent of $d + C/9$ in error on every such tensor whose distance can be computed.