Five steps is a rate

The honest residual is not a stopping test took the repair for a reduced-precision conjugate-gradient run’s blind residual — recompute it in double every few steps — and found that it reports the error well and stops nothing. At a working precision whose floor is above $10^{-12}$, the double residual never reaches $10^{-12}$, and a run that waits for it runs until its own recurrence breaks down. A stagnation clause rescued it: check the double residual every five steps, and stop when two checks in a row fail to halve it. On thirty runs that stopped every one within forty steps, at the error the recurrence rule reached, and reported a residual within a small factor of that error.

Its essay named the clause’s weak point. “The stagnation clause’s interval of five steps works because one decade comes every five steps here. A rule that set the interval from the last two checks’ observed reduction — long while progress is slow, short while it is fast — would make the clause safe on slowly converging problems. The prediction with a sign is that on the unpreconditioned Laplacian, which converges several times more slowly, the fixed five-step interval stops some runs early at above twice the attainable error, and the rate-set interval does not.”

The second half holds. The first does not, on the problem it names — and it does on a problem a little slower than that, by five orders of magnitude.

Three problems, two clauses, one oracle #

The setting is the earlier essay’s, the reduced-precision conjugate gradients that buying the accuracy back and its neighbours use to ask what a cheap working precision can still deliver: the five-point Laplacian on grids of side 6 to 14, from 36 to 196 unknowns, solved by conjugate gradients with every operation rounded to a working precision of 24, 16, 11 or 8 significand bits, and the residual recomputed from A and b in double whenever a clause checks it. Three versions of the problem are run. The first is the earlier essay’s, preconditioned by an incomplete Cholesky factor. The second drops the preconditioner. The third drops it and also scales the Laplacian’s rows and columns by a seeded diagonal D, solving $DAD\,y = Db$: the same graph, the same sparsity, with entries spread over three decades and a condition number raised from between 19 and 91 to between $1.8 \cdot 10^3$ and $8.3 \cdot 10^3$.

Each run is made once, to a cap, with the double residual and the energy-norm error recorded at every step, so a clause can be applied afterwards and its stopping step read off. The fixed clause checks every five steps; it stops when the residual reaches $10^{-12}$ or when two checks in a row each fail to halve the one before. The rate-set clause starts with an interval of five; after each check it measures the residual’s reduction per step over the interval just finished and sets the next interval to the number of steps that rate would need to gain a decade, held between five and eighty; it stops when the residual reaches the tolerance or two intervals in a row fail to halve it. The oracle is the step at which the error is least, which a code cannot know. At 53 bits every run reaches the tolerance before it stagnates, and the comparison is made on the twenty reduced-precision runs of each problem.

The Laplacian is not slow enough #

The figure at the top of the page is every reduced-precision run’s stopping error over the least error in that run. With the preconditioner both clauses stop within 1.09 times the least. Without it the fixed clause stops within 1.10 — no run early, though the unpreconditioned runs take two to three times as many steps to reach their least error.

The reason is in the clause’s own arithmetic. It stops a run early only if, while the error is still falling, five steps fail twice in a row to halve the residual. Conjugate gradients reduces its error per step by about $(\sqrt\kappa - 1)/(\sqrt\kappa + 1)$ in the worst case, and five such steps halve it as long as that factor is below $2^{-1/5} \approx 0.87$ — a condition number below about 200. The unpreconditioned Laplacian on these grids has a condition number of 19 to 91. It is several times slower than the preconditioned problem, as predicted, and still comfortably fast enough that five steps do what the clause asks. The earlier essay’s phrase “one decade comes every five steps” overstated what the clause needs: it needs half a decade’s worth, a factor of two, and the Laplacian delivers it.

