A short window from the start

A later look is a worse stop built a stopping clause for conjugate gradients in reduced precision on a quantity the method already carries. Hestenes and Stiefel showed that the energy-norm error at step $k$ is the sum of $\alpha_j\|r_j\|^2$ over every later step, so the same sum over the $d$ steps after $k$ is a lower bound on that error, available $d$ steps late. A clause that stops as soon as that windowed bound falls below the working precision’s unit roundoff times the iterate’s energy norm stopped twenty runs on a scaled Laplacian within 1.22 of their least error — a third of the overrun of the residual-based clause before it.

It also found that the window is a pure delay. A longer window waits longer, and in reduced precision the error past its least does not sit still: it creeps upward, by three per cent in twenty steps at the median and up to twenty-two per cent in forty. So a longer window is both slower and less safe. A window of five overran least of all but stopped some runs before their least; a window of forty overran most. The essay proposed the compromise anyone would. “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.”

Two of the three clauses hold. The third misses narrowly. And the comparison that matters is with the fixed window of five, which wins on everything the prediction scored.

The clause that shrinks #

The runs are the earlier essays’: conjugate gradients on the five-point Laplacian on square grids of 6 to 14 points a side, with and without a diagonal scaling that equalises the rows, each in four reduced precisions — 24, 16, 11 and 8 significant bits — emulated operation by operation and run to a cap well past the least error. Forty runs, each with its least energy error known.

The shrinking clause starts with a window of twenty steps. At each step it forms the windowed bound over the current window, stops if the bound has fallen below $u\|x\|_A$, and otherwise checks whether the same bound has fallen tenfold since the window was last set; if it has, it halves the window, down to a floor of four, and resets its reference. As the run converges and the bound falls through decades, the window falls through twenty, ten, five and four, so that near the end it is waiting only a few steps to confirm what the bound says. Three variants check the choices: halving per two decades instead of one, starting at forty, and a floor of eight.

Why a lower bound is the right thing to stop on #

It is worth restating what the windowed bound is, because the argument below turns on it. Conjugate gradients minimises the energy-norm error over a growing Krylov space, and each step’s reduction of the squared error is exactly $\alpha_k\|r_k\|^2$, the step length times the squared residual the method has just computed. The squared error at step $k$ is therefore the sum of all the reductions still to come, and the sum of the next $d$ of them is a piece of that, hence a lower bound. It costs one multiplication and one addition per step, and it is exact in exact arithmetic; in reduced precision the earlier essay checked that it stays at or under the true error on every scaled run before the least, by at most five per cent.

A clause built on a lower bound has two properties that pull against each other. A small bound does not prove a small error; it only fails to deny one, and a short window, which includes less of the error’s remaining tail, is easier to fool. That is the caution behind starting long. And the bound for step $k$ is not complete until step $k + d$, so the clause can only stop $d$ steps late, which is the cost of being cautious. The whole question of the window is how to trade the two, and the trade depends on how much of the error a few steps of the tail already carry — which near the least, on these runs, is nearly all of it.

The honest residual is not a stopping test and the reading that never moves were about the residual clause’s two failures in reduced precision — a residual that reports a floor while the error is still falling, and a residual that stops moving long before the error does. The windowed bound reads the error directly, and its only failure is the delay.

Two clauses hold #

The shrinking clause runs 335 steps past the least over all forty runs, against window 20’s 963: about a third, comfortably under the half the prediction asked. Its median run stops eight steps after its least, where window 20’s stops twenty. And it stops four runs before their least, where window 5 stops eight: no more, as predicted.

The bound misses by a hair #

The worst run under the shrinking clause stops at 1.126 times its least error, against the prediction’s 1.12. That is a miss of half a per cent, and it would not be worth a sentence if the figure did not show what is next to it. The fixed windows lie on a line from window 5, at 1.097 and 239 steps, through window 10 at 1.134 and 516, window 20 at 1.219 and 963, to window 40 at 1.398 and 1,805 — the delay and the creep, priced together. The four shrinking rules lie on or above that line, between windows 5 and 20. None of them is below it, and the best of them, the one the prediction specified, sits just above the point for window 5 in both coordinates.

Window 5 is safer than the shrinking clause — 1.097 against 1.126 at worst — and prompter, 239 steps against 335 in all and a median of four steps past the least against eight. There is no trade here to make. The shrinking window, whatever its rule, spends its early steps at a window of ten or twenty and pays those steps’ delay on every run, and on the runs where the estimate falls in a few large drops rather than steadily, it is still at a window of eight or ten when the bound crosses the threshold.

Run by run the picture is the same. Window 20’s error at the stop climbs from barely above one to 1.22 across the forty runs; the shrinking clause’s runs sit below it on most runs and alongside it on a few; window 5’s sit at the bottom on almost every one. The earlier essay found the window was a delay and nothing else. The shrinking window is a delay that is long at the start and short at the end, and the start’s delay is paid on every run whether or not the run ends anywhere near it.

What a short window costs #

The prediction’s caution was about the short window’s one fault: it stops some runs before their least. Window 5 does that on eight of forty. The dial shows why that hardly matters. Near its least, a reduced-precision run’s energy error is flat to within a per cent or two over tens of steps: the method has stopped making progress and has not yet started losing it, and the least itself is the lowest point of a shallow trough rather than a sharp minimum. A clause that stops a few steps early stops in the trough.

