Two forcing terms, one floor

A target the residual can promise stopped inexact Newton for a forward error rather than a residual. A caller who wants six digits divides $10^{-6}$ by a condition number, and conjugate gradients estimates that condition number for free from the Ritz values its own iterations produce. Stopped by the effective rule — tolerance $\delta\,\hat\lambda_{\min}\lVert x\rVert/\lVert b\rVert$, the bound $\lVert x - x^*\rVert \le \lVert J^{-1}\rVert\lVert F\rVert$ read with the smallest Ritz value — and with the usual floor under the forcing term, the run landed within a fifth of its target on every cell a residual can certify.

Every run there, and every run in the four essays before it, used the second of Eisenstat and Walker’s two adaptive forcing terms: the ratio of the last two residual norms, squared and scaled. A tolerance that reads its own residual introduced it and one line that buys a quarter of the run found that it over-solves its last step unless a floor stops it. The essay named the other one. “Eisenstat and Walker’s other choice of η reads the difference between the new residual and the linear model’s prediction of it. The question from the earlier essay stands, now with a target to set its floor from: whether that rule over-solves its last step the way the ratio rule does, and so whether the floor set from δ saves as much there.”

The figure above answers the first half. Run without the floor, both rules solve the last step far past what the stopping test asks — every coloured dot above the dashed line, most of them by one to four decades. The grey dots are the same runs with the floor, all between 1.3 and 2.9.

The two forcing terms #

Inexact Newton solves each linear system $J(x_k)s = -F(x_k)$ only until the relative residual of the inner solve is below a forcing term $\eta_k$. Too small an $\eta_k$ and the inner solver does work the outer iteration will throw away, because the linearisation itself is wrong at second order; too large and the outer iteration crawls. The accuracy that is thrown away measured the first half of that: below the square of the current error, inner accuracy buys nothing.

The second choice, the one measured so far, is

$$\eta_k = 0.9\left(\frac{\lVert F(x_k)\rVert}{\lVert F(x_{k-1})\rVert}\right)^{2},$$

which asks for more accuracy as the residual falls faster, on the reasoning that fast decrease means the iteration is in the region where Newton’s quadratic rate holds. The first choice is

$$\eta_k = \frac{\bigl|\,\lVert F(x_k)\rVert - \lVert F(x_{k-1}) + J(x_{k-1})s_{k-1}\rVert\,\bigr|}{\lVert F(x_{k-1})\rVert},$$

the difference between the residual actually reached and the residual the linear model predicted, relative to where the step started. It is a direct measurement of how wrong the linearisation was over the last step, and it asks the next inner solve to be no more accurate than that. Both carry Eisenstat and Walker’s safeguards — a lower bound from the previous $\eta$ when that is above 0.1, with exponent 2 for the second choice and the golden ratio for the first — and both are capped at 0.9.

The first choice is the one that sounds as though it should know when to stop. It measures exactly the quantity that makes extra inner accuracy pointless.

Both over-solve the last step #

The problems are the forcing essays’ $F(x) = Ax + \lambda x^3 - b$ on 200 unknowns, at the standing $\kappa(A) = 10^5$, $\lambda = 3$ and at four variants moving one knob, with forward targets from $10^{-4}$ to $10^{-10}$ — nineteen cells a residual can certify, as before. Each is run four ways: each choice, with the floor at half the effective tolerance and without it.

Without the floor the first choice’s last inner solve reaches a residual a median of 34 times below the stopping tolerance, and up to 19,000 times; the second choice’s median is 95 and its largest 9,500. The first choice over-solves by less in the middle of the distribution and by more at the extreme, and on four cells of nineteen it stops within three times the test, against three for the second. That is not a rule that knows when to stop. It is a rule that over-solves on a slightly different schedule.

The extremes are larger for the first choice for a reason in its formula. Near the root the linear model’s error over a step is second order in the step, so the numerator of the first choice shrinks like the square of the residual and $\eta_k$ like the residual itself: the closer the iteration gets, the harder it asks the next step to be solved, which is what gives the method its fast local rate. On the strongly nonlinear problem at $10^{-6}$ that drove the last unfloored step to 19,000 times the accuracy the stopping test needed. The second choice’s $\eta_k$ falls like the square of the residual ratio, which flattens once the ratio settles, and its extremes are correspondingly milder.

