One hyperplane hides nothing

The right-hand side that hides the saddle measured how a second-order test can be delayed. Iterative refinement against an unregularised saddle-point matrix, correcting with a factor regularised by δ past the Hessian’s most negative eigenvalue, multiplies its error along each reduced curvature μ by $\delta/(\mu + \delta)$ every step — above one on a saddle, below one on a minimum — and the residual shows which. On one negative curvature the verdict comes when the growing direction’s share of the residual overtakes the slowest contracting one’s. A right-hand side can be built with that direction removed, and each decade removed delays the verdict by $\ln 10 / \ln(g/c)$ steps, the growth $g$ measured against the slowest contraction $c$ — 147 steps a decade on the shallowest saddle, until rounding caps the hiding near the unit roundoff and gives the verdict anyway.

Its last section asked what changes with two growing directions. “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.”

The first and last clauses are right. The middle one confuses hiding a direction with leaving it in view, and the difference is the whole of what a second curvature does.

Two growing directions, and two left partners #

The system is the earlier essay’s: ten unknowns, four constraints, regularised by δ = 7 in the Hessian block and $10^{-8}$ in the zero block — the regularisation the regularisation that legalises every order introduced to make every elimination order factorise. Its reduced Hessian — the curvature left once the constraints remove their directions, which a minimum the Hessian cannot see separated from the Hessian’s own — now has two negative curvatures $\mu_1 < \mu_2 < 0$ and positive ones of 0.1, 3, 4 and 5. Three pairs are measured: $-1$ and $-0.1$, $-0.1$ and $-0.01$, and $-1$ and $-0.01$. Along them refinement grows by 1.1667, 1.0145 and 1.0014 a step, and the slowest positive curvature contracts by 0.9859.

Refinement’s iteration matrix $G = I - R^{-1}K$ now has two eigenvalues above one, and both are measured directly: the two dominant eigenvectors of $G$ and of its transpose are found together, and their eigenvalues agree with $\delta/(\mu + \delta)$ to the size of the zero block’s regularisation. A right-hand side’s starting share along growing direction $i$ is $c_i^{\mathsf T} b$, where $c_i$ comes from the left eigenvector, exactly as in the single case — linear in $b$, so each direction has its hyperplane of right-hand sides that contain none of it.

Hiding one direction is then a precise operation: remove from $b$ a vector that sets one share to $\varepsilon$ times its random value and leaves the other share exactly where the random draw put it. Hiding both sets both shares to $\varepsilon$ times theirs. The verdict is the earlier essays’ windowed one: the step from which a least-squares fit of $\log \|r\|$ over the last ten steps stays positive to the end of the run.

Hiding both costs the faster direction’s race #

The figure at the top of the page is the pair $-0.1$ and $-0.01$. With both directions hidden, the verdict moves from step 12 with nothing removed to 110, 270, 431 and on to 1,068 at fourteen decades, a straight line on the scale of decades at 80.5 steps a decade. The faster direction’s own race, $\ln 10/\ln(1.0145/0.9859)$, is 80.6. The slower one’s would have been 147.5, and it never shows.

On all three pairs the measured slope is the faster direction’s race to half a per cent: 13.61 against 13.68 where the faster curvature is $-1$, and 80.50 against 80.58 where it is $-0.1$. That is the prediction’s first clause, and the reason is the one it gave. Both hidden shares start at the same $\varepsilon$; both must overtake the same contraction; the faster growth gets there first by a margin that widens with every decade, and once it has overtaken, the residual is growing and the verdict is given, whatever the slower direction is doing.

The two pairs that share a faster curvature of $-1$ give the same line to the step, at 13.61 a decade, one with $-0.1$ as the slower and one with $-0.01$. The slower curvature is a spectator whenever both are hidden equally.

Hiding one hides nothing #

The prediction’s middle clause said that hiding only the faster direction would leave the slower to win the race, $\ln 10/\ln(g_2/c)$ a decade. Measured, hiding only the faster direction on the pair $-0.1$ and $-0.01$ gives the verdict at step 12 at every share from one to exactly zero — the same step as a right-hand side with nothing hidden. On $-1$ and $-0.01$ it gives it between step 10 and step 12. The slope is zero.

