One line that buys a quarter of the run

A tolerance that reads its own residual found the adaptive forcing rule beating every constant: it costs 1,009 inner iterations where the cheapest constant costs 980 with a hundred times the forward error and the dearest costs 9,358. The rule sets each step’s tolerance from the ratio of the last two outer residuals, with a guard against the sequence’s early steps asking for too much.

The accuracy that is thrown away is the measurement the line’s comment appeals to. The implementation carries one more line than the rule as published, and it was written with a comment rather than a measurement:

The reasoning is plain. The outer loop stops when the relative residual falls below tol, and on the step that is about to achieve that, an inner tolerance far below what tol requires is accuracy nobody reads. The floor puts a bottom under the forcing term at half of what the outer test needs.

Removing it saves nothing and costs a great deal, or removing it costs a quarter of the run and buys three orders of magnitude — which of those two sentences is true depends on a question the rule does not ask.

What the line saves #

Four outer tolerances on the 200-unknown drifting problem, with the adaptive rule and nothing else changed:

Between a tenth and a quarter of the whole inner run, from one line, and the whole of it is in the last step. The last step’s inner count is 112 against 257, 84 against 371, 271 against 371 and 97 against 548 — so the floor is cutting the final solve by between a quarter and six sevenths, and the earlier steps are untouched because the floor only binds when the residual is already near the tolerance.

The outer count does not move at any tolerance. Neither does the residual the run stops at: both runs stop below the tolerance they were given, which is the test as written and is what the floor was reasoned about.

And what it costs #

The forward errors are 2.88·10⁻⁴ against 9.06·10⁻⁶, 3.14·10⁻⁶ against 1.19·10⁻⁹, 2.77·10⁻⁸ against 1.19·10⁻⁹, and 1.97·10⁻¹⁰ against 5.25·10⁻¹³.

Factors of 32, 2,600, 23 and 376. The run without the floor is between one and three orders of magnitude more accurate, at every tolerance, for between 9 and 27 per cent more work.

So the comment is wrong in one word. The accuracy the floor declines is accuracy the outer loop does not test for, which is not the same as accuracy it cannot use. The iterate the unguarded run returns is a better iterate. Nobody asked for it and it is there.

A small residual is not a small error is where this field sets the distinction out, and the floor is an unusually direct instance of it: a decision about how much arithmetic to do, taken by reading a residual, whose whole effect is on an error. Neither run is wrong and they answer different questions.

Why the extra accuracy is there at all #

The mechanism is the one the accuracy that is thrown away established and is worth following through, because it explains why the last step is different from every other.

At every step except the last, solving the inner problem more accurately buys nothing: the step lands on a floor set by the linearisation’s second-order error, and eleven decades of inner tolerance below that floor produce the same next iterate. That is the plateau, and it is why a forcing term can be loose.

The last step is not on the plateau. The outer iteration is about to stop, so there is no next linearisation to be wrong at second order — the inner solve’s accuracy is the final answer’s accuracy, directly, with nothing downstream to swamp it. So the one step at which the inner tolerance genuinely reaches the answer is the one step the floor curtails.

That is a slightly uncomfortable place for a guard to be. It is correct about every step it does not affect and it affects the only step where its reasoning does not hold.

It also explains the one row that looks out of line. At an outer tolerance of 10⁻¹⁰ the saving is 9 per cent where the other three are 20, 26 and 27, and the last step’s inner count is 271 against 371 rather than a factor of four. At that tolerance the adaptive rule’s own forcing term on the last step happens to be close to the floor already, so the floor barely binds. Which is the reassuring case: the line does nothing when the rule was going to do the right thing anyway, and its effect is concentrated where the rule would have overshot.

Which currency the caller meant #

So the line is not a bug and it is not free. It is a policy, and the policy is defensible in exactly one reading of what a caller asked for.

A caller who wrote tol = 1e-8 and meant “stop when the residual is 10⁻⁸” has asked for a residual and got one, in 26 per cent less work. A caller who meant “get me eight digits” has asked for a forward error and would have got nine from the unguarded run and six from the guarded one — because the forward error and the residual differ by the conditioning, which on this problem is 10⁵.

