The residual turns before the error doubles

A shift that certifies a saddle followed a regularisation to its awkward end. A saddle-point matrix $\begin{bmatrix} H & A^{\mathsf T} \\ A & 0\end{bmatrix}$ whose Hessian $H$ is indefinite is quasi-definite — factorisable in every symmetric order — only once $H + \delta I$ is positive definite, which on the systems measured there needs δ past about five. At that δ the pivot signs count the inertia of $Z^{\mathsf T}HZ + \delta I$ rather than of the reduced Hessian $Z^{\mathsf T}HZ$, and every saddle whose negative curvature is shallower than δ is certified a minimum. The factorisation that was regularised so that it could not fail reports the wrong answer to the one question it was being asked.

What survived was iterative refinement against the unregularised matrix. Its error is multiplied each step by $|\delta/(\mu + \delta)|$ along each reduced curvature μ, so it contracts when every μ is positive and grows when one is negative and δ has passed half its size. The second-order test moves from an integer read once to a rate read over steps. And the essay stated the test’s limit plainly: a saddle whose negative curvature is a hundredth of δ grows by 1.0014 a step, takes 485 steps to double, and over the first hundred steps its history and a minimum’s “look alike”.

It closed by asking whether the residual could read the rate. The error is what that measurement used, because the construction knew the answer. A solver does not. It has the residual, the right-hand side minus $K$ times its current iterate, and whether a fit of the residual’s logarithm over a few dozen steps separates a shallow saddle from a minimum is the question that decides whether the test is usable at all.

What the residual starts with #

The residual obeys the same iteration as the error. If the correction solves with the regularised factor $R$, the error is multiplied each step by $I - R^{-1}K$ and the residual by $I - KR^{-1}$, which is the same matrix seen from the other side and has the same eigenvalues. So the residual’s rate, once it settles, is the error’s.

The difference is where each begins. The residual is $K$ times the error, and $K$ weights each direction by something of the size of its curvature. A regularised solve at δ = 7 is badly wrong in its large-curvature directions — its relative residual on these systems is 28, where its relative error is about one — and those directions contract fast, at $\delta/(\mu + \delta)$ with μ of several units. So the residual’s history begins with a steep fall that has nothing to do with the second-order question, and the question’s answer is buried under it until the fall is over. That is what could make the residual slower than the error, and it is the thing to measure.

How long the fall lasts can be read off the same algebra. The perturbation that does the work measured refinement removing a regularisation at $\delta/(\mu + \delta)$ a step along each reduced curvature, to three figures. Here the curvatures other than the slow ones are 2, 3, 4 and 5, so the opening fall is made of components shrinking by 0.78, 0.70, 0.64 and 0.58 a step. After ten steps the fastest of them is down by a factor of 220 and the slowest of them by twelve; after twenty, by 50,000 and 150. The fall should be over, to the resolution a sign test needs, within a couple of dozen steps, and whatever is left after that is the slow directions talking — the saddle’s negative one and the smallest positive one, which the saddle and the minimum share.

A shallow saddle and a minimum, side by side #

At μ = −0.01, the hardest case, both residuals fall steeply for the first dozen steps, from 28 to 8.9 on the saddle and to 5.0 on the minimum. Then they part. The minimum’s goes on falling at 0.9859 a step — the rate its slowest positive curvature, 0.1, predicts. The saddle’s stops falling: it bottoms out at 8.4 around step 60, and from there it creeps upward at 1.0014 a step, to 9.9 by step 200. Over the same two hundred steps the saddle’s error grows from 0.99 to 1.39, which is the change the earlier essay called too small to see. The residual’s change of direction is not small at all. By step 200 the minimum’s residual is 0.33, thirty times below the saddle’s, and it is the difference between a line that keeps falling and one that has stopped.

Turn the dial toward deeper saddles and the turn comes sooner and sharper: at μ = −0.1 the saddle’s residual is rising by step 15, and at μ = −1 it rises from the first handful of steps and has grown by six orders of magnitude by step 100.

When the verdict settles #

A verdict needs a rule, and the natural one is a sign: fit a straight line to the logarithm of the residual over the last $w$ steps and call the problem a saddle if the slope is positive. The measurement is the first step from which that rule gives the right answer and keeps giving it until the run ends.

