Convexity, and why nobody promises anything about deep networks

The shape that comes with a guarantee

A function is convex if the straight line between any two points on its graph lies on or above the graph — a bowl, with no dents. The reason anyone cares is a guarantee: a convex function has exactly one minimum region, and gradient descent with a sensible step size will find it, from any starting point. No luck involved, no initialisation to tune.

Convex problems include linear regression with squared loss, logistic regression, support vector machines, and lasso and ridge regression. This is why those methods are so reliable: run the fit twice on the same data and you get the same answer, because there is only one answer to get.

Test for convexity in one variable by looking at the second derivative. f(x) = x² has f'' = 2 > 0 everywhere: convex. f(x) = x³ has f'' = 6x, negative for negative x: not convex. In many variables the equivalent is that the Hessian, the matrix of second derivatives, has no negative eigenvalues.

Neural networks are not convex, and it is not close

Add one hidden layer with a non-linear activation and convexity is gone. It is easy to see why: swap two hidden units, along with their weights, and you get a network computing exactly the same function with different parameters. Two distinct points, identical loss. A convex function cannot have two separate equally-low points with a rise between them, and a network with n hidden units in a layer has n! such copies of every solution. A layer of 100 units has more equivalent minima than there are atoms in the observable universe.

So there are no convergence guarantees for deep learning. None. Everything about why training works is empirical, and it is worth saying that plainly rather than implying there is a proof somewhere you have not read.

Why it works anyway: saddles, not traps

The intuition people carry from two-dimensional pictures — gradient descent trapped in a small local dip, missing the deep valley next door — turns out to be mostly wrong in high dimensions, and the reason is a counting argument.

At any flat point, the surface curves up or down in each of the directions given by the Hessian's eigenvectors. For that point to be a local minimum, it must curve up in every single one. In a million-dimensional space, that requires a million independent conditions to hold at once. A point where some directions curve up and others curve down is a saddle, and gradient descent escapes a saddle: it simply follows a downward direction out.

Both theoretical analysis of random high-dimensional surfaces and empirical measurement of trained networks support this picture: the flat points encountered during training are overwhelmingly saddles, and the local minima that exist tend to have losses close to one another. Being stuck is far less common than being slow.

Treat this as the current best explanation rather than a settled fact. It is an active area, and the honest statement is that deep networks train reliably, that we have a plausible account of why, and that the account is not a proof.

Sharp and flat, and why it might matter

A related and genuinely contested question is whether the kind of minimum matters. The proposal is that wide, flat minima generalise better than narrow, sharp ones, because a flat basin means small perturbations to the weights barely change the loss, and the test distribution is a small perturbation of the training one.

There is supporting evidence, there is a well-known counter-argument that sharpness can be manufactured or removed by rescaling weights without changing the function at all, and there are optimisers built on the idea, such as sharpness-aware minimisation, which do measurably help on some benchmarks. It is a live disagreement. Anyone presenting flat-minima theory as established is going beyond the evidence.

What follows for you in practice

• Initialisation matters in a way it does not for convex problems. Different seeds give different final models, with genuinely different behaviour on edge cases even at identical accuracy.
• Reporting one run is reporting one draw. If two configurations differ by half a point, run each three times before believing the difference. Seed variance on a small dataset is routinely larger than the effect people publish.
• Do not go hunting for the global minimum. It almost certainly corresponds to memorising the training set. What you want is a good enough minimum that generalises, which is why regularisation and early stopping exist.
• Reach for convex methods when they fit. If logistic regression solves your problem, its reproducibility and its interpretable coefficients are real advantages, not a consolation prize.

The rule to keep

Convexity buys a guarantee, and deep learning gave it up in exchange for expressive power. What replaced the guarantee is the empirical observation that high-dimensional loss surfaces have far more saddles than traps, which is a good reason for confidence and not a substitute for running your experiment more than once.