That is the collection’s standing point and this is an unusually sharp instance of it. Under the floor, the run’s forward error at a residual tolerance of 10⁻⁸ is 3.14·10⁻⁶ — about tol times the condition number, which is exactly what the standard bound predicts and is the honest answer to a residual request. Without the floor it is 1.19·10⁻⁹, which is better than the bound because the last inner solve happened to place the iterate rather than merely satisfy a test.

A method whose accuracy exceeds its own guarantee by three orders of magnitude, accidentally, is not a method anyone should rely on. That is the strongest argument for the floor: it makes the run’s accuracy predictable — tol times κ, every time — where the unguarded run’s is whatever the last forcing term happened to be.

What a rule should therefore do #

The measurement supports a specific change and it is not “remove the floor”.

The floor’s level is a choice and its current level is half of what the residual test needs. Setting it instead from a forward target — if the caller has one — would make the last step’s tolerance a statement about the answer rather than about the test, and the arithmetic is available: the forward error is about the inner tolerance times the conditioning, and a condition estimate costs a few solves the run has already paid for.

Absent a forward target, the two defensible policies are the two measured, and the measurement says which to prefer by saying what each is: the floor delivers the guarantee at the advertised price, and its absence delivers an unpredictable bonus at a 9 to 27 per cent premium. A library should ship the floor and document that it is there, which is the half no published statement of the rule currently does.

The line nobody wrote down #

It is worth asking why a line worth a quarter of a run is in no statement of the rule, because the answer is about what a paper and a program are each for.

The rule is a theorem-bearing object: choose the forcing term this way and the outer iteration retains its superlinear convergence, with the constants stated. A floor at the last step is irrelevant to that theorem, because the theorem is about the asymptotic rate and the last step is by definition not asymptotic. So the rule as published is complete as a statement about convergence and silent about a quarter of the arithmetic.

The program has the opposite emphasis. It has to decide what to do on every step including the last, and the decision the theorem does not cover is made by whoever implements it, usually with a comment and rarely with a measurement. A tolerance that reads its own residual measured the rule against every constant and did not measure the rule against itself with one line removed, which is the gap this essay fills.

The general shape is worth carrying. A published method is a family of programs, and the members of the family differ by the decisions the publication did not need to make. Those decisions are where a method’s measured cost actually lives, and they are invisible to anyone reading the method rather than an implementation of it.

What must fail for any of this to be wrong #

Four claims and a refusal. That the floor never costs inner iterations at any tolerance measured — it saves at all four. That it never changes the outer count. That both runs satisfy the residual test they were given, which is what makes the comparison legitimate rather than a comparison between a converged run and an unconverged one. And that the unguarded rule spends more on its last step, which localises the whole effect.

The refusal is fed the claim that the floor never costs a factor of three in the answer, and it fails at 2,600.

Both runs come from one routine with one flag, so the comparison is between two values of one line rather than between two implementations of a rule. That arrangement is what made the measurement possible at all: the floor was written into the expression as a max with no way to turn it off, which is the ordinary condition of a line that nobody has measured.

What the measurement needed from the implementation #

Making the line measurable took one change and it is the change this field keeps having to make.

The floor was written inside the expression that computes the forcing term, as a max with no alternative. There is no argument to the inexact-Newton routine that turns it off, no branch that skips it, and no record anywhere that it exists apart from its comment. So the question “what does this line do” had no answer that did not involve editing the routine, and a routine edited to answer a question is a routine whose other answers have to be re-checked.

Making the last-step floor an option and checking that the two settings agree on everything except the quantities under test is what turns an edit into a measurement. The checks do exactly that: the outer count is the same, both runs’ final residuals are below the tolerance, and the difference in inner iterations is entirely in the last step. Three checks that the two runs are the same method, so that the fourth — the forward error — is a difference the flag caused.

That pattern is worth stating because it is available cheaply and is almost never taken. A constant inside an expression is a decision with no name; a default argument is a decision with a name, a measurement and a place to record what it is worth. The cost of the second over the first is one identifier.