The reason is the same for both, and it is the reason the floor exists. Neither forcing term knows where the outer iteration will stop. Each sets a tolerance from the iteration’s recent history — the residual ratio, or the model’s error — and near the end that history says the iteration is converging fast and the model is good, so each asks for an accurate step. Neither can see that the step it is solving is the last one, and that the stopping test will accept a residual several decades larger than the one it is about to pay for. The floor is the one line that tells the inner solve what the outer test needs, and nothing about how the forcing term is computed can replace it.

The over-solve shows in the forward error as accuracy nobody asked for. Floored, both choices land within a fifth of the target on every cell — the first between $2.6\cdot 10^{-2}$ and 0.15 of it, the second between $4.5\cdot 10^{-2}$ and 0.18. Unfloored, each sometimes lands within a fifth and sometimes five decades below the target, as one line that buys a quarter of the run found for the second choice with a residual stopping test. The forward target makes the waste legible: the caller said $\delta$, and the unfloored run delivered $10^{-5}\delta$ and charged for it.

The floor saves about as much #

Over all nineteen cells the floor takes the first choice from 42,859 inner iterations to 35,368, a saving of 17.5 per cent, and the second from 44,154 to 37,087, 16.0 per cent. Cell by cell the savings scatter widely and do not line up — the median is 13.1 per cent for the first and 14.9 for the second, and on individual cells one choice saves thirty per cent where the other saves nothing — because which cell’s last step happens to over-solve heavily depends on the schedule each rule follows. In total they are within one and a half points.

So the second half of the prediction holds: the floor saves as much under the first choice as under the second. On one cell, the strongly nonlinear problem at $10^{-6}$, the floor costs the second choice eight per cent instead of saving, because it lets an early step be solved loosely enough to cost an extra Newton step; under the first choice the floor never costs anything. That one cell aside, the floor is the same good bargain under either rule, which is what one would want of a line that is meant to be independent of how the forcing term is chosen.

Where they differ: the middle of the run #

The two choices end alike and travel differently. On the strongly nonlinear problem, $\lambda = 30$, the second choice’s forcing term falls quickly to $2\cdot 10^{-2}$ by the fifth Newton step — and then jumps back to 0.9, because at the sixth step the residual rose, from $1.3\cdot 10^{-2}$ to $1.5\cdot 10^{-2}$ of its start, and a ratio above one gives the largest forcing term allowed. It spends five more steps descending again. The first choice never resets: the model’s error falls steadily, and the first choice reaches the end in eleven steps and 550 inner iterations against the second’s thirteen and 786.

Turn the dial to the easy problem, $\kappa(A) = 10^3$, and the picture reverses in miniature. The second choice falls fast and straight, the residual never rises, and the first choice’s more cautious schedule — it reads a model error that is small but not tiny, and so asks for moderate accuracy for longer — costs it a step and a few per cent. On the standing problem the first choice is the cheaper by eleven per cent, and on the two in between the two are within one and a half per cent.

Cheaper overall, by a different route #

Summed over the certifiable cells, the first choice floored spends 35,368 inner iterations and the second 37,087: 4.6 per cent less. Per problem the ratio is 0.684 on the strongly nonlinear problem, 0.891 on the standing one, 0.988 on the hard one, 0.995 on the mildly nonlinear one and 1.045 on the easy one. The first choice is the cheaper on 12 of 19 cells.

It is cheaper by a different route, and the route has a price the measure used here does not count. The first choice takes more Newton steps on 15 of the 19 cells, a median of eleven against nine, and fewer inner iterations per step. Each Newton step costs an evaluation of $F$ and of the Jacobian’s action, which in these problems is cheap beside a hundred conjugate-gradient iterations, and so inner iterations are the right currency here. In a problem where evaluating $F$ is the expensive part — a simulation behind every residual — two extra Newton steps could cost more than the 4.6 per cent saved. The first choice’s advantage is real on the strongly nonlinear problem, where it avoids the second choice’s reset, and slight elsewhere.

The last step, and the steps before it #

