A guess worth two per cent

The accuracy that is thrown away established the shape of an inexact Newton method’s economics: a Newton step is the exact answer to a linearised problem, the linearisation is wrong at second order, so there is a floor under how close the step can land and eleven decades of inner tolerance below it buy the same four digits at four times the price. A tolerance that reads its own residual then found the rule that sets the tolerance from the ratio of the last two residuals arriving at 1,009 inner iterations with neither the cost of the dearest constant nor the error of the cheapest.

Both of those are about how accurately to solve the inner problem. There is a second question that nobody has asked of this field and that a reader arrives at immediately: how to start it.

What a rebuild is worth prices the same instinct for a factorisation rather than a vector, and a factorisation kept past its date measures how long one stays worth carrying. Every inner solve above begins at zero. Along a converging sequence the Jacobian tends to a limit and the residual falls quadratically, so the previous accepted step is a vector the method already has and is at least in the right neighbourhood. Starting from it would be free.

It is free and it is worth nothing.

The unscaled guess is worse than no guess #

Starting the inner conjugate gradients from the previous accepted step, on the 200-unknown drifting problem, costs 1,583, 1,740, 2,292, 3,255, 4,680, 6,048 and 7,289 total inner iterations at forcing terms from 0.1 down to 10⁻¹⁰. Starting from zero costs 980, 1,281, 1,851, 2,982, 4,382, 5,708 and 7,016.

So the guess costs 61, 36, 24, 9, 7, 6 and 4 per cent more than nothing. Every one of those is a loss and the losses are largest where the run is cheapest.

The mechanism is a size error rather than a direction error. The warm start is applied as a correction — solve $J\delta = -F - Jd_0$ and take $d = d_0 + \delta$ — so the quantity that says how good the guess is is the ratio $\|{-F} - Jd_0\| / \|F\|$, which is one for a start at zero. Measured along a run at a forcing term of 0.01 it reads 1.000, 106.97, 15.78, 3.57, 8.15, 57.68 and 104.98.

A hundred and seven. The guess is not a little wrong; it is two orders of magnitude worse than starting from nothing, and the inner solve spends its first iterations undoing it.

Because the step falls quadratically #

Which is obvious once the residuals are looked at. The outer relative residuals along that run are 1.0, 9.4·10⁻³, 6.3·10⁻⁴, 1.0·10⁻⁴, 9.4·10⁻⁶, 1.5·10⁻⁷, 1.1·10⁻⁹ and 8.5·10⁻¹².

A Newton step is about J⁻¹F, so its size is proportional to the residual, and the residual falls by two to three orders of magnitude a step. The previous step is therefore two to three orders of magnitude too large, which is exactly the ratio the measurement reports.

That is the price of quadratic convergence, and it is a price the ordinary intuition about warm starts does not anticipate. A warm start is worth having in a sequence of similar problems — which is what the reuse essays are about, and where the successive right-hand sides are comparable in size. Inside a single Newton run the right-hand sides are not comparable; they are collapsing.

A warm start is degree zero is the same object named from the other direction: carrying the previous answer forward is the constant term of an extrapolation in the sequence parameter, and there is a whole family of higher-degree carries above it. The measurement here is that the degree-zero carry, inside a Newton run rather than across a sequence of problems, is worth less than nothing — and the reason is that the sequence parameter here is not drifting slowly, it is converging.

And the scaling fixes the size and not much else #

The repair is one line. Scale the previous step by the ratio of the two outer residual norms — the quantity the adaptive forcing rule already computes — and the guess has about the right magnitude.

It does. The same ratio at the same forcing term reads 1.000, 1.43, 1.60, 0.58, 0.40, 0.48 and 1.34, and at a tighter forcing term 1.000, 1.59, 0.55, 0.55, 0.54, 0.54, 0.55, 0.50 and 0.23. So the scaled guess halves the starting residual about half the time and increases it by up to 60 per cent the rest.

The inner counts follow: 1,039, 1,223, 1,727, 2,748, 4,231, 5,559 and 6,837 against no guess at all’s 980, 1,281, 1,851, 2,982, 4,382, 5,708 and 7,016. That is −6 per cent, +5, +7, +8, +3, +3 and +3 — a loss at the loosest forcing term and a gain of a few per cent everywhere else.