With a ten-step window the verdict settles at step 62 on the saddle at −0.01, 24 at −0.03, 11 at −0.1 and 10 or 11 on every deeper one. On the minimum it is negative from step 10 and stays so. Fitted instead over the whole history from step zero, the verdict is later — 160 steps at −0.01, 70 at −0.03, 28 at −0.1 — because the opening fall is in the fit and has to be outweighed. And the error’s doubling time, the quantity the earlier essay’s reading rested on, is 485, 162 and 48 steps at those three depths.

So the shallowest saddle is identified eight times sooner than its error doubles, and the reason is not subtle once it is stated. A verdict is a sign. To see a sign it is enough that the residual stop falling while the minimum’s keeps falling; it is not necessary to wait until the growth is large. The earlier essay compared the saddle’s growth, 1.0014, against the minimum’s contraction, 0.986, and concluded that over a hundred steps the two histories look alike. Their errors do not look alike at step 100 — 1.20 against 0.20 — and their residuals, 8.7 against 1.4, differ by more.

The residual’s rate is the error’s #

The residual reads more than the sign. Its per-step factor over a ten-step window is 0.9981 at step 30 on the shallowest saddle — still contaminated by the opening fall — 1.0010 at step 100 and 1.0014 at step 200, which is the prediction to four places. On the minimum it is 0.9859 at step 100, again the prediction. On the saddle at −1 it matches from about step 20, and at −0.1 by step 100. So a solver that runs refinement for a couple of hundred steps knows not only that the problem is a saddle but the rate, and from the rate and δ the curvature: $|\delta/(\mu + \delta)| = 1.0014$ at δ = 7 gives μ = −0.0098 against a true −0.01.

That is a second-order certificate a factorisation cannot give on these problems at any δ past the guarantee. The pivot signs report a count and the count is wrong; the residual reports a number and the number is right.

What the wait costs #

The wait is what the regularisation charges for its legality, and it grows with the regularisation.

At δ = 5, 7, 10, 20 and 50 — every one past the Hessian’s most negative eigenvalue, −4.84 for this saddle — the verdict settles at steps 46, 62, 87, 169 and 416, and the error doubles in 346, 485, 693, 1,386 and 3,465 steps. Both are proportional to δ, and their ratio stays between 7.5 and 8.3. The minimum’s verdict is at step 10 at every δ.

The constant itself can be read off the two rates. The error’s doubling time is set by the saddle’s rate alone: 1.0014 a step, a logarithm of 0.0014. The verdict is set by the gap between the saddle’s rate and the minimum-like direction it shares with the minimum, $\ln 1.0014 - \ln 0.9859 = 0.0156$ a step, eleven times larger. Sixty-two steps at that gap is a factor of 2.6, which is how far the shared contracting component has to fall relative to the growing one before the growing one dominates the slope. The ratio of the two times is then the ratio of the two logarithms, 11.1, times $\ln 2$ over the logarithm of 2.6 — $11.1 \times 0.69/0.97 = 7.9$.

The proportionality is the rates’ doing. Both the saddle’s growth and the minimum’s contraction are $\delta/(\mu + \delta)$, which for δ large against μ is $1 - \mu/\delta$ to first order: each rate’s distance from one falls as $1/\delta$, so every timescale in the problem stretches with δ. The constant of about eight between the verdict and the doubling is this problem’s — it depends on how the opening residual is shared among the directions — but the scaling is not. A code that regularises by ten times what legality needs waits ten times longer to learn what the regularisation hid.

That is a reason to regularise no further than the guarantee needs, which the inertia-correcting loops of the shift that stops at the first right count already try to do for a different reason — and a reason, when a large δ is forced on a code, to spend some of the saving on refinement steps.

How long a window #

The window barely matters below a dozen steps: the verdict settles at step 59 with a three-step window, 60 with five, 62 with ten. It matters above that, because a long window has to fill with post-turn history before its slope can change sign — 67 with twenty, 78 with forty, 101 with eighty. The turn happens at about the same step whatever reads it, and a short window reads it soonest. A sign test on a residual computed in floating point wants some window, because a single step’s change can be rounding; ten is a fair compromise and is the one used throughout.

