A later look is a worse stop

A floor the error has not reached predicted the residual floor of a reduced-precision conjugate-gradient run from the arithmetic — $u\,\|\,|A||x|\,\|/\|b\|$, to within a factor of 3.3 on sixty runs — and then found that the prediction could not be used as a stopping test. The residual reaches its floor tens of steps before the error reaches its least: at the step the residual first comes within four times its floor, the energy error is still 4.6 to 12.6 times as large as it will get. Every clause in the essays before it — five steps is a rate and the honest residual is not a stopping test among them — read the residual and paid for it, either by stopping too early or by running long past the least.

The essay ended by proposing to read the error instead, from numbers the method already carries. “Conjugate gradients carries the quantities for a cheap lower bound on the energy error — the sum of $\alpha_j\|r_j\|^2$ over a window of the last $d$ steps. The prediction with a sign is that on the scaled problem a clause stopping when that estimate over a window of 20 steps falls below $u$ times the energy norm of $x_k$ stops all twenty runs within two fifths of their least error, and does so within thirty steps of the least on the median run, where the rate-set clause runs 1,952 steps past it in total.”

The clause is safe on every run, and it cuts the overrun to a third. The median clause misses by three steps. And a sweep of the window says something the prediction did not ask: waiting longer to be sure is worse.

An estimate the method has been carrying all along #

In exact arithmetic conjugate gradients satisfies a remarkable identity, due to Hestenes and Stiefel: the squared energy norm of the error at step $k$ is the sum, over every later step, of the step length times the squared residual, $\|x - x_k\|_A^2 = \sum_{j \ge k} \alpha_j \|r_j\|^2$. Every term is positive, so any finite stretch of the sum is a lower bound, and the stretch from $k$ to $k + d - 1$ is available at step $k + d$ from the step lengths and residual norms the recurrence computes anyway. It costs one multiplication and one addition per step.

Two things could go wrong in floating point. The identity relies on the orthogonality that rounding destroys, and the residual it uses is the recursively updated one, which in reduced precision drifts away from $b - Ax_k$; the residual the method reports measured that drift reaching nine orders of magnitude. Work by Strakoš and Tichý showed the window estimate survives both for as long as the error is well above the arithmetic’s floor. Measured here, it does: on every one of the twenty scaled runs the window estimate stays at or below the true energy error at every step before the least, with a largest ratio of 1.018, and mostly between a half and one.

The picture says where the guarantee stops. Up to the step of least error the points of every run, in every precision, lie on or below the line where the estimate equals the error: in 24 bits they hug it, and in 8 bits they sit a little under, between a third and two thirds of the error for most of the run, because the coarser arithmetic loses a little more of each term. Past the least they fall away by orders of magnitude. The recursively updated residual goes on shrinking there while the true error has stopped, and the estimate, built from that residual, follows the residual. That is the shape a stopping test wants. Before the least the estimate is honest and slightly pessimistic about how much error is left, so a threshold on it cannot fire early; and the place where it parts company with the error is exactly the place the run should already have stopped.

The estimate is also nearly free. The residual clauses of the earlier essays read the true residual, $b - Ax_k$ recomputed in double precision, which costs a full product with the matrix at every check — the reason they check only every five steps, or at intervals set from the rate. The window sum needs one multiplication and one addition per step, from two numbers the recurrence has just computed, so it can be checked at every step for nothing. An orthogonalisation nobody calls one explained why the identity holds at all: conjugate gradients builds an orthogonal basis of residuals without saying so, and the energy it removes at step $j$ is exactly the component of the error along the $j$-th direction. Summing those components is reading the error off its own expansion, one coefficient at a time, and a window of $d$ steps is $d$ of the coefficients.

The clause stops at step $s$ as soon as the window estimate for step $s - 20$ falls below $u\,\|x_{s-20}\|_A$, with $u$ the working precision’s unit roundoff, and it reports the iterate at $s$. The threshold is the error a perfect run in that precision could hope for: rounding the iterate’s entries alone costs about $u$ of its size.

Safe on every run #

