The certificate that arrives soonest is worth least

A direction of negative curvature is cheap and it proves something. The division that cannot be done is the account of how it arrives: conjugate gradients divides by pᵀAp at every step, on a Hessian that is not positive definite that number eventually comes out non-positive, and the direction the iteration was about to divide by is a vector anybody can check in one further matrix–vector product.

What it is not is a step. Along that direction the quadratic model ½xᵀAx − bᵀx falls without bound, so there is no distance to move and nothing finite to compare a move against. A trust-region method supplies both by refusing to trust the model beyond a ball of radius Δ around the current point. Inside that ball the subproblem has an answer; it is finite because the ball is bounded, and the cheap step can be scored against it.

Scoring it needs the answer, and the answer is expensive. It comes from a full symmetric eigendecomposition of the Hessian, followed by a search for the shift σ at which the solution of (A + σI)x = b has norm exactly Δ, which here is a bisection on the secular equation carried to two hundred halvings. Steihaug’s method is conjugate gradients with two extra tests — one for leaving the ball, one for the curvature going non-positive — and it stops at whichever fires first, having spent a handful of products and nothing else. The ratio of the two model decreases is what the cheap step is worth, and this essay is about how that ratio moves.

It moves against the eigenvalue, and it moves the wrong way. At the smallest radius drawn the share runs 89.8, 89.7, 89.2, 83.2 and 39.6 per cent as λ_min goes from −10⁻³ to −10 — a factor of 2.3, across the same five Hessians on which the certificate arrives after nine, eight, six, four and two products. The sharper the indefiniteness, the sooner it is proved and the less the proof is worth.

Two products, and a factor of two in what they buy #

The five Hessians differ in one number. Each is 40×40 with a spectrum spread over one decade from 1 to 10, and each has a single eigenvalue moved to −λ; the right-hand side is the same unit vector in all five. That construction is deliberate, because it makes the negative eigenvalue the smallest in magnitude as well as the only negative one, which is the case a factorisation with nothing to pivot for finds last and a spectrum plot does not draw attention to.

At Δ = 0.25 the exact subproblem’s model decrease is −0.13808, −0.13819, −0.13930, −0.15321 and −0.38952 across the five. Steihaug’s is −0.12394, −0.12397, −0.12428, −0.12747 and −0.15437. Both columns rise as the eigenvalue gets more negative, which is expected — a more negative eigenvalue makes more decrease available inside the same ball — but they do not rise together. The exact decrease grows by a factor of 2.82 across the sweep and the truncated one by 1.25. The share is the quotient of those two growths, and it falls because the available decrease outruns what a truncated conjugate-gradient path can reach.

The cost of reaching it does not move at all. At Δ = 0.25 every one of the five stops after two matrix–vector products: the region is small enough that the first full step leaves it, so the iteration takes one step, finds the boundary on the second, and stops. Two products buy 89.8 per cent of the available decrease on the mildest Hessian and 39.6 per cent on the sharpest. Nothing in the count distinguishes them, and nothing a caller can see at the moment of stopping distinguishes them either.

That is the inversion this essay is named for. The arrival of the certificate is governed by which eigenvalues a Krylov space finds first, and it finds large ones first — so a Hessian with an eigenvalue at −10 hands over a proof after two products and one at −10⁻³ takes nine, a spread the essay that first priced the certificate records as the reassuring direction for the detection to run in. The worth of the step is governed by something else entirely, and it orders the same five Hessians in the opposite direction.

What the exact answer is made of #

The share falls because the exact answer changes what it is made of, and that is measurable rather than inferable.

Take the eigenvector v of the negative eigenvalue — available here because these Hessians are small enough to decompose, and unavailable in any setting where the method would actually be used. At Δ = 0.25 the cosine between v and the exact subproblem solution runs 0.618, 0.619, 0.635, 0.759 and 0.968 across the five. On the mildest Hessian the exact step is mostly not the eigenvector; on the sharpest it is almost exactly the eigenvector and nothing else.

The same reading from the other side. Moving from the origin to the boundary of the ball along ±v alone, and taking the better of the two signs, obtains 33.9, 34.1, 35.8, 51.0 and 92.2 per cent of the exact decrease. So at λ_min = −10 the entire subproblem is one eigenvector followed to the edge, and everything else the model knows is worth eight per cent of the answer. At λ_min = −10⁻³ the same direction is worth a third, and the other two thirds are an ordinary well-conditioned quadratic minimised over a small region — which is precisely the problem the rate the condition number predicts is about, and precisely what a truncated conjugate-gradient path is good at.

