The step before the reset

Two forcing terms, one floor ran inexact Newton with both of Eisenstat and Walker’s forcing rules on five problems and found the first — which reads how wrong the linear model was at the last step — a third cheaper than the second on the strongly nonlinear problem, at the cost of more Newton steps elsewhere. On that problem the second rule took two extra Newton steps, and the essay traced them to one event: the residual rose, and the second rule’s safeguard, which bounds the forcing term below by $0.9\,\eta_{k-1}^2$ and caps it above at 0.9, let it jump straight back to 0.9.

It proposed the repair and gave it a sign. “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.”

The first clause holds. The second fails by forty points. The third fails on one problem of four, and that failure is the more interesting.

The cap, and what it is asked to do #

The problem is the one every essay on inexact Newton has used: $F(x) = Ax + \lambda x^3 - b$ in 200 unknowns, with $A$ symmetric positive definite, solved by Newton’s method whose linear systems are solved by conjugate gradients to a relative residual $\eta_k$, the forcing term. The runs are floored as one line that buys a quarter of the run recommended and stopped by the effective forward rule of a target the residual can promise, at four forward targets from $10^{-4}$ to $10^{-10}$, on five settings of the condition number and the cubic’s strength. The strongly nonlinear problem has $\kappa(A) = 10^5$ and $\lambda = 30$.

The second rule sets $\eta_k = 0.9\,(\|F_k\|/\|F_{k-1}\|)^2$, the squared ratio of the last two residual norms, which a tolerance that reads its own residual measured as the cheapest rule of its day. The cap adds one line: $\eta_k \le c\,\eta_{k-1}$, with $c$ at 3, 10 or 100. While the residual’s contraction speeds up the cap never binds, because the forcing term is falling; it binds whenever the forcing term would rise more than $c$-fold, which the prediction took to mean the step after the residual rose.

The question the cap is meant to answer is the one the problem that arrives again put at the head of this field: an inner solve is one step of an outer loop, its answer is an input to the next step rather than a deliverable, and how accurately to compute it is a question about what the outer loop will do with it. A forcing term is that question’s answer, step by step. The cap is a claim that the answer should change slowly — that a step solved to 2.4 per cent should not be followed by one solved to 90. The measurement below is about whether that claim is true of the outer loop, and it is not.

Two steps removed, nothing saved #

The figure at the top of the page is the whole result on one cell. The capped rule finishes in eleven Newton steps, the same as the first rule and two fewer than the uncapped second — the first clause of the prediction, exactly. It finishes them with 675 inner iterations, against 690 uncapped and 462 for the first rule. The two steps went; the work did not.

At every target the pattern is the same. The capped rule moves left — from 12 Newton steps to 10 at $10^{-4}$, from 13 to 11 at $10^{-6}$ and $10^{-8}$, from 13 to 12 at $10^{-10}$ — and barely moves down: 542 to 535, 690 to 675, 786 to 761, and at the tightest target up, from 879 to 905. Summed over the four targets the capped rule does 0.993 of the uncapped rule’s work and 1.451 times the first rule’s. The prediction asked for 1.05. The gap between the rules was 46 per cent and the cap closed under one point of it.

Where the work goes #

Step by step the picture is different from the one the prediction assumed. The two rules agree for four steps: one, one, two and nine inner iterations for the second, one, one, one and two for the first. At the fifth step they part. The second rule’s forcing term has fallen to 0.024, because the last two residuals fell by a factor of 6.3; the first rule’s is 0.49, because the linear model was still wrong by half. The second rule spends 109 inner iterations solving the step to 2.4 per cent; the first spends 5.

And the step the second rule solved so carefully does not help. Newton’s linear model is poor this early on a problem whose cubic term is thirty times the linear one, so the step that solves the model to 2.4 per cent overshoots, and the nonlinear residual rises from $1.3 \times 10^{-2}$ of its start to $1.5 \times 10^{-2}$. That is the rise the safeguard answers. The next four steps, with the forcing term reset to 0.9, 0.73, 0.48 and 0.21, cost 6, 8, 15 and 26 inner iterations — 55 in all — and by the end of the eighth step the second rule has spent 151 inner iterations to the first rule’s 162, ahead of it.

