A tolerance that reads its own residual

The essay on the accuracy that is thrown away ends with a curve that has a bottom, and the obvious next move is to go and sit at the bottom. It is the wrong move, and the reason is visible in the same figure if it is read one column at a time rather than as a shape.

The cheapest constant forcing term on that problem is η = 0.1, at 980 conjugate gradient iterations for the whole solve. The dearest is η = 10⁻¹⁴, at 9,358. Both stop when the outer residual is below 10⁻¹⁰, so by the test that was actually asked, both are correct. But the run at 0.1 arrives with a forward error of 2.43·10⁻⁸ and the run at 10⁻¹⁴ arrives at 2.79·10⁻¹⁰ — eighty-five times better — because a quadratically converging iteration overshoots its stopping test and the tightly solved run overshoots further.

So the two ends of the curve are not two prices for one thing. They are two different things, and the question is whether either of them is what anybody wants.

What the run actually needs, step by step #

The measurement in that essay says what a step can use: the inner tolerance stops mattering below about the distance to the root, because the linearisation error is the square of that distance.

An outer iteration does not know the distance to the root. It knows something almost as good, and it knows it for free: the ratio of this step’s residual to the last one’s. Near a root that ratio is approximately how much the linearisation is about to be wrong by, and Eisenstat and Walker’s second choice turns it directly into a tolerance,

ηₖ = γ · ( ‖Fₖ‖ / ‖Fₖ₋₁‖ )^α , γ = 0.9, α = (1 + √5)/2

with two safeguards. The first stops the sequence of tolerances falling faster than the residuals justify — if γ·ηₖ₋₁^α is above 0.1, the new tolerance is not allowed below it, which prevents one lucky step from committing the run to an expensive one. The second is the one this collection cares about and it is a single line: do not ask for an accuracy the outer loop is going to stop before using, which means η is never allowed below half the outer tolerance divided by the current residual.

Both are in the run drawn here, and the second is why the last step costs 271 iterations rather than the 500 a naive reading of the formula would have asked for.

What it costs #

Ten Newton steps. The tolerances asked for, in order:

0.90 0.76 0.58 0.37 0.18 0.053 0.021 0.024 0.0061 0.0042

and the inner iterations paid, in the same order:

1 1 2 5 17 119 160 176 257 271

The first four steps of a Newton solve on a matrix with a condition number of 10⁵ cost nine conjugate gradient iterations between them. The last two cost 528. The total is 1,009, against 9,358 for the run that solved every step to 10⁻¹⁴, and the outer residual history is

1.0 → 3.6·10⁻¹ → 2.2·10⁻¹ → 8.1·10⁻² → 2.6·10⁻² → 4.5·10⁻³ → 4.5·10⁻⁴ → 4.8·10⁻⁵ → 2.2·10⁻⁶ → 1.2·10⁻⁸ → 3.4·10⁻¹¹

which is one more outer step than the fully solved run took, and a ninth of the work.

Why no constant does this #

The temptation is to say the rule is a way of finding the best constant automatically. It is not, and the sequence of tolerances above is the proof: they span two and a half orders of magnitude inside a single run. A constant is one number. Whatever it is, it is too tight for the first four steps or too loose for the last two.

Set it at 0.9 and the early steps are free and the late ones never converge quadratically; the run takes thirty steps. Set it at 4·10⁻³ and the last two steps are right and the first four cost several hundred iterations each for a step that lands in the same place anyway. Set it at 0.1 — the measured optimum — and both of those are half true, which is what an optimum of a U is.

The rule is not interpolating between them. It is doing something no constant can do, which is to change during the run, and the quantity it changes in response to is one the run has already computed for another reason.

The plateau it is tracking is drawable, and drawn step by step it is the whole argument.

Across the first seven steps the plateau reads 1.799, 1.027, 0.5071, 0.1787, 0.03719, 0.002497 and 1.2·10⁻⁵ — six orders of magnitude inside one Newton solve. That is the reason no constant works, stated about the problem rather than about the rule: the tolerance that is exactly right at step one is a hundred and fifty thousand times too loose at step seven, and the tolerance that is right at step seven costs 560 iterations at step one to buy nothing.

The square of the distance predicts the plateau to a factor of five, and the factor drifts. Over the seven steps the ratio of plateau to d² reads 0.21, 0.32, 0.48, 0.69, 1.17, 1.81 and 1.93 — the plateau sits below the squared distance early and above it late, crossing between the fourth and fifth steps. So d² is the right scaling over six orders of magnitude and it is not the right constant anywhere for long; the mechanism the rule rests on is correct and the coefficient in it is not one number.