The measured runs agree with the bound and are well inside it. Taking each reduced-precision run’s falling stretch — the steps before its double residual comes within a factor of ten of its floor — and the median reduction five steps achieve there, the preconditioned runs reduce the residual by a factor of 250 every five steps at the median, and the unpreconditioned ones by a factor of thirteen; the least reduction on any unpreconditioned run is a factor of 4.5. Two checks in a row would each have to see less than a factor of two, and nothing on these grids comes close. The bound’s threshold of a condition number near two hundred is pessimistic too, since conjugate gradients on a Laplacian beats its worst case; the runs suggest the fixed clause would survive grids several times larger before it began to stop early.

Scale it, and five steps is a stall #

On the scaled Laplacian, with condition numbers in the thousands, the factor per step is above 0.95 in the worst case, and the residual of the early steps falls by less than half over five of them. The fixed clause reads that slow start as stagnation. It stops nineteen of the twenty runs at step 15 — the first step at which it can have seen two failing checks — and the twentieth at step 35. The least error in those runs comes between steps 84 and 383. At 24 bits the runs it stops are half a million to 775,000 times worse than they would become; at 16 bits six hundred to 2,500 times; at 11 bits sixty-nine to 147; at 8 bits nine to fifteen. Half the runs are stopped more than five hundred times above their best.

The same five-step measurement shows why. On the scaled problem the median reduction over five steps of the falling stretch is to 0.76 of the residual, and it lies between 0.45 and 0.83 across the twenty runs: most five-step windows fail to halve the residual, and two failing in a row is the common case, not the rare one. The fixed clause’s test is a test of the rate, and on this problem the rate fails it from the first check.

The rate-set clause measures the slow start rather than reading it. At 16 bits on the 10 by 10 grid its first interval of five sees a small reduction, and it sets the next interval long enough for a decade at that rate — the ticks on the dial’s figure spread out through the slow stretch — and it stops at step 342, after the least error at step 197, at 1.05 times it. Over all twenty scaled runs it stops within 1.37 times the least error; the worst is at 8 bits on the 12 by 12 grid, where the floor is a few parts in a thousand and the error wanders on it.

The figure of stopping steps puts the two failures side by side. The fixed clause’s scaled runs sit in a row along the bottom, at fifteen, under least-error steps from 84 to 383. Every rate-set dot sits on or above the diagonal: it never stops before the best on any problem, and on the problems where five steps were enough it stops well after it.

The price of waiting a decade #

The rate-set clause’s intervals tell what it is doing. On the scaled problem they are long through the slow stretch and long again once the run is on its floor, because a residual that is barely moving sets an interval of eighty. On the preconditioned problem the same rule produces short intervals while the residual is falling — and then, once the floor is reached and the reduction per step drops to almost nothing, intervals of eighty again. The clause stops only after two intervals in a row fail to halve the residual, so on a fast run that reaches its floor at step ten it waits through one long interval to see the stall and a second to confirm it.

That is the cost, and it is not small. Over the twenty preconditioned runs the fixed clause runs 198 steps in all past the least error and the rate-set clause 1,661; without the preconditioner, 118 against 1,372. The checks themselves are not the problem — the rate-set clause makes 73 checks on the preconditioned runs, exactly as many as the fixed one, and 99 against 109 without the preconditioner — but each step it runs past the floor is a step of the iteration, at the working precision, doing nothing. On the scaled problem it makes 133 checks against 64 and runs 1,952 steps past the best; the fixed clause runs none past the best there, because it never reaches it.

So neither clause dominates. The fixed clause is cheap and right whenever five steps can halve the residual, and catastrophically wrong when they cannot, with nothing in the run to warn of the difference before it has stopped. The rate-set clause is right on all three problems and spends eight to twelve times as many steps past the best as the fixed clause on the two where the fixed clause was right.

The same trade appears wherever a stopping rule is set once for many problems. The tolerance that buys no agreement found a tighter tolerance buying accuracy and no agreement between runs; what a regression test can ask for found the tolerance a test can demand bracketed by the machine’s own variation. A stagnation clause is the same kind of object: a number chosen on the problems at hand that encodes, without saying so, how fast those problems converge. Five steps encoded a rate the Laplacian has and its scaled version does not.