The error clause stops every scaled run within 1.22 times its least error: the worst is the 12-by-12 grid at eight bits, where the error rises fastest after its least. The rate-set residual clause, which waits for two checks in a row that fail to halve the residual, has a worst of 1.37. The fixed residual clause, which checks every five steps, stops before the least on every scaled run — the scaled problem’s residual stalls early and often, and two failed halvings come long before the error has done its work — with errors up to 780,000 times the least. The prediction’s bound of two fifths holds with room to spare, at every precision from twenty-four bits down to eight.

On the plain Laplacian, the twenty runs without the diagonal scaling, the error clause’s worst is 1.13 and the rate-set clause’s the same; the fixed clause works there, at 1.10. The scaled problem is the hard case for a residual clause, and the error clause does not notice the difference: it reads the error, and the scaling changes the residual’s relation to the error but not the error’s relation to itself.

A third of the overrun, and three steps late on the median #

In total the error clause runs 601 steps past the least across the twenty runs, against the rate-set clause’s 1,952: under a third. Run by run it stops between two steps before the least and 59 after; the rate-set clause stops between 11 and 163 after. The median run’s error clause stops 33 steps after its least, where the prediction said thirty or fewer. The miss is small and it is structural, and the reason is the window itself: the estimate for step $k$ cannot be computed until step $k + 20$, so even a clause whose estimate crosses its threshold at exactly the least error stops twenty steps later. Thirty- three is the twenty-step window plus the thirteen steps the estimate takes, at the median, to fall from the least error’s level to the threshold.

The window is a delay, and in reduced precision delay costs accuracy #

The run on the dial shows the mechanism. The error falls, reaches its least, and then rises slowly — in reduced precision the computed iterate does not stay at the best it reached, because each later step adds rounding that the recurrence no longer corrects. The window estimate follows the error down, a little under it, and keeps falling past the least, because it is built from the recursively updated residual, which goes on shrinking long after the true error has stopped. It crosses the threshold, and the clause stops twenty steps after the step it describes. By then the error has risen a little from its least, and that rise is the clause’s whole cost.

So the window’s length trades nothing for safety; it only adds delay, and delay is paid for in the error’s rise. On the scaled runs a window of 5 totals 173 steps past the least with a worst of 1.10; a window of 10, 354 and 1.13; 20, 601 and 1.22; 40, 1,043 and 1.40. The plain runs show the same order, from 66 steps and 1.05 at a window of 5 to 762 steps and 1.13 at 40. The longest window is the least safe, which is the opposite of what a window is usually for.

The usual reason for a longer window is that a longer sum is a tighter lower bound: in exact arithmetic the sum from $k$ to infinity is the error itself, and a window of $d$ terms captures more of it as $d$ grows. A tighter bound would make the clause stop later in the sense of being less likely to stop while the error is still large. But at these precisions the window-5 bound is already tight enough never to stop badly early: it stops six runs of twenty before their least, and none of them more than ten per cent above it, because by the time a five-step sum falls below $u\,\|x\|_A$ the error is within a few steps of its least. The extra safety a longer window buys is safety against stopping before the least, and stopping before the least costs less than stopping after it.

A threshold the error never reaches #

There is something odd about the clause’s success, and it is worth stating plainly. The threshold is $u\,\|x_k\|_A$, the error a perfect run in the working precision might reach. On the scaled runs the least error the run ever reaches is between 3.2 and 13.6 times that threshold, with a median of 8.3; on the plain runs between 1.7 and 5.0 times it. The true error never comes down to the threshold. If the window sum were the true error, the clause would never stop.

It stops because the window sum is not the true error once the error has stopped falling. Its terms are built from the recursively updated residual, and in reduced precision that residual goes on shrinking geometrically after the true residual and the true error have both reached their floors — the gap the residual the method reports measured at nine orders of magnitude. While the run converges the sum tracks the error from below, within a factor of two; past the least it detaches and falls on, and it falls through the threshold at a rate set by the recursion, not by the error. The reading that never moves saw the same detachment from outside: the residual the method reports stops at the same tiny level, between $10^{-13}$ and $10^{-12}$, at every precision from fifty-three bits to eight, because that level belongs to the recursion and not to the answer. The clause works because it reads two things in sequence: the error, faithfully, for as long as there is error to read, and then the recursion’s own collapse, which happens only after the error has stopped.

