The right-hand side that hides the saddle

The residual turns before the error doubles rescued a second-order test from a regularisation. A saddle-point matrix $K = \begin{bmatrix} H & A^{\mathsf T} \\ A & 0\end{bmatrix}$ whose Hessian is indefinite becomes factorisable in any order once $H + \delta I$ is positive definite — the regularisation that legalises every order — and at that δ its pivot signs certify every saddle shallower than δ as a minimum. Iterative refinement against the unregularised $K$, correcting with the regularised factor, keeps what the signs lose: along each reduced curvature μ its error is multiplied each step by $|\delta/(\mu + \delta)|$, which is above one on a saddle and below one on a minimum. And the residual, which is what a solver has, reads it. A least-squares fit of the residual’s logarithm over the last ten steps turned positive on the shallowest saddle, at a hundredth of δ, from step 62, and on every deeper saddle within a dozen steps.

It closed with the case it had not measured. “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 something cheap removes the risk, was “the measurement that would turn this into a test with a stated failure rate.”

A right-hand side can be built to contain none of it #

The system is the earlier essay’s: ten unknowns, four constraints, a Hessian whose reduced form — the curvature left once the constraints have removed their directions, which a minimum the Hessian cannot see separated from the Hessian’s own — has one negative curvature μ and positive curvatures from 0.1 to 5, regularised by δ = 7. Three saddles are measured, at $\mu = -0.01$, $-0.1$ and $-1$, where refinement grows by 1.0014, 1.0145 and 1.1667 a step along the negative direction.

Refinement’s error is multiplied each step by the iteration matrix $G = I - R^{-1}K$, where $R$ is the regularised factor. Its growing eigenvalue is $\delta/(\mu + \delta)$ and every other eigenvalue lies between zero and one. The run starts from the regularised solve, so its first error is $e_0 = (R^{-1} - K^{-1})\,b$, and the component of that error along the growing eigenvector is $w^{\mathsf T}e_0$ for the left eigenvector $w$. That component is linear in the right-hand side: it is $c^{\mathsf T} b$ with $c = (R^{-1} - K^{-1})^{\mathsf T} w$, one fixed vector per saddle. So the right-hand sides that hide the saddle completely are a hyperplane, $c^{\mathsf T} b = 0$, and a right-hand side can be placed any distance from it. Each right-hand side below is a random one with its component along $c$ scaled by $10^{-k}$: $k$ decades of the growing direction removed, from none to sixteen, and then all of it.

In exact arithmetic a right-hand side on the hyperplane never shows the saddle. Its error has nothing in the growing direction to grow, refinement converges to $K^{-1}b$ as if the problem were a minimum, and the residual’s fit is negative for ever.

Each decade hidden costs a fixed number of steps #

The figure at the top of the page is the measurement. On the shallowest saddle the verdict that settled at step 62 with the full share settles at 276 with two decades removed, 570 with four, 1,160 with eight and 1,749 with twelve. The steps between are nearly equal: a least-squares line through the points from two decades to twelve has a slope of 147.3 steps a decade. On the saddle at $-0.1$ it is 80.5 steps a decade and at $-1$, 13.7.

The dial shows the shape of a hidden run. With the full share the residual turns within the first sixty steps and climbs at 1.0014 a step. With eight decades removed it does something the earlier essay never saw a saddle do: it falls like a minimum’s, steadily, for more than a thousand steps, to a relative residual of $4.3 \cdot 10^{-7}$, and only then turns and begins its climb. The fall is the slowest positive curvature’s contraction, 0.986 a step, the rate the earlier essay read off the minimum; the turn is where the growing direction, started eight decades down, finally overtakes it.

That crossover is the whole mechanism, and it is not the one the prediction described. The prediction reasoned about the growing direction recovering its share — climbing back eight decades at 1.0014 a step, which takes about 12,900 steps. But the verdict does not wait for the growing direction to reach its normal size. It waits for the growing direction to pass whatever the residual is otherwise made of, and while it climbs the rest of the residual is falling. Setting a hidden share ε that grows at $g$ equal to a slowest component that decays at $c$,

$$\varepsilon\, g^{t} = c^{t} \quad\Longrightarrow\quad t = \frac{\ln(1/\varepsilon)}{\ln(g/c)},$$

so a decade costs $\ln 10 / \ln(g/c)$ steps.

The figure puts the two predictions beside the measurement. With $c = 7/7.1 = 0.98592$, the slowest contraction the saddle shares with the minimum, the formula gives 147.5, 80.6 and 13.7 steps a decade on the three saddles, against 147.3, 80.5 and 13.7 measured: agreement to a tenth of a per cent. The growth alone gives 1,611, 160 and 14.9. On the deepest saddle the two predictions nearly agree, because a growth of 1.1667 a step dwarfs the contraction. On the shallowest they differ by a factor of eleven, because a growth of 1.0014 a step is a tenth of the contraction’s 0.0141, and the contraction does nine tenths of the work of exposing the saddle.