How much of a run the last step is says how much the floor can possibly save. Without the floor the last inner solve is a median of 33 per cent of the first choice’s whole run and 36 per cent of the second’s: a third of the work spent on one step, most of it on decades the stopping test will not read. With the floor the median shares fall to 24 and 19 per cent. The floor cannot touch the rest, and the rest has its own over-solves.

A forcing term that rises by more than three times from one step to the next is the rule saying, in hindsight, that the previous step was solved more accurately than the iteration could use: the residual ratio or the model’s error has turned out worse than the accuracy it had asked for. Both choices do this on 24 steps of their runs — 24 of 189 steps for the first choice, 24 of 165 for the second. The steps just before such a rise hold 17,770 of the first choice’s 35,368 floored inner iterations and 13,504 of the second’s 37,087: half of the first choice’s work and a bit over a third of the second’s sits in steps that the rule itself later judged too tight.

That is not all waste — a tight step that lands well can be what makes the next one cheap — but it says where a better forcing term would have to find its savings. The floor removes the over-solve that comes from not knowing where the iteration ends. The over-solve that comes from not knowing how the next step will go is the forcing term’s own, and the two rules have it in different measure: the first choice, reading a noisy measurement of the model’s error, puts more of its work into steps it later loosens after; the second, reading the smoother residual ratio, puts less, but pays the reset when the residual rises. Neither is a fix for the other.

What a library default should be #

Codes that offer inexact Newton usually offer both choices and pick one as the default, and the measurements here give a reason for either. The first choice is the safer default where the nonlinearity is strong enough to make the residual rise, since its forcing term does not reset; the second is marginally cheaper on mild problems and takes fewer evaluations of $F$ everywhere. What the measurements do settle is that the floor belongs in every implementation whichever is chosen, and that it should be on by default: it saves a sixth of the inner work under either rule, costs nothing under the first and almost nothing under the second, and changes no answer the caller asked for.

What the floor is, seen twice #

The floor was introduced as a correction to one forcing rule, and it turns out to be the same correction to the other. That is the useful finding, more than which rule is cheaper. A forcing term is a model of how accurate the next step needs to be, built from the iteration’s past; the stopping test is a statement about the future, the accuracy at which the iteration will be declared done. The floor is where the two meet, and its form — never ask for less than half the stopping tolerance, relative to the current residual — does not depend on which past the forcing term read. A floor with a cliff at one found its constant must stay below one; a target the residual can promise found the tolerance it reads should come from a forward target. Neither finding depended on the forcing choice, and this one confirms that they do not.

It also says something about a guess worth two per cent, which found that starting each inner solve from a scaled previous step buys only a constant handful of iterations because conjugate gradients pays the logarithm of its tolerance. The floor works on the same logarithm from the other side: it does not make the inner solve converge faster, it stops it asking for decades it does not need, and decades are what conjugate gradients charges for.

What five problems do not show #

One family of problems, symmetric positive definite Jacobians, conjugate gradients as the inner solver, and one constant in each safeguard as Eisenstat and Walker published it. The first choice’s safeguard exponent and the second’s scaling constant were not varied; with a nonsymmetric Jacobian and GMRES the over-solve could differ, because GMRES’s residual falls monotonically and its cost per iteration grows. The targets and the effective stopping rule are the earlier essay’s unchanged, so the one uncertifiable cell — the hardest problem at $10^{-10}$ — is left out here for the same reason it was there: no residual test can certify it, and every rule runs to the outer limit on it whichever forcing term it uses.

Still open: the safeguard’s exponent, and a residual that rises #

The safeguard. The second choice’s reset on the strongly nonlinear problem came from its safeguard permitting a jump to 0.9 when the residual rose. Eisenstat and Walker’s safeguard bounds $\eta_k$ below by a power of $\eta_{k-1}$, which prevents the forcing term falling too fast but not rising too fast. The prediction with a sign is that capping the rise — never more than ten times $\eta_{k-1}$ — removes the second choice’s two extra steps on that problem and makes it within five per cent of the first choice’s work, while changing nothing on the four problems where the residual never rose.

A rising residual, on purpose. None of the five problems is hard enough to make either choice’s residual rise more than once. A problem with a fold, where Newton’s direction is poor for several steps, would make the second choice reset repeatedly; the prediction is that the first choice’s advantage there grows past the third it reached on the strongly nonlinear problem here, and that a line search, which every production code adds, changes which choice wins.