The residual histories say why. With six decades removed from both directions the residual falls for four hundred steps like a minimum’s before it turns, and the verdict settles at step 431. With six decades removed from the faster direction only, the residual turns upward at once and the verdict settles at step 12; from the slower only, at step 21. The direction left in view starts at its random share, and a random share is not a small number to recover from: it is already larger than what the contracting directions will have left after a dozen steps. The race the prediction priced is the cost of recovering a share that was removed. A direction whose share was never removed pays no race at all.

The dial makes the point with the number of decades. At two decades, ten or fourteen, the curves for one hidden direction do not move; only the curve with both hidden walks to the right, 80 steps for every decade the dial adds.

The asymmetry between the two single hidings is small, and it is not the growth rates’. The two random shares on this right-hand side are nearly equal, 0.35 and 0.33 of what a perfectly aligned one would have, and yet the verdict with only the faster in view comes nine steps later than with only the slower. The verdict reads the residual, not the error, and a direction’s weight in the residual depends on how the matrix maps it as well as on how fast it grows; for the first dozen steps the contracting directions dominate both, and which growing direction surfaces first is decided inside that noise. Nine steps is the whole of the effect, beside the 1,127 that hiding both can buy.

So the hiding set of the earlier essay’s question — “the intersection of two hyperplanes” — is not a refinement of one hyperplane. It is the only set that hides anything. A right-hand side on one hyperplane and not the other is, for refinement’s verdict, exactly as visible as a random one.

Even a small lead decides it #

The prediction left room for a gentler outcome when the two curvatures are close: two races within a tenth of each other, the faster winning by a margin that takes many decades to show, and a slope somewhere between the two over any practical number of decades. Two more pairs test it, $-0.02$ and $-0.01$, whose races are 135.1 and 147.5 steps a decade, and $-0.012$ and $-0.01$, whose races differ by two per cent, 144.8 and 147.5.

There is no in-between. With both directions hidden the verdict moves 87, 136, 136.5, 135.5, 135.5, 135 and 132.5 steps for each further decade on the first pair, a slope of 135.7 against the faster race of 135.1, and on the second pair 145.7 against 144.8. The figure above shows the both-hidden line lying along the faster single saddle’s dashed line from the second decade on, and nowhere near the slower one’s. The reason is that both hidden shares start at the same $\varepsilon$, so the faster direction is ahead from the first step and stays ahead; the size of its lead changes how long the opening takes, not who wins. What would make the slower direction matter is a right-hand side that hides the faster one more — and that is a right-hand side hiding one direction, which buys a fixed number of steps.

The close pairs do make the single hidings less symmetrical. On $-0.02$ and $-0.01$ a right-hand side with nothing hidden gets its verdict at step 45 — later than on the separated pairs, because two growing directions this alike can partly cancel in the residual for a while. Hiding the faster direction removes the cancellation and the verdict comes at step 12; hiding the slower leaves the faster to surface alone and it comes at step 79. Both are the same at every share from two decades to exactly zero. Neither is a race.

The worst case is the faster curvature’s #

The longest delay on a pair is the longest delay its faster curvature can produce alone. Hiding both directions of $-0.1$ and $-0.01$ peaks at 1,127 steps, against 1,105 for a single saddle of $-0.1$; of $-1$ and $-0.1$ at 193 against 188; of $-1$ and $-0.01$ at 199 against 188. Against the slower curvature alone the pair is far quicker: 1,127 steps against 2,907 for $-0.01$, and 199 against 2,907 when the faster is $-1$. That is the prediction’s last clause, and it holds because the first does: the price per decade is the faster’s, and the decades run out at the same place — the unit roundoff, where rounding puts back a share of order $u$ along every direction at every step, as the earlier essay found for one.

The few steps by which each pair exceeds its faster single saddle are the slower direction’s contribution to the residual during the turn: it is growing too, more slowly, from the same tiny share, and it adds a little to what the windowed fit has to see past. It never adds more than twenty-two steps in eleven hundred.

Random right-hand sides need both shares small #

The earlier essay found that random right-hand sides on one saddle spread the verdict: on the shallowest, a tenth of four hundred took more than twice the median and the slowest took 417 steps, more than six times the 62 that a single right-hand side had suggested. On a pair, a slow verdict needs the right-hand side to be close to both hyperplanes at once.