That makes the threshold’s exact value less important than it looks. A threshold ten times higher would be crossed a few steps earlier on the same collapse; ten times lower, a few steps later. What matters is that it sits below every error the run can reach — so that the clause cannot fire while the error is still falling — and above the floor the recursion falls to, which in these precisions is far below. The tolerance that buys no agreement found the opposite problem with a residual tolerance asked to mean more than the arithmetic allows; here a tolerance set at the arithmetic’s own scale means exactly what the clause needs.

How much the wait costs #

The window’s cost is the rise in the error between the least and the stop, and it can be measured directly. On the scaled runs the energy error twenty steps after its least is a median 2.9 per cent above the least and at most 9.1 per cent; forty steps after, at most 22 per cent. On the plain runs it barely moves — a median 0.4 per cent at every delay — which is why the window length matters so much less there. The rise comes from the recursion carrying on after it has nothing left to remove: each further step adds rounding to the iterate in directions the method no longer corrects, and in eight-bit arithmetic that drift is visible within ten steps.

So the safety numbers in the window sweep are the rise curve read at different delays. A window of 5 stops a median eight steps after the least, where the error has risen about one per cent; a window of 40 stops a median 54 after, where it has risen three, and on the worst run twenty-two. A walk needs a length found the same mechanism in the gap between the two residuals — a random walk of roundings that grows with the number of steps it is given. The clause’s best defence is not to give it steps.

Why the residual clauses could not do this #

The residual clauses failed for a reason the error clause avoids by construction. The honest residual is not a stopping test found the true residual pinned at its floor while the error was still falling, so a clause that waits for the residual to stop improving waits for something that has already happened and cannot tell when the error catches up. Five steps is a rate found the fixed clause’s interval too short for slowly converging runs and the rate-set clause’s too long once the residual flattened, and a floor the error has not reached found that even an exact prediction of the floor did not say when the error would stop. All three were trying to infer the error’s state from a quantity that stops tracking it exactly when the inference matters.

The window sum tracks the error rather than the residual. Its terms are the energy the method removes at each step, and when the method stops removing energy — when the error stops falling — the sum stops growing. That the recursive residual in it goes on shrinking past the least is what makes it cross the threshold, and that is the right behaviour: by then the true error is at its floor and further steps cannot lower it. A stopping test is a race argued that a stopping rule is a contest between the quantity it reads and the quantity it is meant to protect; here they are, for once, the same quantity read twenty steps late.

What twenty runs do not show #

Every run is unpreconditioned. With a preconditioner the identity holds in the preconditioned energy norm, with $\alpha_j$ times the inner product of the residual and the preconditioned residual in place of $\alpha_j\|r_j\|^2$; it is not measured here. The threshold $u\,\|x_k\|_A$ is the arithmetic’s floor for the iterate’s representation and ignores the floor the recurrence itself adds, which on these problems lies below it; on a problem with larger growth in the recurrence, the estimate might cross the threshold late or not at all. And the explanation of the window’s cost as the error’s rise after its least is read off the runs and checked against the measured rise only in aggregate.

Still open: a window that ends at the least, and a stall in the middle #

A window that shrinks. If the window is a pure delay, the right window is the shortest whose estimate is already tight. The prediction with a sign is that a clause starting with a window of 20 and halving it each time the estimate falls by a decade, down to a floor of 4, stops all forty runs — scaled and plain — within 1.12 times their least error and totals less than half the window-20 clause’s overrun, with no more runs stopped before their least than the fixed window of 5 stops.

A stall in the middle. The earlier essay’s second question is still open and is now answerable with a quantity that reads the error. A plateau partway down a run — a cluster of eigenvalues the method must resolve before the next decade — is a stall in the error, not only in the residual. The prediction is that on a problem built with such a cluster, the window-20 estimate falls below the threshold on the plateau on no run, because the plateau’s error sits far above $u\,\|x\|_A$, while the fixed residual clause stops on the plateau on at least one run in four.