Where the guarantee stops

Three rungs of this ladder are about what convexity gives: chords above, lines below, a description by tangents, and — the practical consequence — that a method which only moves downhill lands on the right answer.

This rung is about the other side. Without convexity, none of it holds, and the failure is not a degradation. A local minimum of a non-convex function can be arbitrarily worse than the global one, and nothing local distinguishes them.

How bad it can be #

The gap between a local minimum and the global one is unbounded, and demonstrating that is one line: take any convex function with its minimum at the origin, add a narrow dip at some distant point, and make the dip as deep as one likes. The original minimum is still a local minimum, the dip is the global one, and the difference is whatever was chosen.

So no statement of the form “a local minimum is within a factor of the global one” is available. That is worth being clear about because a great many practical claims are of that form and they are all claims about particular problems rather than about non-convexity. A paper reporting that a method’s local answers are good is reporting a fact about its problem family, and the fact does not transfer.

Worse, finding the global minimum of a general non-convex function is hard in the technical sense. Deciding whether a quartic polynomial in many variables takes a negative value is NP-hard, and quartics are as simple a non-convex family as exists — a quadratic is either convex or unbounded below, so quartics are the first interesting degree. There is therefore no general algorithm anybody expects to find, and the hardness is not about pathological functions but about polynomials of degree four.

And worse again: even deciding whether a given point is a local minimum is hard for a general function of several variables. It requires knowing that a certain matrix is positive semidefinite throughout a neighbourhood, and for a quartic that is itself an NP-hard question — so the difficulty is not confined to the search, it reaches the verification.

That last point is the sharpest statement of what convexity provided. Under convexity, verifying an answer is a supporting line, checkable in one step. Without it, even the local question has no cheap certificate, and an optimisation’s output is a number with nothing attached.

The obstruction is not always a local minimum #

The picture of a landscape with several valleys is the standard one and it is misleading for high dimensions, where the obstructions have a different character.

Saddle points outnumber minima enormously. At a critical point of a function of $d$ variables, the matrix of second derivatives has $d$ eigenvalues, and a minimum needs all of them positive. For a randomly chosen critical point that is exponentially unlikely — the eigenvalues of a typical symmetric matrix are spread over both signs — so the overwhelming majority of critical points are saddles with at least one direction going down. The critical points that are minima also tend to be the low ones, which is a second and independently useful fact.

A saddle is not a trap for a method that can see it, since some direction decreases. It is a trap for a method that stops when the gradient is small, because the gradient is small at a saddle and the escaping direction may be very shallow. Most of the practical difficulty in high-dimensional optimisation is saddles rather than minima.

And the useful consequence is that the guarantee can be partly restored. Methods with a little randomness escape saddle points, provably and in a number of steps depending only polynomially on the dimension, so “converges to a point where the gradient vanishes” can be upgraded to “converges to a local minimum” without convexity. That is a genuine theorem, it was proved in the 2010s and is one of the field’s recent successes, and it is a long way short of finding the global minimum.

Setting the working case beside the failing one makes the character of the loss clear, and it is worth naming because it is unusual.

Most mathematical properties degrade. A function that is nearly continuous behaves nearly like a continuous one; a matrix nearly of rank one behaves nearly like one. Convexity does not degrade: a function that is convex except on a small interval has, on that interval, no supporting line, no certificate, and possibly a local minimum that is not global. The size of the non-convex region bounds nothing.

That is why the conditions below are separate hypotheses rather than approximate versions of convexity. There is no useful notion of “nearly convex” that buys a weakened guarantee, and the search for one is a recurring and so far unsuccessful line of work.

What partially replaces convexity #

Several weaker conditions each buy back part of the guarantee, and knowing which buys what is the practical content of the subject.

Quasi-convexity asks that every sub-level set be convex — that $\{x : f(x) \le t\}$ is a convex set for each $t$. It is weaker than convexity, it still gives that a local minimum is global, and it is what a great many economic models actually assume. It does not give that a downhill method converges quickly, and it is not preserved by addition — the sum of two quasi-convex functions need not be quasi-convex — which limits its use badly, since almost every objective anybody writes is a sum.