A guess worth two per cent is the same story on the other side of the same routine — an option that did not exist until a measurement wanted it, and a finding that a reasonable implementation would have got wrong. Both are about the same gap: between a method as it is described and a method as it runs.

What the last step is, exactly #

The floor binds on “the last step”, and the phrase deserves a definition because the method does not know which step is last until it has taken it.

The rule as implemented does not identify a last step at all. It floors every step’s forcing term at tol·‖b‖/(2‖F‖), a quantity that is tiny while ‖F‖ is large and rises toward the tolerance as ‖F‖ falls — so the floor is inactive for most of the run and becomes active exactly when the residual approaches the target. There is no branch and no lookahead.

That is a better construction than a test for the last step would be, and the reason is the one this field keeps meeting: a rule that had to know it was on the last step would have to predict the next residual, which is the thing Newton’s method is in the business of not knowing. Expressing the same intent as a floor that rises with the progress is the version that needs no prediction.

It also explains why the saving is not a clean fraction of the run. On the tolerance where the rule’s own forcing term was already near the floor, the floor binds on one step and saves 9 per cent; on the tolerances where the rule would have overshot on the last two steps, it binds twice and saves a quarter. The variability across the four rows is the variability in how many steps the floor catches, not noise.

What this does not settle #

One problem family, one conditioning — 10⁵ — and four outer tolerances. The whole argument about which currency the caller meant is quantitative in the conditioning, and at κ = 1 the two runs would agree.

The forward error is against a solution the problem was constructed to have, which is what makes any of this measurable and is not available to a method.

The floor’s constant is a half and is not swept. A floor at tol·bn/nf rather than half of it would save a little more and cost a little more, and the shape of that trade is the obvious parameter this essay leaves fixed.

And no line search, no trust region, and a symmetric positive definite Jacobian throughout. A globalised method’s last step is not the step that achieves the tolerance — it is whatever the globalisation accepted — so the floor’s reasoning about “the last step” would need restating before any of the numbers transferred.

What it means for that measurement’s numbers #

One consequence is worth drawing out because it changes how a number earlier in this field should be read.

A tolerance that reads its own residual reported the adaptive rule at 1,009 inner iterations against the cheapest constant’s 980 and the dearest’s 9,358, and concluded that the rule arrives with neither the cost of the dear one nor the error of the cheap one. All three of those runs had the floor in them, because the floor is in the routine and applies whenever the forcing term the rule computes falls below it.

For a constant forcing term the floor binds only when the constant is below tol·‖b‖/(2‖F‖) on some step, which for the tight constants it is. So the dearest constant’s 9,358 is a guarded 9,358 and its unguarded cost would be larger — the floor is doing some of the work that made the adaptive rule look good, and the comparison understates how much dearer a tight constant really is.

That does not change the earlier conclusion, which is about the ordering. It does mean the numbers in this field are numbers for a particular implementation and not for a rule, which is the same point as the section above and is worth having attached to a specific figure rather than only stated.

Still open: a floor from a forward target, the constant, and the same line in other rules #

A floor set by a condition estimate. The forward error is about the inner tolerance times κ, and κ is estimable from quantities a Krylov run already produces. A floor derived from a forward target rather than from the residual test would deliver the accuracy a caller meant at whatever it costs, and whether the cost is nearer the guarded run’s or the unguarded one’s depends on how much the two differ — which this measurement gives for one conditioning only.

The constant. A half is arbitrary. Sweeping it from a tenth to ten would put the saving and the accuracy on one curve and say whether the trade is linear or has a knee.

The same line in the other rules. A stopping test is a race is the general form of the difficulty and every rule in this field that stops on a residual is exposed to it. Whether any of them has an equivalent floor — an accuracy declined because a test would not have noticed it — is a question about implementations rather than about methods, and it is the kind of question only a measurement of a flag can answer.

And what the bonus is worth to a caller who cannot predict it. The unguarded run is more accurate at every tolerance measured, by between 23 and 2,600 times. Whether that factor is stable enough across problems to be relied on — in which case the unguarded rule is simply better and its premium is worth paying — or varies enough to be useless, is the measurement that would settle the policy rather than describe it.