And the certificate direction is a good stand-in for v exactly where v does not matter. Its cosine against v runs 0.9998, 0.9985, 0.9773, 0.8547 and 0.7032 across the same five, in the same order — nearly the eigenvector when the eigenvalue is a thousandth, and seven-tenths of it when the eigenvalue is ten. That is the whole mechanism in two rows of numbers. The alignment the exact answer needs climbs from 0.618 to 0.968; the alignment the certificate supplies falls from 0.9998 to 0.7032. The two lines cross, and the share is what is left over.

The reason is not mysterious and it is worth stating in the vocabulary of the gap decides the eigenvector. At λ_min = −10⁻³ the Krylov space has to run nine products before any direction in it sees the negative eigenvalue at all, and the direction it finds when it does is separated from everything else in the spectrum by a factor of a thousand, so it is an eigenvector to four digits. At λ_min = −10 the space meets a non-positive curvature on its second direction, before it has resolved anything, and what it hands over is a proof of indefiniteness computed from a subspace of dimension two.

The cost runs the other way #

Read along the radius rather than at one radius, and the products tell the opposite story to the shares.

The most expensive stop in each of the seven-radius sweeps costs 8, 7, 6, 4 and 2 products as λ_min goes from −10⁻³ to −10. That is the same ordering as the detection cost and the reverse of the share, so the Hessian whose sweep is cheapest to run is the one whose steps are worth least, at every radius drawn. There is no radius anywhere in the five sweeps at which a more negative eigenvalue bought a larger share for more work.

Counted in products rather than in operations, because at the sizes where any of this is done the operator has no entries and a product is the only unit there is. Against that, the exact answer costs a symmetric eigendecomposition — cubic in n, requiring the Hessian to exist as a stored array, and here computed by cyclic Jacobi rotations to full accuracy — plus two hundred bisection steps on the secular equation, each of which forms an n-vector. Eight products against that is the trade the whole method exists to make, and the measurement above says the trade is best exactly where the eight products are needed.

Where the curve changes character #

A single number at a single radius is not the curve, and the curves differ in kind rather than in degree.

The reason the step stops is either the boundary or the curvature, and which one it is moves along the radius. The crossover — the smallest radius at which the curvature fires before the ball is reached — sits at Δ = 0.25 for λ_min = −10, Δ = 1 for −1, Δ = 4 for −0.1, and nowhere in the drawn range for −10⁻² or −10⁻³. Below the crossover the truncated path is an ordinary conjugate-gradient path that ran into a wall; above it, the step is one direction of negative curvature followed to the edge.

Those two regimes have different shapes and it is visible without reading a number off the axis. Where the curvature stops every step, the share is nearly flat: 39.6 falling to 35.2, a drop of thirteen per cent across a sixty-fourfold increase in the radius, because the same direction is being followed to a further boundary and it is competing against an exact answer that is also mostly that direction. Where the boundary stops every step, the share falls: 89.8 to 68.3 at λ_min = −10⁻³, and 89.7 to 40.8 at −10⁻². The fall is not even monotone at the mildest eigenvalue, where 61.0 per cent at Δ = 8 is followed by 68.3 at Δ = 16 — the exact subproblem’s own answer has begun to swing towards the eigenvector there while the truncated path is still improving, and asserting a monotone fall on that sweep would be asserting something the measurement does not show.

The practical half of this is about where a trust-region method spends its time. The radius shrinks when the model has predicted badly and grows when it has predicted well, so a method in difficulty is a method at small radii, and small radii is where the shares above are largest. That is the standard argument for the method and it survives this essay intact. What does not survive is the version of it that quotes a single number: “the truncated step gets about ninety per cent” is true at Δ = 0.25 on three of the five Hessians here and false by a factor of more than two on the fifth.

The size moves the crossover and not the ordering #

The five sweeps above hold n at 40, which invites the question of whether any of it is about the matrix rather than about the eigenvalue.

Holding λ_min at −0.1 and moving n, the share at Δ = 0.25 is 81.6 at n = 20, 89.2 at 40 and 94.9 at 60, and at Δ = 16 it is 11.8, 36.9 and 30.1. The first row is a narrow band and the second is not a band at all. The small-radius share across every sweep drawn in this essay, at five eigenvalues and four sizes, lies between 81.6 and 94.9 per cent; the large-radius share over the same set runs from 6.5 to 68.3. One of those two numbers is a property of the method and the other is a property of the particular sweep it was measured on.

The crossover moves with n as well, and in the direction the mechanism predicts: at λ_min = −0.1 the curvature first stops the step at Δ = 16 when n = 20, at Δ = 4 when n = 40 and at Δ = 2 when n = 60. A larger matrix has more directions between the right-hand side and the negative eigenvalue, so the iteration takes more steps before it meets one — which pushes the boundary crossing earlier in the sequence and the curvature crossing earlier in the radius. The most expensive stop over those three sweeps is 8, 6 and 8 products, which is the flatness in n that a Krylov space finds the extremes of a spectrum regardless of what it sits inside measures directly.