Invexity and its relatives ask that a vanishing gradient imply a global minimum, which is exactly the property wanted, taken as a hypothesis. That is honest and circular, and it is nonetheless useful, because for particular problem families it can be checked directly — and a hypothesis that is checkable is worth having even when it is the conclusion in disguise.

Geodesic convexity replaces straight lines by the geodesics of some geometry. A function that is not convex in the usual coordinates can be convex along the right curves, and several problems — computing a matrix’s geometric mean, maximum-likelihood estimation for some models, operator scaling — are geodesically convex and thereby easy despite looking otherwise. Finding the geometry is the work, and there is no procedure for it.

And the Polyak–Łojasiewicz condition asks that the gradient’s size bound the gap to the minimum: wherever the function is far from its best value, the gradient is correspondingly large, so there is always somewhere to go. It gives fast convergence without giving uniqueness — the set of minimisers can be large and curved — it is checkable for some families, and it is the condition under which several results about training large models are proved.

What all four have in common is that they are hypotheses to be verified rather than properties to be observed. None of them is visible in a graph and all of them require an argument.

Why practice is better than theory allows #

The theoretical picture is bleak and the practical one is not, and the discrepancy is worth taking seriously rather than dismissing.

Many non-convex problems in practice have good local minima everywhere. For several families — matrix completion, phase retrieval, some neural network architectures — it is a theorem that every local minimum is global, or that all local minima are within a small factor. Those results are about the specific structure and not about non-convexity, and each was a substantial piece of work: the statement “this particular non-convex landscape has no bad local minima” is exactly as hard to prove as it sounds, and there are perhaps a dozen families for which anybody has managed it.

The dimension helps rather than hurts. In one dimension a function with two dips has a genuine trap; in a million dimensions a point that is a minimum in every one of a million directions is rare, so the landscape is mostly saddles and the descent keeps finding a way down. That is the opposite of the intuition a one-dimensional picture gives.

And the objective is often not what is wanted. In machine learning the function being minimised is a proxy for a quantity nobody can compute — performance on data not yet seen — and a local minimum of the proxy can be as good as the global one for the actual purpose, or better. So the optimisation’s failure to reach the global minimum is not necessarily a failure at all, and in some settings finding it exactly would be worse.

None of that is a general theorem, and the honest summary is: non-convex optimisation has no guarantees, has many specific results, and works better than it should for reasons that are understood case by case.

The gap, measured #

The relationship between a non-convex problem and its convex relaxation is measurable, and it is the standard practical tool.

Replace the problem by its convex hull — the transform’s double, from the previous rung — and solve that. The answer is a lower bound on the true minimum, and the difference is the duality gap.

A small gap is a strong statement. If the relaxation’s answer is close to some feasible point’s value, that point is nearly optimal — within the gap — and the certificate is available without ever solving the original problem. That is how every serious integer optimisation reports its answer: a solution, a bound, and the distance between them.

And a large gap is informative too. It says the relaxation has lost something specific — the bump — and often identifies which constraint to tighten. That is the basis of branch-and-bound, cutting planes, and most of practical integer optimisation: solve the hull, find where its answer lies, add a constraint that excludes it without excluding any genuine solution, repeat. Each step tightens the relaxation towards the true hull, and the method terminates because the true hull has finitely many faces.

The same machinery is what the assignment problem never needs, because there the relaxation is already exact — and the contrast is exactly the contrast this rung is about, in a combinatorial setting rather than an analytic one.

So the convex theory is not abandoned when convexity fails; it becomes the tool used to bound and attack the problem that lacks it.

The one-dimensional intuition, and why it misleads #

It is worth being explicit about how the standard mental picture goes wrong, because almost everybody carries it.

The picture is a landscape with hills and valleys, a ball rolling downhill, and the risk of settling in the wrong valley. In two dimensions that is accurate.