And the premium for solving tightly falls as the run proceeds, which is the last thing the step-by-step view says and the opposite of what the total cost suggests. The ratio of the tight run’s inner iterations to the loose one’s reads 25.5, 21.2, 16.0, 12.9, 12.1, 10.3 and 10.4 across the seven steps. A tight tolerance is most wasteful at the beginning — where the answer is furthest away and the extra digits are discarded by the next linearisation — and least wasteful at the end, where they survive. The adaptive rule is loose exactly where the waste is largest, which is why a ninth of the work costs it nothing.

The left arm is a plateau, not a slope #

The comparison at the top of this essay takes η = 10⁻¹⁴ as the dearest constant and treats it as the top of a continuum: pay more, get more, and the rule’s job is to find where that stops being worth it. Swept properly, the continuum is not there. The whole left arm is one answer at eleven different prices.

Nine decades of forcing term, five per cent of movement in the answer, and a factor of 2.53 in the bill. The run at 10⁻¹⁴ does not merely resemble the run at 10⁻⁵; it produces the same number to two significant figures, and 5,655 of its 9,358 inner iterations bought nothing at all. The plateau ends at 10⁻⁴, where the forward error triples in one decade — so this is a flat with an edge on it rather than a sweep in which nothing happens.

That corrects the headline comparison further down this page. “Against the dearest constant, the rule costs a ninth of the work” is arithmetic against a constant that is itself paying 2.5 times over. The comparison that means something is against the cheapest constant that reaches the same accuracy, which is η = 10⁻⁵ at 3,703 iterations, and against that the rule costs 27 per cent. Still the right answer, still by a wide margin, and a claim that survives somebody re-running the sweep.

What the eighty-five is and is not #

The mechanism offered for the eighty-fold accuracy gap between the two ends — that a quadratically converging iteration overshoots its stopping test, and the tight run overshoots further — is right in direction and does not carry the number.

Both runs stop when the outer relative residual falls below 10⁻¹⁰. The tight one lands at 1.43·10⁻¹³, seven hundred times past the line; the cheap one lands at 4.09·10⁻¹¹, only two and a half times past. So the residual overshoot differs by a factor of 286 and the forward error by 87. The missing factor of 3.3 is in the amplification between them: the ratio of forward error to final residual is 594 on the loose run and 1,950 on the tight one, and it varies by more than a factor of three across the sweep.

Which is a second reason the two ends are not two prices for one thing. They do not even sit on one line from residual to error, because the iterates they stop at are in different parts of the basin and the local amplification is not the same there. The overshoot argument explains the sign of the gap. Nothing in it predicts eighty-five, and eighty-five is a measurement rather than a consequence.

assertTheExpensiveArmIsAPlateauInAccuracy holds the whole of this: that the forward error is one number across nine decades, that the work over that range varies by more than two-fold and buys nothing, that the plateau ends at 10⁻⁴, that the overshoot is real but that the residual gap is far larger than the error gap, and that the honest comparison for the adaptive rule is against 3,703 rather than 9,358.

The comparison that has to be made on two numbers #

The awkward part of this comparison, and the reason the refusal in this essay is worded the way it is, is that a single number cannot express it.

• Against the cheapest constant, the rule costs 3 per cent more work (1,009 against 980) and arrives with a comparable forward error.
• Against the dearest constant, the rule costs a ninth of the work and arrives with a hundred times the forward error.

Neither of those on its own is a recommendation. What makes the rule the right default is the pair together with a third fact: the cheapest constant is only knowable by running the whole sweep, and the sweep is specific to this problem, this conditioning and this outer tolerance. Move the outer tolerance from 10⁻¹⁰ to 10⁻¹² and the minimum moves; the rule does not have to be told.

What the rule cannot see #

This collection’s habit is to say where a rule fails, and this one has a clean answer: it cannot see cost.

The forcing term decides how much of an inner solve to buy. The rule prices that decision in the only currency it can observe — the residual, which is a statement about accuracy — and it never asks what an inner iteration costs relative to an outer step. On this problem that is harmless, because an outer step is a residual evaluation and a Jacobian assembly and the inner solve is hundreds of matrix–vector products, so the inner side dominates and the accuracy question and the cost question have the same answer. The problem that arrives again is the field’s statement of that ratio, and it is the thing a forcing term is priced against.

Change that ratio and they come apart. If the residual evaluation were the expensive thing — a full physics evaluation, say, with a cheap Jacobian — then more inner work per step would be worth buying, because it saves outer steps and outer steps are what costs. The rule would keep asking for the same tolerances and would be wrong, quietly, by whatever that ratio is.

The essay on what a rebuild is worth is the same observation about a different object, and there it is not harmless: the rule that reads the iteration count of a preconditioned solve loses to a fixed period at both ends of the range, because what it cannot see is exactly what decides the answer there.

The safeguard that is one line #