What would fix the price, and what does not #

The obvious repair is to cap the interval at the number of steps taken so far, so that a run that reached its floor at step ten checks again at twenty rather than at ninety. It is the wrong repair. A cap that short lets two short intervals in a slow stretch fail to halve the residual, which is exactly the fixed clause’s failure, and on the scaled problem it brings the early stops back. The interval has to be long when progress is slow, and a stalled run and a slow run look alike over a short window — that is the whole difficulty, and the earlier essays on a stopping test that is a race met it in another form, where the step a run stops at moved with the partition count because the residual crossed its threshold slowly.

What distinguishes the two is a number the run does not have: the floor. A run on its floor has reached the error its precision allows, and the reading that never moves found that floor scaling with the working precision’s unit roundoff and the problem. If it were predictable from those two numbers, a clause could stop as soon as the double residual came within a small factor of it, and wait as long as the rate demanded only above it.

What a code can take from this #

A library that offers a reduced-precision iteration — the setting where the hardware went describes, in which the cheap arithmetic is the fast arithmetic — has to ship a stopping rule that works on problems its authors never saw. The measurement says what the two clauses promise in that position. The fixed clause promises the attainable error on any problem whose residual halves in its interval, and promises nothing at all otherwise; a code using it should at least report the reduction it saw at the last two checks, because a stop on two reductions of 0.8 is a stop on a slow problem, not on a floor, and the user can then tell the two apart even if the clause could not. Two machines, one certificate argued for reporting what a solver cannot decide alongside its answer; the last two reductions are a two-number certificate of exactly that kind. The rate-set clause promises the attainable error on all three problems here and charges for the promise in steps past the floor, which on a fast problem are most of the run.

A code that cannot afford the rate-set clause’s overrun and cannot trust the fixed clause’s interval has one more option the measurement supports: run the fixed clause, and when it stops, check whether the last reductions were below a half by a wide margin or barely failed it. The scaled runs the fixed clause stopped early stopped on two reductions each between a half and one, typical of the three quarters measured above; the preconditioned ones stopped with reductions of nearly one, on a floor. Those are different signatures, and a clause that reads them is a clause with a little of the rate in it — the earlier essay’s honest residual, used for once to decide something.

What three problems do not show #

Five small grids, one scaling, four working precisions, one iteration. The scaled Laplacian is slow because its diagonal spans a decade and a half; a problem slow for a different reason — a near-singular one, or one whose spectrum has a few outliers that conjugate gradients removes late — might stall in the middle of its run rather than at the start, and a stall in the middle with a long interval on either side is the case where the rate-set clause would wait longest. The energy-norm error is the one conjugate gradients minimises, so the least error in the run is well defined; the residual’s own minimum need not coincide with it. And the cap on the interval, eighty, is a choice: a cap of forty would halve the overrun on the fast problems and could stop a run whose decade takes more than forty steps.

Still open: the floor in advance, and a stall in the middle #

The floor before the run. The earlier essay’s second question is now the one that would remove the rate-set clause’s price. The floor the double residual stops at scales with the working precision’s unit roundoff and with the grid. The prediction with a sign is that it is predictable from those two numbers to within a factor of four on all three problems here, and that a clause stopping once the residual is within that factor of the predicted floor, and using the rate-set interval only above it, keeps the rate-set clause’s safety and runs no more steps past the best than the fixed clause.

A stall in the middle. A problem whose residual plateaus partway down — a spectrum with a cluster conjugate gradients must resolve before the next decade — is the case that tests whether two failing intervals mean a floor. The prediction is that on such a problem the rate-set clause stops on the plateau above twice the attainable error, because a plateau and a floor are indistinguishable from the rate alone, and that only a floor predicted in advance tells them apart.