The symptom a caller already sees #

There is a plainer way to say what the residual does on a saddle, and it is the one a caller would meet without looking for it. Refinement is normally run until the residual falls below a tolerance. On the minimum at δ = 7 it falls steadily, by 0.986 a step, and reaches any tolerance eventually. On the saddle it never gets below 8.4 — the value it bottoms out at around step 60 — and then rises. A refinement loop with an ordinary stopping test does not diagnose the saddle; it simply fails to stop, and a code that caps its iterations reports that refinement did not converge.

A stopping test is a race described a test that stops too early because the quantity it reads is not the one it is meant to guard. This is the opposite and more benign failure: the quantity the test reads is behaving correctly and the test is right not to stop. The non-convergence is the second-order information, delivered through the channel every refinement loop already has. What the windowed slope adds is timing — the loop can report a saddle at step 62 rather than exhausting an iteration cap of several hundred — and a number, the rate, which a failure to converge does not carry.

It is worth contrasting with the other route to the same answer. A loop that asks the null space why settled a wrong count by factorising a basis for the constraints’ null space and reading the reduced Hessian’s eigenvalue directly: one QR factorisation, one small symmetric eigenproblem, and the shift in one step. That route is exact and needs a factor the saddle-point solve did not otherwise make. The residual route needs nothing but the regularised factor already in hand, and pays in solves with it — sixty of them for the shallowest saddle here. Which is cheaper depends on how large the null space is and how expensive a solve is, and on a large sparse problem the second is usually the smaller bill.

What this changes about the second-order test #

The earlier essay’s summary was that regularisation converts a sign read once into a rate read over time, and that the rate’s resolution is worst where the curvature is smallest. The first half stands and the second needs one qualification. The resolution needed to measure a curvature of −0.01 is poor: the rate differs from one by 0.0014. The resolution needed to classify it is not, because the classification is against a minimum whose own rate differs from one in the other direction by ten times as much. What separates a shallow saddle from a minimum is the gap between their rates, 0.0155 a step, and that gap is set by the minimum’s smallest positive curvature as much as by the saddle’s negative one.

This is also the answer to where the test sits relative to a minimum the Hessian cannot see, which found the unregularised count failing in floating point where the reduced Hessian is nearly singular. The residual test fails in the same place, for the same reason, and no sooner: a curvature that is zero to working precision gives a rate of one to working precision, and there is no sign to read. What the residual adds is that everything above that floor is classifiable in a few dozen steps, where the count was blind to everything shallower than δ.

What this does not settle #

One family of systems — ten unknowns, four constraints, reduced curvatures of 0.1 and 2 to 5 besides the one that varies — and one right-hand side. The step at which the residual turns depends on how the opening residual is spread over the directions, which depends on the right-hand side, and a right-hand side nearly orthogonal to the saddle’s direction would delay the turn by an amount nothing here measures. The constraints here are well conditioned; a code whose constraints are also nearly dependent meets the count’s other blind band, which a constraint the count stops seeing placed at $\sigma^2/|h|$, and whether the residual’s verdict survives a constraint that is barely there is not tried. Refinement with a residual computed in working precision was used throughout; in extended precision the rate would be the same and the floor below which no sign can be read would move.

Still open: a right-hand side that hides the saddle, and the rate from a Krylov method #

The worst right-hand side. The verdict comes when the growing direction’s share of the residual overtakes the slowest contracting one’s. A right-hand side with almost no component along the negative direction starts that share at nearly zero, and the delay is then the time for a growth of 1.0014 a step to recover it — potentially the doubling time many times over. Whether random right-hand sides ever come close to that, and whether a random perturbation of the right-hand side, which costs one solve, removes the risk, is the measurement that would turn this into a test with a stated failure rate.

A Krylov iteration instead of refinement. Refinement is a stationary iteration and reads one rate. A Krylov method preconditioned by the regularised factor, of the kind the residual the method reports studied for its own reasons, would find the negative direction in far fewer steps if it is allowed to — its own Lanczos process estimates the spectrum as it goes, and a negative reduced curvature appears there as a negative Ritz value. Whether it gives the second-order verdict in a handful of steps, and what it costs against the factorisation it is wrapped around, is the natural next comparison.