It is worth isolating the second safeguard, because it is where the collection’s own subject appears inside somebody else’s method.

Without it, the formula on the last step of a converging run asks for a tolerance proportional to the square of a residual that is already at 10⁻⁸ — which is to say, for something near 10⁻¹³ relative, on a step whose result will be tested at 10⁻¹⁰ and then accepted. The tolerance is not wrong; it is simply for a quantity nobody is going to look at.

With it, η is floored at half the outer tolerance divided by the current residual: exactly the accuracy that makes the next outer residual land at the tolerance, and no more. On the run above that turns the last step’s demand from a number the formula produced into 4.2·10⁻³, and the step costs 271 iterations rather than several hundred.

It is a line of code and it is worth about a fifth of the whole solve, and the thing it encodes is the field’s sentence: an inner solve is worth exactly as much accuracy as the outer loop is going to use — which is the distinction between a residual and an error turned into a floor.

The first four steps cost nine iterations #

It is worth pausing on one line of the table above, because it is the part that sounds wrong.

The first four Newton steps of this solve — on a 200×200 system whose Jacobian has a condition number of 10⁵, where a single conjugate gradient solve to machine precision costs over a thousand iterations — cost one, one, two and five iterations. Nine in total. A tenth of one per cent of what the fully solved run spends on the same four steps.

Nothing has been approximated away. Those are real conjugate gradient solves of the real Newton systems; they simply stop after a step or two because the tolerance they were given is 0.9, 0.76, 0.58 and 0.37, and a single step of conjugate gradients from a zero start already reduces the residual by more than that on this problem. What the rule has noticed is that the outer iteration is so far from the root that a direction is all a step can use, and the first conjugate gradient iterate is the steepest-descent direction scaled to minimise the quadratic — which is a perfectly good direction.

The outer residuals over those four steps run 1.0 → 0.36 → 0.22 → 0.081 → 0.026. That is a factor of forty, for nine matrix–vector products, from a method that has not yet been asked for a single accurate solve.

The last two steps then cost 528 iterations between them, and every one of those is needed: they are the steps where the outer residual goes from 2.2·10⁻⁶ to 3.4·10⁻¹¹ and the plateau has dropped below what a loose solve can reach.

The work is where the accuracy survives. That is the entire content of the staircase, and it is what a constant cannot express.

Where this sits beside the collection’s other rules #

Three parameter-choice rules have been measured here now, and it is worth putting them side by side, because they fail in different places and the pattern is not obvious.

A regularisation parameter is chosen without knowing the noise level, and every published rule for it is a heuristic that can be scored against a truth that exists only because the problem was constructed. Some of them are badly wrong on some problems.

A step count used as a regularisation parameter degrades gently: being one step out costs a few per cent, in the way a factorisation kept past its date does not, which is a different kind of robustness from being right.

A forcing term is chosen with the answer unknown too — and unlike the first two, being wrong costs work rather than accuracy. There is no bad answer at the end of a Newton run with a badly chosen forcing term, only a slow one or a wasteful one. That is what makes it the easiest of the three and the one where an automatic rule is uncontroversial.

What the rule assumes about the outer iteration #

The rule reads the ratio of consecutive residuals and turns it into a tolerance, and that step carries an assumption worth making explicit: that the residual ratio is a usable proxy for how wrong the linearisation is about to be.

Near a simple root of a smooth problem it is a good one, which is the case the formula was derived for and the case measured here. Away from one it can be poor in either direction — a step that happens to reduce the residual sharply is read as evidence that the linearisation is good, and the rule tightens; a step that stalls for a reason unrelated to the linearisation is read as evidence that it is bad, and the rule loosens.

Both of those are why the safeguards exist. The first stops one lucky step from committing the run to an expensive tolerance, and it is not a numerical nicety — it is the rule declining to believe a single observation. The second stops the last step from being solved past the point the outer loop will look at.

What neither safeguard can do is notice that the proxy has stopped being a proxy, and the honest statement of this rule’s scope is that it is a heuristic with two guards on it rather than a measurement of the quantity it wants.

What is checked #

Four things are asserted about this rule rather than described, and each of them is fed a case it must refuse.

That the rule costs under an eighth of the fully solved run — 1,009 against 9,358 — with a final residual below the tolerance it was given.

That its tolerances actually move: above 0.5 at the first step and below 0.05 at the last, which is what makes it not a constant.

That the cost profile follows: a handful of iterations at the first step and hundreds at the last, so the work is spent where the accuracy survives.

And that the effect needs something to save. The refusal is a problem at a condition number of 4, where the inner solve costs a handful of iterations at any tolerance: there the claim that oversolving costs a factor of eight is fed to the assertion and fails, which is what stops the main result from being a statement about arithmetic in general.