So the reset is not where the second rule loses. It is where it recovers. The loss is 104 inner iterations at the fifth step, before anything rose, and a second instalment at the end of the run, where the second rule’s last three steps cost 174, 196 and 57 against the first rule’s 143 and 66 — two more steps because the reset spent four steps relearning a contraction rate the first rule never lost.

What the cap does instead #

The cap leaves the fifth step alone — it cannot touch a forcing term that is falling — and changes the four after it. Held to ten times 0.024 the forcing term after the rise is 0.24 instead of 0.9, and it keeps falling from there: 0.096, 0.039, 0.018. Those steps cost 20, 40, 84 and 116 inner iterations instead of 6, 8, 15 and 26. The capped rule has spent 266 by the end of the eighth step where the uncapped one had spent 151, and the 115 it overspends there is almost exactly what it saves by not needing the two extra steps at the end.

The dial makes the trade visible at three strengths. At a hundred times the cap never binds — the jump from 0.024 to 0.9 is a factor of 38 — and the run is the uncapped one. At ten and at three it binds, the loose recovery becomes a tight one, two Newton steps disappear, and the total moves by 15 iterations either way. The cap converts the reset’s cheap, loose steps into dear, tight ones at almost exactly the price of the steps it saves.

That the trade comes out even is not a coincidence of these numbers. Conjugate gradients costs roughly the logarithm of its tolerance, as a guess worth two per cent measured; a Newton step solved to $\eta$ near the end of a run costs about as much as two solved to $\sqrt\eta$. The capped rule solves fewer steps more tightly and the uncapped rule more steps more loosely, and on a run of this length the sum of logarithms is nearly the same.

The cap binds on the forcing term, not the residual #

The third clause of the prediction was that the cap changes nothing where the residual never rose. On the mild and easy problems, and on the standing problem at caps of ten and a hundred, it changes nothing to the iteration: the ratio is exactly one. At a cap of three the standing problem moves by 0.8 per cent, because a factor of three binds on an ordinary step where the residual fell only slightly and the squared ratio jumped back up.

The ill-conditioned problem is different. With $\kappa(A) = 10^7$ the cap at ten costs 10.1 per cent of the inner work and the cap at three 11.0 — and on that problem the residual never rose, at any certifiable target. The prediction treated the cap as something that binds after a rise in the residual. It binds after a rise in the forcing term, and the second rule’s forcing term rises whenever the residual’s contraction slows, which is a different and much commoner event.

On that problem the residual falls by a factor of a hundred at the seventh step, so the squared ratio drives the forcing term down to $8 \times 10^{-5}$, and that step costs 2,111 inner iterations on a Jacobian with condition number near ten million. The residual then falls by only a factor of ten, from $4.6 \times 10^{-6}$ of its start to $4.7 \times 10^{-7}$, and the squared ratio lets the forcing term rise a hundredfold, to $9 \times 10^{-3}$. That rise is a correction. The seventh step was solved far more tightly than the outer iteration could use, and the accuracy that is thrown away is the reason: a Newton step’s error is bounded below by the square of where it started, so solving the linear model past that floor buys nothing, and the slower contraction is the outer iteration saying so. The cap holds the forcing term at $8 \times 10^{-4}$ instead, the eighth step costs 1,818 inner iterations rather than 1,225, and the ninth and tenth are dearer too. The rise the cap was written to prevent was, here, the rule noticing that it had over-solved.

The same mechanism, much weaker, is what moved the standing problem by 0.8 per cent at a cap of three: its forcing term rose sixfold, from $5 \times 10^{-3}$ to $3 \times 10^{-2}$, when the contraction slowed at the seventh step, and a factor of three held it under that. Neither problem’s residual rose. Both rules of thumb the prediction relied on — that the cap is idle when the residual falls, and that a rising forcing term is a symptom — fail on the same event.

What the safeguard was for #