The direction, meanwhile, is fine. A guess whose residual ratio is 0.5 is a guess that supplies half of the step, and half of a vector in a 200-dimensional space is not a small amount of information — so the Jacobian has not moved much and the step’s direction is largely preserved. The information is there. What is not there is a way for conjugate gradients to be paid for it.

Why a factor of two is worth so little #

The arithmetic is the whole finding and it is not about Newton’s method at all.

A stopping test is a race is the general warning about reading one quantity as a proxy for another, and this is the benign version of it: the guess is genuinely good and the currency it is good in is the wrong one. Conjugate gradients on a system with condition number κ reduces the residual by a fixed factor per iteration, so the iterations needed to reach a relative tolerance e from a starting residual $r_0$ is proportional to $\log(r_0/e)$ — the logarithm of the ratio. Halving $r_0$ therefore saves $\log 2$ divided by the per-iteration factor’s logarithm, which is a constant number of iterations independent of e.

At a forcing term of 10⁻¹⁰ the inner solve takes about 760 iterations a step. Saving a constant handful of them is a fraction of a per cent of the step, and the 3 per cent measured is the accumulation over nine steps plus the two steps where the guess was unusually good.

So the only way a warm start could matter is if it reduced the starting residual by orders of magnitude, and the measurement above says the best it manages is a factor of four. A guess that halves a residual is not a good guess for an iterative method; it is a good guess for a direct one.

Where the guess is worth something #

It is worth noting the one row where the scaled start wins by more than noise, because it says what a warm start would need.

At a forcing term of 10⁻⁴ the saving is 8 per cent — 2,748 against 2,982 — and it is the largest in the table. That is the forcing term at which the inner solve is dear enough for a constant saving to be several iterations and the outer residual ratios are stable enough for the scaling to be accurate. Either side of it the saving shrinks: at a looser term the inner solve is too cheap for a constant to matter, and at a tighter one the outer run has fewer steps, so there are fewer warm starts to take.

The outer count, meanwhile, does not move at all. Ten, seven, seven, nine, nine, nine and nine outer steps at the seven forcing terms, identical for all three starts. That is the check that makes the comparison a comparison: a warm start that changed the sequence of iterates would be a different method, and this one changes only how each step is computed.

What a rebuild is worth prices the other half of the same economy — what it costs to recompute rather than to carry — and the two measurements bracket the question a sequence method actually faces. Carrying a factorisation is worth a great deal because a factorisation is expensive and its accuracy degrades slowly. Carrying a solution vector is worth almost nothing because the vector is cheap and the thing it is a guess at is collapsing. The general rule the pair suggests is that a carry is worth what the carried object cost, discounted by how far the problem has moved — and inside a quadratically convergent iteration the problem moves a very long way each step.

What must fail for any of this to be wrong #

Three claims and a refusal. That the scaled start saves a larger share at a tight forcing term than at a loose one — 2.6 per cent against a 5.7 per cent loss. That what it saves anywhere is a few per cent rather than a factor. That the start never changes the outer count, at any forcing term. And the refusal is fed the claim that the unscaled guess is no worse than no guess, which fails by 61 per cent at the loosest term.

The warm start is applied as a correction rather than by handing a nonzero starting vector to the inner routine, which means the inner conjugate gradients is the same routine the cold runs use. That matters for the same reason every comparison in this field is built that way: two implementations of an inner solve is a comparison between programs.

It also has a consequence worth stating. Because the tolerance passed to the inner solve is relative to the shifted residual, it has to be rescaled — a forcing term of $e$ relative to $\|F\|$ becomes $e\|F\|/\|{-F} - Jd_0\|$ on the shifted problem, capped at one. When the guess is good enough that the quantity exceeds one, the step is accepted with no inner iterations at all. That never happens on this problem at any forcing term, which is the measurement’s most compact summary.

What a negative result of this shape is worth #

The finding is that a free thing is worth nothing, which is an odd thing to spend a measurement on, so it is worth saying why the measurement was needed.

Warm-starting is one of the two or three reflexes a numerical analyst has. It is right in a sequence of similar problems, right in a continuation method, right in a time-stepping scheme, and right often enough that its being wrong here is not something a reader would guess. Every one of those settings has a parameter that drifts; a Newton run has a residual that collapses. The reflex reads the two situations as the same because in both the previous answer is nearby, and nearby is the wrong measure — what matters is nearby relative to the size of the new answer, and a step two orders of magnitude too large is nearby in absolute terms and useless in relative ones.

