Alternating least squares on a tensor with a rank-two answer and on one without, over 20,000 sweeps
At its defaults it draws alternating least squares on a tensor with a rank-two answer and on one without, over 20,000 sweeps. The steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00141 and has not finished, while the rising curve is its largest term: 4.698 to 10.15, a factor of 2.16. Fitted over 199 points, the error falls as the 2.03 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.
swamp-trace is one function in lib/figures/cpals.js —
alternating least squares — an iteration that walks out of the set it is searching. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
The steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00141 and has not finished, while the rising curve is its largest term: 4.698 to 10.15, a factor of 2.16. Fitted over 199 points, the error falls as the 2.03 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.
show: "crawl"
The arguments are the ones A fit that has an answer and cannot stop passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
One planted rank-three tensor fitted with four terms: without noise, where the error reaches 2.47·10⁻¹⁴ and the stopping test fires at sweep 49; and with 1% noise, where it never fires. Drawn against the sweep on logarithmic axes: each run's relative change in error from one sweep to the next, which is what the stopping test reads, beside the threshold of ten to the minus sixteen at which it fires. After sweep 1,000 the noisy run's change per sweep has a median of 4.6·10⁻⁷; from sweep 500 to 6,000 its error changes by 0.0026 of itself in all, and its largest term goes from 0.672 to 0.674 of the data's size.
show: "noisycoll"
The arguments are the ones A fit that has an answer and cannot stop passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For six planted rank-three tensors at each noise level, the largest cosine between two terms of the best fit with three terms and with four. With four the medians are 0.975, 0.992, 0.977, 0.997 at no noise, 0.1% noise, 1% noise, 3% noise; the range at every level is about 0.87 to 0.999. With three they are 0.652, 0.653, 0.658, 0.669, and one tensor's own terms reach 0.96.
show: "noiseshare"
The arguments are the ones A fit that has an answer and cannot stop passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For six planted rank-three tensors at 0.1%, 1% and 3% noise, the best fit's error at ranks three, four and five divided by the noise level, beside the square root of one minus the fit's parameters over the tensor's 216 entries: 0.882, 0.839 and 0.793. The medians measured are 0.885, 0.833 and 0.781.
show: "crawl", level: 0.01
The arguments are the ones A fit that has an answer and cannot stop passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
One planted rank-three tensor fitted with four terms: without noise, where the error reaches 2.47·10⁻¹⁴ and the stopping test fires at sweep 49; and with 1% noise, where it never fires. Drawn against the sweep on logarithmic axes: each run's relative change in error from one sweep to the next, which is what the stopping test reads, beside the threshold of ten to the minus sixteen at which it fires. After sweep 1,000 the noisy run's change per sweep has a median of 4.6·10⁻⁷; from sweep 500 to 6,000 its error changes by 0.0026 of itself in all, and its largest term goes from 0.672 to 0.674 of the data's size.
show: "settle"
The arguments are the ones A fit that has an answer and cannot stop passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For six planted rank-three tensors at 0.1%, 1% and 3% noise, each fitted with four terms for 6,000 sweeps: the sweep at which the error first comes within 5% of its value at sweep 6,000, and within 1%. Within 5% by sweep 150 on 17 of 18 runs; the sweeps are 11, 133, 24, 8, 32, 32, 8, 945, 16, 6, 16, 24, 7, 90, 12, 5, 14, 22. Within 1% they are 12, 150, 27, 9, 38, 35, 9, 2666, 19, 7, 25, 27, 3677, 642, 15, 1458, 2312, 2288.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
54 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the error a ridge costs a fit that has an answer is the ridge, at λ = 1e-10 — checked 6 times
a collinearity the control is built at
a collinearity the slow fits are run at
a collinearity the sweep is drawn at
a larger ridge never lets the terms grow further
a noise level the long run is drawn at
a noise level the rank sweep is drawn at
a reading of the alternating run this generator draws
a ridge bounds the terms a swamp was growing
a run long enough to see the plateau
a run long enough to show the plateau
a size the fit is drawn at
a threshold on the elasticity
a window of at least one sweep
and at the exact rank they do not
and is tens of times above it somewhere in the usable range
and never reaches a smaller error
and on none of the ordinary fits
and one term too many returns a pair that nearly is
and past a cosine of 0.9 the badly conditioned run does not finish at all
and stops the run
and the badly conditioned run converges, which is what makes it the control
and the benign run's terms do not move
and the extra terms pair off with the ones the tensor has
and the two are separated by when it fires rather than by whether it does
and two too many is no better
and with one, the error it reaches is never as cheap as the ridge
at the true rank the agreeing starts match
how many terms past the tensor's rank to fit
matmul shapes agree
one of the six starts
one weight per term fitted
the benign run makes progress
the boundary run makes progress
the boundary run's terms grow without bound
the collinear run makes progress
the exact rank's fit returns terms that are not parallel
the fit reaches the rounding level whatever the rank asked for
the noisy overfit never stops and the clean one does
the ordinary run's do not move
the overfit's collinearity does not fall with noise
the swamp's error keeps falling
the test fires on every run with nothing to converge to
the true-rank fit leaves the share of noise its parameters predict
while firing on badly conditioned fits that do converge, which is its cost
while reaching an error that says nothing is wrong
while the heaviest ridge pulls the terms apart into a different decomposition
while the terms it returns are still the right terms
without a ridge the badly conditioned fit does converge
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
When the index is a tupleA 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.
When the index is a tupleAn iteration that walks out of the set
Every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall. What it cannot do is converge, when the target's nearest rank-r point is not in the rank-r set — and a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it.
When the index is a tupleOne term too many
A tensor built from three rank-one terms, fitted with four, reaches a relative error of 1.0·10⁻¹³ in seventy-six sweeps. Two of the four terms come back with a cosine of 0.99927 between them, subtracting each other, and the smallest weight is a fifth of the largest rather than a rounding. Nothing in the residual says any of it.
When the index is a tupleThe 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.
When the index is a tupleThe repair that costs exactly itself
A ridge on every subproblem is the standard cure for a swamp and it works — the terms stop at 1.61 instead of climbing past 6.7, and a run that never finished finishes in 798 sweeps. On a tensor that does have an answer the error it costs is the ridge itself, to within a factor of two, at every setting from 10⁻¹⁰ to 10⁻¹. And the terms it returns are still the right terms.
When the index is a tupleThe 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.