That inverts the worry. A shallow saddle grows slowly, and that was why the earlier essay feared a hidden one would be hidden for its doubling time many times over. But a slow growth is overtaken by the minimum’s contraction in either case: the verdict is a race between two rates, and on a shallow saddle the faster runner is the one leaving. A stopping test is a race used the same word for the step at which a convergence test fires; here what races is not the run against a tolerance but two directions of the same error against each other.

Rounding finds every hidden saddle #

The rightmost points of the hero figure are the right-hand sides on the hyperplane exactly — none of the growing direction at all. In exact arithmetic they would never show the saddle. In double precision the verdict comes at step 2,723 on the shallowest saddle, 1,102 at $-0.1$ and 181 at $-1$, each within a fifth of the verdict with sixteen decades removed (2,907, 1,103 and 181).

The reason is that the hyperplane is a property of exact vectors. Every correction refinement adds is rounded, and the rounding error has a component along every eigenvector of $G$, the growing one included, at every step. So the growing direction is reseeded continually at the level of the unit roundoff times the current iterate, whatever the right-hand side was, and a share below that level behaves like a share at it. The floating-point iteration cannot be hidden from by more than about sixteen decades: an exact zero along one direction is not something a rounded iteration can keep.

So in double precision there is a worst right-hand side, and its delay is finite and predictable: sixteen decades times $\ln 10 / \ln(g/c)$, or about 2,400 steps on the shallowest saddle — measured, 2,723. The earlier essay’s test has a stated worst case after all.

A hidden saddle converges first #

What the worst case means for a solver is not the delay. It is what the residual does during the delay.

While the growing direction is below the rest of the residual, refinement converges, and it converges to the right answer: $K^{-1}b$ exists, the system is nonsingular, and the iterate approaches it at the minimum’s rate. On the shallowest saddle each decade hidden lets the residual fall about nine tenths of a decade further before the turn — the ratio of the contraction’s logarithm to the race’s, $\ln c / \ln(g/c) = -0.91$ — from 0.12 with two decades removed to $4.3 \cdot 10^{-7}$ with eight and $1.0 \cdot 10^{-10}$ with twelve. With the direction removed exactly, the residual reaches $2.6 \cdot 10^{-13}$ at step 2,160 before the rounding-seeded growth turns it.

Any stopping test above that floor stops first, and the reading that never moves is the reminder of how little a stopping residual says about what was achieved: it reports the same figure whatever lies behind it. A refinement loop with a tolerance of $10^{-12}$, which is a demanding one, would end on that right-hand side about a hundred steps before the turn, report a solution correct to twelve digits, and have seen a residual history that fell monotonically for two thousand steps. Everything about the run says minimum. The linear system has been solved correctly — that is not in question — and the second-order verdict the run was supposed to carry has been lost, because the verdict needs the run to continue past the point at which every sensible solver stops.

On the saddle at $-0.1$ the floor is $4.2 \cdot 10^{-7}$, so a tolerance of $10^{-6}$ is fooled and one of $10^{-12}$ is not. On the saddle at $-1$ the growth is fast enough that the residual never gets below 0.14, and nothing is fooled. The hiding is dangerous exactly where the earlier essay’s test was weakest, on saddles much shallower than δ.

A shift that certifies a saddle made the point that the pivot signs of a regularised factorisation answer the wrong question confidently, and an eigenvalue count that cannot be slightly wrong is why that confidence is persuasive: a count is an integer and is either exactly right or wrong by a whole eigenvalue. A refinement loop on the worst right-hand side does the same thing by a different route, and its confidence is a converged residual rather than an integer.

How close random right-hand sides come #

The constructed right-hand sides are a worst case. The question the earlier essay asked is how often an ordinary one approaches it. Four hundred normally distributed right-hand sides, on the saddles at $-0.01$ and $-0.1$, answer it with a distribution.

The right-hand side the earlier essay measured, which gave the verdict at step 62, was a typical draw but not a lucky one. Over four hundred on the shallowest saddle the median verdict is step 50; one in ten takes more than 132 steps, one in a hundred more than 239, and the slowest 417. On the saddle at $-0.1$ the median is 11, one in ten past 34 and the slowest 190. On the saddle at $-1$ every one of them settles by step 28.

The figure shows where the slow ones come from. The share of the growing direction in a random right-hand side is the cosine between two vectors in fourteen dimensions, with a median of 0.20; one draw in a hundred has less than 0.012 and the smallest of four hundred has $7.3 \cdot 10^{-4}$. The verdicts’ upper edge follows the dashed line, the median verdict plus 147 steps for each decade the share falls below the median: the slowest draws are exactly the ones nearest the hyperplane, two and a half decades below the median at worst, and they pay the same price a decade as the constructed ones. Below the edge the scatter is the other directions’ shares, which decide how much of the residual the growing direction has to overtake.

What matters for a solver is that no random draw comes near the converged-looking floor. The lowest residual any of the four hundred reaches before turning is 0.030 on the shallowest saddle and 0.30 on the next. A random right-hand side delays the verdict — by up to eight times the median on these draws — but it does not make a saddle look converged. Only a right-hand side within about eight decades of the hyperplane does, and a random one lands that close with probability of order $10^{-8}$.