Second, the negative result has a boundary and the boundary is the useful part. A warm start is worth having when it reduces the starting residual by orders of magnitude, because the inner cost is logarithmic; it is not worth having when it reduces it by a factor. That is a statement about any warm start for any Krylov solve, and it says what to measure before implementing one: not whether the guess is good, but by how many decades.

Third, the reflex has a cost when it is wrong, and the cost is not zero. The unscaled guess — the thing a reasonable implementation would write first — is 61 per cent worse than the two lines it replaced. A free optimisation that makes a method slower is the worst kind of change to have in a code, because nothing in the answer says it is there.

What this does not settle #

One problem family: the 200-unknown drifting family at condition number 10⁵, with a symmetric positive definite Jacobian so that conjugate gradients applies. A problem whose Jacobian changes more slowly between outer steps would give a better guess, and nothing here says how much better.

Conjugate gradients, whose cost is logarithmic in the tolerance. A direct inner solve has no starting vector and the question does not arise; a stationary inner iteration has a cost linear in the logarithm too. The finding is about the shape of the inner method’s cost and applies to any Krylov method.

The scaling uses the ratio of outer residual norms, which is one of several available quantities. The ratio of step norms, the ratio of the last two forcing terms, or a scalar fitted by minimising the shifted residual are three others, and the last is exact by construction and costs one product.

And no line search. Every step here is accepted whole, so the previous step is the previous Newton step rather than the previous damped one, which is the favourable case for the guess.

The ratio that should have said so first #

One quantity in the measurement is the one a reader should take away, and it is not an iteration count.

$\|{-F} - Jd_0\| / \|F\|$ is the residual of the guess divided by the residual of nothing, and it is computable for one matrix–vector product before any inner iteration is spent. It is 107 for the unscaled guess and 0.5 for the scaled one, and those two numbers contain the whole of this essay: a ratio above one is a guess that is worse than zero, and a ratio of a half is a guess worth a couple of iterations.

So a code contemplating a warm start has a one-product test available, and it is a test with no tolerance in it: if the ratio is above one, discard the guess and start at zero. That costs one product a step and cannot lose, which makes it strictly better than either of the two policies measured — and it is what any implementation of the unscaled guess should have had.

Measured on the run at a forcing term of 0.01, such a policy would have discarded the guess at six of seven steps and kept it at one, arriving at the cold run’s 1,281 plus six products for the tests. The scaled policy would have kept it at three of seven. Neither is worth implementing for the few per cent at stake; the point is that the test is cheaper than the thing it tests, which is unusual and is the shape of check this field prefers.

Still open: the best scalar, the Jacobian’s own drift, and a subspace instead of a vector #

The scalar that minimises the shifted residual. The scaling above is a ratio of residual norms and is a guess at a guess. The scalar $\alpha$ minimising $\|{-F} - \alpha J d_{\mathrm{prev}}\|$ is a single inner product over a single product $J d_{\mathrm{prev}}$, and it is the best possible one-vector warm start. Whether it reaches a factor of ten rather than a factor of two — which is the threshold at which a warm start would be worth having — is one product a step away.

Whether a line search changes it. Every step here is accepted whole, so the previous step is the previous Newton step. A globalised method’s previous step is a damped one, which is smaller by the damping factor and therefore a better-scaled guess at the next full step — so the measurement may be pessimistic for the method anybody actually runs, and by a factor the damping supplies.

A subspace rather than a vector. Krylov recycling keeps a handful of directions from the previous solve and projects the new right-hand side onto them, which is a k-dimensional warm start rather than a one-dimensional one. It should reduce the starting residual by more than a factor of two, and it costs k products and k vectors of storage — a genuine trade rather than a free one.

The Jacobian’s own drift as the limit. The guess is bounded by how much J has moved between steps, since a perfect scalar on an unchanged Jacobian would give a residual of zero. Measuring $\|J(x_k) - J(x_{k-1})\|$ along the run would say what the ceiling on any one-vector warm start is, and whether the factor of two is near it or far from it.

And the same question with the forcing rule adaptive. Every sweep above uses a constant forcing term so that the start is the only thing varying. Under the adaptive rule the tolerance itself depends on the residual ratio, which is the same quantity the scaling uses, so the two interact — and the adaptive run’s totals are 1,009 cold and 1,015 scaled, which is a wash rather than the few per cent the constants give.