On the pair $-0.1$ and $-0.01$ the same four hundred draws give a median verdict at step 12, a ninetieth percentile at 22, a ninety-ninth at 74 and a slowest at 79. On a single saddle of $-0.1$ they give 11, 34, 92 and 190, and of $-0.01$ 50, 132, 239 and 417. The pair’s tail is shorter than either of its curvatures’ alone. The other two pairs are shorter still — slowest at 13 and 15 steps — because their faster direction grows by a sixth a step and overtakes the contraction from almost any share.

The filled dots are where the slow draws sit: towards the small end of the faster share, and never at the large end of the slower. A draw with little of the faster direction is rescued by the slower unless it happens to have little of that too, and four hundred draws contain few such. The single-saddle tail came from one share being small by chance; the pair’s needs two, and two small shares by chance is rarer than one.

What a solver can take from this #

The earlier essay turned refinement’s verdict into a test with a stated failure rate: on a saddle as shallow as a hundredth of δ, a random right-hand side gave the verdict by step 417 in four hundred draws, and a kick to the starting point bounded the hidden case near that. A second negative curvature changes both numbers in the solver’s favour. The worst case is the faster curvature’s, so a test sized for a single saddle at the shallowest curvature it must detect is sized correctly for any saddle with an additional, deeper direction. And the random tail is shorter, so a step budget that detects one shallow direction with a stated probability detects a pair with a better one.

The case the test still has to fear is the single shallow direction, alone. That is not a comfortable conclusion for a nonconvex solver, which meets its shallowest saddles near the end of a run, where the curvature is small and often of one sign but one direction. But it is the conclusion: depth in some other direction does not make a saddle harder to see. The pivot count has the opposite failure: a constraint the count stops seeing found it losing a nearly redundant constraint six decades before any rank test would, and the residual’s verdict, which reads the iteration rather than the factor, is not exposed to that at all. A shift that certifies a saddle found the pivot signs blind to every saddle shallower than δ; refinement’s residual sees all of them, and the more of them a saddle has, the sooner.

The residual turns before the error doubles said the verdict comes when the growing direction overtakes the decaying one. With two growing directions the statement becomes: when the first of them does. Every result above is that sentence and the fact that a share not removed is a share already large.

What five pairs do not show #

One constrained problem of ten unknowns, its positive curvatures fixed, δ fixed at 7, five pairs of negative curvatures, and every hiding right-hand side built from one random draw with both hidden shares scaled alike. A right-hand side that hides the two directions by different amounts — eight decades from the faster, four from the slower — would be decided by whichever share recovers first, and the verdict would follow the slower direction’s race over the decades where it leads; that is a statement about two hidden shares, and it needs both hyperplanes approached at once. A pair in which the faster curvature’s random share is orders of magnitude below the slower’s is the only way one hidden direction could matter, and it would matter by that share’s recovery, not by a race. The positive curvatures’ smallest, 0.1, sets the contraction for every pair; the perturbation that does the work is the account of how the zero block’s regularisation would move it. Three negative curvatures are not measured.

Still open: a Krylov reading, a kick that is not random, and two curvatures that nearly agree #

A Krylov method instead of refinement. The earlier essay’s second question stands. A Krylov method preconditioned by the regularised factor builds its basis from the right-hand side, so a right-hand side on both hyperplanes gives it nothing along either growing direction, and rounding reseeds it slowly because the basis is orthogonalised. The prediction with a sign is that a hidden right-hand side delays a Krylov method’s detection — the first negative Ritz value of the preconditioned operator — by more steps a decade than it delays refinement, and that hiding one direction delays it not at all, as here.

A kick aimed at the slowest directions. The kick to the starting point works because its share along each growing direction is a random one’s. A deterministic kick along the regularisation’s own correction direction, or along the last few Ritz vectors, might put more weight on the shallow direction than a random one does. The measurement is whether any such kick brings the slowest of four hundred hidden right-hand sides on a single shallow saddle to the median.

A third curvature. With three negative curvatures the argument above predicts that the fastest sets the price a decade, that any two hyperplanes of the three hide nothing, and that the worst case is again the fastest curvature’s alone. The case worth measuring is the one the inertia-correcting loop of the shift that stops at the first right count meets: one shallow curvature and two deep ones, where a right-hand side hiding the two deep directions leaves the shallow one in view — and the prediction is that its verdict then comes at the shallow direction’s open step, not at any hidden one’s.