Which leaves the case a random draw does not cover: right-hand sides that are not random. A right-hand side assembled from a model’s structure — a load that is symmetric when the saddle’s direction is antisymmetric, a constraint residual that is zero by construction — can sit on the hyperplane exactly, for the same reason that a structured problem’s eigenvector can be orthogonal to a structured starting vector. The earlier essay’s test needs a guard that does not assume the data is random.

A kick to the starting point #

The guard the earlier essay suggested was a random perturbation of the right-hand side, which costs one extra solve. A cheaper one is available, and it follows from where the hiding lives. The growing direction’s share is fixed by the starting error, and the starting error is the regularised solve minus the answer. Adding a random vector to the starting point adds a random share of every direction to the starting error, without changing the right-hand side, the fixed point or the cost of a step. On a minimum the extra error contracts like any other; on a saddle the kick’s share of the growing direction grows.

The figure is the hidden right-hand side, refined from a start kicked by a random vector whose norm is a fraction of the regularised solve’s. A kick of $10^{-12}$ is below the rounding’s own reseeding at first and moves the shallowest saddle’s verdict only from 2,723 to 2,099. Each further four decades of kick remove about 600 steps — 1,479 at $10^{-8}$, 890 at $10^{-4}$ — and a kick the size of the solve itself gives the verdict at step 224, inside the random right-hand sides’ slowest one in a hundred (239). On the saddle at $-0.1$ the full kick gives step 22, and at $-1$ step 12.

The cost on a minimum is nothing measurable. The same system with every reduced curvature positive reaches a relative residual of $10^{-12}$ in 2,070 steps from the regularised solve and in 1,936 from the kicked start: the kick’s extra error is spread over every direction, most of which contract fast, and on this draw it happened to cancel part of the slow one. The kick turns the worst right-hand side into a random one, and it does so for the price of one random vector.

The perturbation that does the work measured refinement removing a regularisation along each curvature at its own rate. A kicked start is that measurement used as a probe: it puts something in every direction so that the rates can be read, rather than relying on the data to have done so.

What the test can now promise #

The earlier essay’s verdict becomes a test with numbers on it. On this system, with the residual’s ten-step fit as the rule, a kicked start and a saddle at a hundredth of δ, the verdict settles by the random right-hand sides’ distribution — median 50 steps, one in a hundred past 239 — whatever the right-hand side, because the kick’s share is a random one’s. Without the kick the same holds for random right-hand sides and fails for structured ones, by up to 2,700 steps, and in the failing case the run looks converged long before it looks like a saddle. With the kick the worst case is the random case.

What it cannot promise is a verdict from a run that stops at its tolerance. A second-order test read off refinement needs the run to continue until its rate is readable, and on a minimum that is long after the answer is good enough. Small compared to what asked what a residual is small relative to; here the question is what a residual history is long relative to, and the answer is the race between the saddle’s growth and the minimum’s slowest contraction, $\ln 10 / \ln(g/c)$ steps for every decade the data happens to hide.

What one system does not show #

One saddle-point system, ten by ten with four constraints, at one regularisation, with three depths of saddle and a single negative curvature each. A saddle with two negative curvatures has a two-dimensional growing subspace and a codimension-two set of hiding right-hand sides, which a random draw approaches more rarely and a structured one can still reach. The slowest contraction here is set by a positive curvature of 0.1; a minimum with a smaller one contracts more slowly, which makes each decade of hiding cost more steps and the converged-looking floor shallower. The verdict rule is the ten-step fit of the earlier essay; a longer window settles later on every right-hand side by about the same number of steps, so the delays above are differences that do not depend on it. And the kick is a random vector of the solve’s own size; a smaller kick is cheaper on nothing and slower on a saddle, so there is no reason measured here to use one.

Still open: two directions, a Krylov reading, and a kick that is not random #

Two negative curvatures. With a two-dimensional growing subspace the hiding set is the intersection of two hyperplanes, and the verdict comes when either direction overtakes the contraction. The prediction with a sign is that the delay a decade is set by the faster-growing of the two, and that a structured right-hand side hiding only the faster one is delayed by the slower one’s race, $\ln 10 / \ln(g_2/c)$ a decade — so a second negative curvature shortens the worst case rather than lengthening it.

A Krylov method instead of refinement. The earlier essay’s second open question stands and the hiding sharpens it. A Krylov method preconditioned by the regularised factor builds its subspace from the right-hand side, so a right-hand side on the hyperplane gives it no component along the growing direction to find, and rounding reseeds it only slowly because a Krylov basis is reorthogonalised. Whether a Krylov method is hidden from for longer than refinement, and whether the same kick protects it, is one more sweep over the same systems.

A kick that is not random. The kick works because its share is a random one’s, and one draw in a hundred is still slow. A deterministic kick — the regularisation’s own correction direction, or the eigenvector of the last few Ritz values — might do better than random by aiming at the slowest-growing directions, and the measurement is whether any such kick brings the slowest of four hundred right-hand sides to the median.