The second rule’s safeguard has two halves, and this measurement separates them. The lower bound $0.9\,\eta_{k-1}^2$ stops the forcing term falling faster than the residual’s squared contraction can justify; on the strongly nonlinear problem it was inactive at the fifth step, because $0.9 \times 0.21^2 = 0.04$ is below 0.1 and the safeguard only applies above that threshold. The upper cap at 0.9 is the only limit on a rise, and the measurement says that limit is generous for a reason: a rise after an over-solved step is information, and the rule that reads residuals has no other way of receiving it.

So the defect on the strongly nonlinear problem is the fifth step, and it is a defect of falling too far, not rising too far. The rule read a residual that had fallen by 2.7 as licence to solve the next model to 2.4 per cent, on a problem where the model was still wrong by half. The first rule reads that wrongness directly, which is why it spent 5 iterations where the second spent 109.

Two ways a forcing term can be wrong #

A forcing term can be wrong in two directions, and both have now been measured. Too loose at the end of a run, and the outer iteration cannot finish: a floor with a cliff at one raised the floor under the forcing term past one times the stopping tolerance and watched four problems of five run to the outer limit, every step asked for less than the test needed. Too tight in the middle of a run, and the inner solver pays for accuracy the outer iteration discards: the accuracy that is thrown away put a floor under how close a Newton step can land, and this essay’s fifth step on the strongly nonlinear problem is the same waste arriving early, where the floor is not the square of a small residual but a linear model that is wrong by half.

The two errors have different signatures, and that is the useful part. Too loose leaves a residual that stalls, and every stopping test sees it. Too tight leaves nothing visible at all — the step converges, the residual falls or rises slightly, and the only trace is a column of inner iterations no other number reports. The second rule’s 109 iterations at the fifth step produced a step slightly worse than the first rule’s 5, and nothing in the run’s residual history says that they were wasted except the comparison with a run that did not spend them.

That is why a cap on the rise was the natural repair to propose and the wrong one to make. A rise is visible; it was the event the earlier essay could point to, and a rule written against a visible event feels like a rule written against the defect. The defect was the invisible event that caused it. A repair aimed at the fifth step would have to bound how fast the forcing term may fall when the linear model is still poor — which is what the first rule does by construction, since it reads the model’s error, and what the second rule’s safeguard does only above its threshold of 0.1.

Eisenstat and Walker published the threshold with the rule, and it has a reason: below 0.1 the safeguard would hold the forcing term up on every ordinary problem where the residual is contracting quadratically and the squared ratio is right to fall fast. The standing and easy problems are such problems, and on them the second rule is as cheap as the first or cheaper. The threshold trades the strongly nonlinear problem’s fifth step against the efficiency of every problem where Newton’s method is already in its quadratic regime, and whether that trade is right depends on how often a caller’s problem is strongly nonlinear early on — a question about a population of problems that five problems cannot answer.

What five problems do not show #

The five problems share one structure — a symmetric positive definite matrix plus a monotone cubic — so the Jacobian is always symmetric positive definite and conjugate gradients always applies; the strongly nonlinear problem’s residual rises once, at one step. A problem whose residual rose repeatedly would give the cap more to do and might change which way the trade falls. The fifth step’s over-solve is one event, and that the second rule’s whole excess traces to one event and its consequences is a statement about this problem rather than about the rule. Each figure is one problem at one target unless it says otherwise; the four targets differ only after the floor binds, which is after the fifth step, so the fifth step costs 109 iterations at every target.

Still open: a threshold, and a fold #

The safeguard’s threshold. The lower bound $0.9\,\eta_{k-1}^2$ applies only when it exceeds 0.1, and on the strongly nonlinear problem it was 0.04 at the step that went wrong. The prediction with a sign is that lowering the threshold to zero — applying the safeguard always — holds the fifth step’s forcing term at or above 0.04, costs it fewer than half the 109 iterations it spent, and brings the second rule’s work on that problem within fifteen per cent of the first rule’s, while costing under two per cent on the other four.

A fold. On a problem whose Jacobian becomes nearly singular part-way through, Newton’s direction is poor for several steps in a row and the residual rises more than once. The prediction is that the second rule’s over-solved steps multiply there, the first rule’s advantage grows past the third it reached here, and the cap — which binds once per rise — costs more than it does on the ill-conditioned problem.