In high dimensions almost nothing about it survives. Three specific failures:

Valleys are rare. At a critical point in $d$ dimensions, all $d$ curvatures must be positive for a minimum. If the curvatures were independent coin flips the chance would be $2^{-d}$, and the true situation is not far off — so critical points are overwhelmingly saddles and a rolling ball almost never gets stuck.

Everything is connected. In high dimensions the level sets of typical functions tend to be connected, so the low-lying regions form one basin rather than many separated ones, and there is a path downhill from nearly anywhere to nearly anywhere else. Two valleys in a two-dimensional picture are genuinely separated by a ridge; in a million dimensions there is almost always a way round.

And distance behaves oddly. Most of the volume of a high-dimensional region sits near its boundary, so “near a minimum” covers far less of the space than it appears to, and the local picture of a smooth bowl applies over a much smaller range than intuition suggests. The same concentration of volume is what makes high-dimensional sampling behave unexpectedly.

The corrected picture is a landscape of ridges and passes rather than of valleys, and the difficulty is slowness at the passes rather than being trapped in the valleys.

What the pictures cannot show #

One dimension is where the intuition is worst. Every figure here is a curve with a bump, which is the picture that suggests non-convex optimisation is about escaping valleys. In high dimensions it is about saddles, and there is no picture of a saddle in a million dimensions that helps.

A landscape is not a graph of anything anybody has seen. The functions minimised in practice have millions of variables and are known only through evaluations. Every published visualisation of such a landscape is a two-dimensional slice, chosen after the fact, and shows what the slice shows — which is a picture of a choice as much as of a function.

Nothing here shows a saddle. The section on high dimensions is about points where some directions go down and some go up, and the smallest such picture needs two variables and a surface. Every figure in this anchor is a curve, so the obstruction the section says is dominant is the one obstruction not drawn.

And the counterexample is a bump added by hand. The figures use a fourth-power well because it is the simplest thing with two minima. Real non-convexity arises from the structure of a problem rather than from an added term, and whether it produces bad local minima is a question about that structure.

Where the ladder goes next #

This rung closes the ladder’s first pass: convexity defined by chords, restated by supporting lines, described by its tangents, and its absence accounted for here.

Named here as debts. Geodesic convexity, mentioned above, which is a genuinely different notion and would need a rung about the geometry it lives in. And the structure of high-dimensional landscapes, where the results about saddles outnumbering minima are recent and are the reason practice outruns theory.

Sideways, a descent method converging to the wrong place is Newton’s method’s basins, the convex hull the relaxation computes is the transform’s double, and the certificate that exists only under convexity is the supporting line.

Ending on the first rung’s picture is deliberate. Four rungs have been spent on consequences of one relationship between a chord and a curve, and the fourth is about what happens when the relationship fails.

The list of what a single picture bought is worth restating. Jensen’s inequality and every named inequality derived from it. A supporting line at every point, and therefore that a local minimum is global, and therefore that any downhill method is correct. A description by tangents, and therefore a duality, and therefore a certificate. And an entire theory of optimisation in which an answer arrives with its own proof.

Every one of those is unavailable for the fourth-power well drawn earlier, which differs from the parabola by a term. That is the shape of the whole subject: a property that costs one line to state, whose presence or absence decides everything.

What is worth carrying away #

A property whose absence removes a guarantee entirely, rather than weakening it, is a property worth checking before anything else.

Convexity does not make a problem easy and its absence does not make a problem hard. What it does is make a local answer certifiably global, and without it a method’s output is a point with no claim attached — which is a different kind of object from an answer, whatever its numerical value.

The habit worth taking is to ask what a computation’s output is a claim about. Under convexity, “the method stopped here” means “this is the minimum”. Without it, the same sentence means only that the method stopped, and the distance between those two readings is the whole of this rung.

That is also the honest way to report a result from a method that cannot certify. Saying that a search returned the best value it found is a true statement about the search; saying that it found the minimum is a claim about the problem, and only convexity — or an argument standing in for it — turns the first into the second.