The pair at λ_min = −1 makes the same point more sharply. At n = 30 the small-radius share is 82.0 and at n = 40 it is 83.2 — a difference of a point. At Δ = 16 the same two sweeps read 6.5 and 29.3, a factor of four and a half. The ordering by eigenvalue is stable across all of it: at Δ = 0.25 the sharpest Hessian is worst on every size measured, and the mildest is best.

What the certificate does and does not decide #

Two quantities have been moving through this essay and only one of them is a property of the Krylov space.

The arrival time is set by where the negative eigenvalue sits in the spectrum. It is monotone, it runs from three products to nine over three and a half decades of λ, and it barely notices the size of the matrix. The worth of the step is set by how much of the bounded subproblem’s answer that one direction accounts for, and that is a fact about the subproblem — its radius, its right-hand side and the whole spectrum — rather than about the direction. The two happen to be governed by the same eigenvalue, and they are governed by it in opposite senses.

So the certificate decides that a step exists and does not decide what the step is worth. It is a proof of indefiniteness, checkable from outside in one product, and an estimate of λ_min is exactly what it is not — the quotient it arrives at recovers between twelve and forty-two per cent of the eigenvalue across the family. A method that read the quotient as a curvature and scaled a step by it would be scaling by a number wrong by a factor of three and inconsistently so; a method that reads the arrival time as a measure of how bad the point is would have the ordering exactly backwards.

What follows for a code that uses it #

Do not report the share without the radius. The single number this essay could be summarised by is 89 per cent, and it is a small-radius number. The same method on the same Hessians at Δ = 16 reads between 6.5 and 68.3, and a trust-region method at a large radius is a method whose model has been predicting well, which is when the step matters most in absolute terms.

Do not read a fast certificate as a good one. The Hessians on which the proof arrives in two products are the ones whose exact answer is an eigenvector, and an eigenvector is what a two-dimensional Krylov space does not have. The correct inference from a fast arrival is that the optimiser should leave, not that the direction it is leaving along is a good one.

Take the eigenvalue seriously as a mode, not as a magnitude. At λ_min = −10 the exact subproblem is 92.2 per cent one eigenvector, so the honest description of that step is an eigenvector computation with a radius attached, and there are cheaper ways to approximate an eigenvector than a truncated linear solve — the ones a Krylov space for a problem that is not linear builds when there is no matrix to build one from.

And the alternative is not the exact subproblem. It is a modified Hessian: add a multiple of the identity until the model is convex and solve that, which is the same move a constraint is a weight at infinity prices in the least-squares setting and the same one where the answer stops being in the data reaches for when a problem is too ill-posed to answer as posed. That route never meets the event and never follows the direction, so it is not on the curve above at any radius. It answers a different subproblem and reports the answer as though it were this one.

The condition number decides nothing here, which is worth saying because the condition number is an amplifier in every neighbouring setting on this site. All five Hessians have a positive part spread over exactly one decade; what separates their shares by a factor of 2.3 is the sign and size of a single eigenvalue that κ, being a ratio of magnitudes, cannot see. A symmetric matrix is not thereby a definite one, and when symmetry is not enough is the account of how little symmetry alone promises.

And the zero that stops the iteration means something different in each of its neighbours. The non-positive pᵀAp here is an output; the one that ends a biorthogonal recurrence in the same zero, and nothing was found is a loss of contact between two sequences with nothing recovered.

The refusal #

Every number in this essay is a share, and a share needs a denominator that exists.

The claim the refusal is fed is the one a reader is most likely to arrive at from the certificate alone: that the negative-curvature direction is where the decrease comes from, so following it is what produces the step and the radius is an implementation detail. It is not. Along that direction the model has no minimum and no finite value to be a share of; the region is what creates the quantity the whole comparison is about.

Posed with no region at all, the exact route returns a solution of norm 8.27·10⁻¹³ at a secular shift of 1.21·10¹², with a model decrease of −8.27·10⁻¹³ — which is not a decrease but the size of the bisection’s own residual, since at Δ = 0 the answer is the origin and the model’s value there is zero. The truncated route returns exactly zero. The share of one by the other is zero divided by a rounding, and the assertion that a trust region of radius zero admits a model decrease is fed that subproblem and required to reject it.

That refusal is small and it is the load-bearing one for everything above. 89.8 per cent and 39.6 per cent are not two measurements of a direction. They are two measurements of what a direction is worth inside a region, and the region is doing half the work in both.