Window 5’s eight early stops are between one and twenty-two steps before the least, and none is more than 2.7 per cent above it — in the same range as the shrinking clause’s four, the worst of which is 2.5 per cent above its least. The prediction counted early stops as a failure to be minimised, because “before the least” sounds like “not yet converged”. On these runs it means “in the trough, a little before its lowest point”, and the price is smaller than the delay the long window pays to avoid it. A floor the error has not reached measured the same flatness from the other side: the error stops falling well above the floor any residual-based clause aims at, and the trough is where it stops.

Why shrinking did not help #

The shrinking rule was built on a sound observation — that the window matters most near the end — and a hidden assumption: that a short window early in the run would be dangerous. It would be, if the clause could fire early in the run, but it cannot. The threshold is the working precision times the iterate’s energy norm, and the windowed bound only falls to it when the run is near its least; at every step before that, a short window’s bound is far above the threshold, and the clause does nothing with it. So a short window costs nothing at the start, and the long window the shrinking rule begins with protects against nothing. What the long window does at the start is set the window size the rule will still be carrying when it reaches the end, which on the runs that converge in a few large drops is eight or ten rather than four.

A stopping test is a race opened this line of argument with the observation that a stopping test is two quantities racing to a threshold, and that the test is right only if the right one arrives first. Here there is one quantity, the windowed bound, and the window decides how late it reports. The best report is the earliest that is still a lower bound, and the earliest is the shortest window that the estimate’s own accuracy allows: at five steps the bound is still a bound on these runs, and the earlier essay measured it as tight to within a few per cent before the least.

Five steps is a rate found that five steps of a run were enough to read its convergence rate. Five steps of the windowed bound are enough to read its error, at the point where reading the error is the only thing left to do.

What the prediction got right #

Two of its three numbers are met, and its premise — that the window should be shortest where the stop happens — is right. What it added on top was the long start, out of a caution the runs do not need. A rule that started at five and stayed there is the limiting case of the shrinking rule with a start equal to its floor, and it is the best point on the frontier the figure draws. The two rules that shrink most slowly — halving per two decades, or starting at forty — are the two furthest from it.

There is a case for the long window that these runs do not test. A problem whose convergence stalls on a plateau in the middle of the run — a cluster of eigenvalues the method must resolve before the next decade — would show a windowed bound that flattens for a while far above the threshold, and a short window, reading that flat stretch, might see the bound fall below the threshold by chance on a quiet step. The earlier essay asked that question too, and it is still open: these forty runs converge steadily, and the short window was never tested against a stall.

What the earlier windows priced, and this one #

The essays this stands on have priced a stopping clause four ways. The residual clause with a fixed tolerance bought no agreement between runs, as the tolerance that buys no agreement found; the residual clause with a rate read off five steps stopped late by nearly two thousand steps in total; the error clause with a window of twenty stopped within a fifth of the least and late by about a thousand; and the same clause with a window of five stops within a tenth and late by about two hundred. Each step down that list read the error more directly or more promptly. The shrinking window is the first proposal that moved back up it, by adding caution where the evidence said the caution was not needed.

That ordering is also the practical recommendation for a reduced-precision solver: stop on the windowed Hestenes–Stiefel bound, with a window of a handful of steps, against the working precision times the iterate’s energy norm. It reads the error, it costs a multiplication per step, and on forty runs at four precisions it stopped every run within ten per cent of the best answer the run ever had. Paired with the iterative refinement buying the accuracy back priced at the start of this field, it tells a low-precision inner solve when it has given all it can, so that the outer correction can start from the inner solve’s best answer rather than from one a window’s delay past it. That pairing is where a stopping clause for reduced precision earns its keep: the inner solve is run many times, and every step past its least is spent in every one of them.

What forty runs do not settle #

The frontier figure is the whole of the comparison, and it is worth reading as a frontier rather than as a ranking: every point is a rule someone could adopt, and the question is whether any rule beats another on both axes at once. Window 5 beats every shrinking rule on both. Window 10 beats none of them on both. That is the shape of a result that says the shortest fixed window is the answer on these runs, and not merely a good one.

The runs are one operator family at five sizes and four precisions; the trough near the least is wide on all of them, and a run whose error rises steeply after its least would punish early stops less and late ones more, which favours the short window even further. The early stops’ cost is read against the least error, which a real run does not know; it is the right comparison for choosing a rule, not a statement about what a user would see. And the shrinking rule’s parameters — the start, the floor, the drop — were tried at four settings; a rule that starts at five and grows only when the bound stalls is the natural next variant and is not measured.

Still open: a stall in the middle, and a window that grows #

A plateau before the end. Build the operator with a cluster of eigenvalues that conjugate gradients must resolve before its next decade. The prediction with a sign is that window 5’s bound falls below the threshold on the plateau on no run — because the plateau’s error sits far above $u\|x\|_A$, and the bound, a lower bound on that error, sits at most a little below it — so that the short window’s safety holds through a stall as well, and the case for any longer window disappears.

A window that grows when the bound stalls. If a stall were ever to fool the short window, the repair is the opposite of the one measured here: start at five, and double the window whenever the bound fails to fall for that many steps. The prediction is that on the forty steady runs this rule never grows past five and so reproduces window 5’s stops exactly, and that its only cost is on runs with a stall, where it waits for the stall to end.