Saddles, Not Traps: Why Gradient Descent Survives a Non-Convex Loss in High Dimensions — Epoche C2
The syllogism that predicted failure The training loss of a deep network is not a convex function of its parameters, and the inference usually drawn from that fact — that gradient descent must halt at an arbitrary local minimum far above the best achievable loss — is empirically false. The inference ran in three steps. The loss $L(\theta)$, as a function of the parameter vector $\theta$ collecting all $N$ weights, is non-convex. A non-convex function has many local minima. Gradient descent moves downhill and stops where the gradient vanishes. Therefore training halts at whichever local minimum the initialisation happens to lie above. Every step is plausible, and the conclusion is contradicted by the simplest experiment available: train one architecture from many independent random starts and look at the spread of the final training losses. Choromanska and colleagues ran that experiment. On a standard handwritten-digit benchmark they trained a single-hidden-layer network from a thousand random initialisations at each of several hidden-layer widths between 25 and 500 units, and plotted the histogram of final losses at each width. At the smallest width the histogram is broad; as the width grows it collapses onto a narrow band sitting just above the lowest loss ever observed, and the collapse continues monotonically with size. The runs are not finding qualitatively different solutions. It is worth being exact about what this does and does not show, because the result is often quoted in an inflated form, as agreement to within a fraction of a percent in networks with tens of millions of parameters. The published measurement is smaller and cleaner than that: the largest network in the experiment has under half a million weights, and what is measured is the narrowing of a distribution, not a bound on any single run. The narrowing is nonetheless the fact that needs explaining. This review sets out the explanation that was given, the theorems subsequently proved about whether it licenses anything algorithmic, and the three places where it is now known to be wrong. Counting critical points by index rather than by number The resolution proposed by Dauphin and colleagues in 2014 attacks the second step of the syllogism. Non-convexity guarantees many critical points — points where $\nabla L = 0$ — but says nothing about what kind they are, and in high dimension the kinds are distributed very unevenly. At a critical point $\theta^{*}$ the local shape is fixed by the Hessian $H = \nabla^{2}L(\theta^{*})$, the symmetric $N \times N$ matrix of second derivatives, whose eigenvalues are the curvatures along $N$ mutually orthogonal directions. The index of the critical point is the number of negative eigenvalues: index $0$ is a local minimum, index $N$ a local maximum, and anything between is a saddle, curving down along some directions and up along others. The distinction that matters to an algorithm is that a saddle is not a trap. At a saddle some direction strictly decreases the loss; only at an index-$0$ point is descent blocked in every direction at once. So the question is what fraction of critical points have index $0$, and here the dimension does the work. A minimum requires all $N$ eigenvalues to be positive simultaneously. Take as a first model that the Hessian at a critical point picked at random from the landscape behaves like a matrix from the Gaussian orthogonal ensemble: real symmetric, with independent Gaussian entries of variance $\sigma^{2}$, whose spectrum fills $[-2\sigma\sqrt{N},\, 2\sigma\sqrt{N}]$ with the semicircular density, symmetric about zero. Rescaling by $\sigma\sqrt{N}$ places the spectrum on $[-2, 2]$, and that is the normalisation used below. Requiring every eigenvalue of a density symmetric about zero to land on the positive side is a large-deviation event, and the argument turns entirely on how large. The crudest estimate treats the $N$ signs as independent fair coin flips: $$P(\text{all eigenvalues positive}) \approx 2^{-N},$$ which at $N = 100$ gives $7.9 \times 10^{-31}$. The estimate is wrong, and wrong in the generous direction. The truth is very much smaller, because the eigenvalues of a random matrix are not independent quantities that happen to be correlated: they repel. Why the signs are not coin flips: a Coulomb gas at order $N^{2}$ The reason the coin-flip estimate fails, and the reason the correct answer has a different functional form rather than a different constant, is visible in the joint density of the eigenvalues. For the Gaussian ensembles, in the normalisation just fixed, it is $$P(\lambda_{1}, \ldots, \lambda_{N}) \propto \prod_{i<j}|\lambda_{i} - \lambda_{j}|^{\beta}\,\exp\left(-\frac{\beta N}{2}\sum_{i}\lambda_{i}^{2}\right),$$ with $\beta = 1$ for real symmetric matrices and $\beta = 2$ for complex Hermitian ones. Writing this as $\exp(-\beta E)$ identifies an energy $$E[\{\lambda\}] = \frac{N}{2}\sum_{i}\lambda_{i}^{2} \;-\; \sum_{i<j}\ln|\lambda_{i} - \lambda_{j}|,$$ the energy of $N$ charges confined to a line, held by a quadratic well and repelling one another logarithmically. Both terms are of order $N^{2}$: the first because an explicit factor $N$ multiplies a sum of $N$ terms, the second because there are $\binom{N}{2}$ pairs. That is the structural point. A constraint requiring the whole charge density to be rearranged — such as pushing every charge onto the positive half-line — costs energy proportional to $N^{2}$, whereas $N$ independent binary constraints would cost an amount proportional to $N$. Dean and Majumdar performed the constrained minimisation exactly, computing the equilibrium density supported on the positive half-line and comparing its energy with that of the unconstrained semicircle. For the Gaussian ensembles the answer is $$P(\text{all eigenvalues positive}) \sim \exp\left(-\beta\,\frac{\ln 3}{4}\,N^{2}\right).$$ Put numbers in for the real symmetric case, $\beta = 1$, where $\ln 3 / 4 = 0.2747$. At $N = 100$ the exponent