DL0180 Convex vs Non-Convex Optimization Landscapes

Written by

Explain the difference between convex and non-convex optimization landscapes in high-dimensional deep learning, and why non-convexity in deep networks is empirically more tractable than classical theory predicts.

Answer

A convex objective is shaped like a single bowl: every local minimum is a global minimum, the stationarity condition $\nabla f(x) = 0$ is sufficient for optimality, and convergence rates hold from any initialization. Deep networks violate convexity by construction, because composing affine maps with nonlinearities produces a loss that is invariant under permuting hidden units within a layer, so the surface already carries $\prod_l h_l!$ equivalent copies of every solution and no convex reparameterization of the weights exists. Classical theory then warns that gradient descent could stall in a poor local minimum, but in high dimension the geometry is different: a local minimum requires all $d$ Hessian eigenvalues to be positive at once, which random-matrix and spin-glass arguments make exponentially improbable except very close to the loss floor, so the overwhelming majority of critical points are saddles that gradient noise escapes. Overparameterized networks add a second effect: along the training trajectory the loss satisfies a local Polyak-Lojasiewicz condition, which gives linear convergence to a near-zero-loss solution without any convexity assumption. The solutions SGD reaches are also not isolated, since distinct runs are joined by low-loss curved paths, so the practical obstructions are ill-conditioning, plateaus, and degenerate saddles rather than the isolated bad basins convexity theory teaches you to fear.

(1) What Convexity Buys: local equals global, a checkable optimality certificate, duality gaps, and initialization-independent rates such as $O(1/k)$ for gradient descent on smooth convex losses.
(2) Deep Nets Are Non-Convex By Construction: nested nonlinearities plus permutation and rescaling symmetries mean the loss is a highly multimodal function of the weights even when it is convex in the network output.
(3) Saddles Dominate Critical Points: the fraction of negative Hessian eigenvalues, the index, is almost never zero away from the loss floor, so most flat regions are passable rather than terminal.
(4) Band Structure Of Critical Values: the expected loss of a critical point grows roughly linearly with its index, so high-loss critical points come with escape directions and low-loss ones are what remains.
(5) Overparameterization Tames The Trajectory: in the wide-network regime the loss is nearly a convex function of the output and satisfies a PL inequality locally, giving linear convergence to global training loss near zero.
(6) The Low-Loss Set Is Connected: mode connectivity shows independent solutions are linked by low-loss curves, and permutation alignment removes most of the naive linear-interpolation barrier.
(7) The Real Enemies Are Conditioning And Degeneracy: plateaus with near-zero curvature in every direction, saturated units, and Hessian condition numbers in the thousands cost far more wall-clock time than bad minima.

Two contour maps side by side. Left: a single elliptical bowl with three gradient descent trajectories from different initializations all converging to the same central minimum. Right: a rugged multi-basin surface where three trajectories from different initializations settle into three different basins of comparable depth, with one saddle point marked between two basins.

Figure 1: The structural difference in two dimensions. On the convex bowl every trajectory reaches the same point, so the answer is a property of the objective. On the rugged surface the endpoint depends on initialization, yet the basins reached have comparable depth, which is the two-dimensional cartoon of what actually happens in $d \approx 10^{8}$ : many solutions, not many bad solutions.

The intuition that non-convexity means “gradient descent gets trapped” comes from low-dimensional pictures, where a basin is bounded by walls in both directions. In $d$ dimensions a critical point is a minimum only if the Hessian is positive definite in every one of $d$ directions, and a single negative eigenvalue is enough to make it a saddle with a downhill escape route. Under a Gaussian-random-field or spin-glass model of the loss, the probability that a randomly encountered critical point has index zero decays like $e^{-c d}$ , and the critical values organize into a band: the higher the loss, the larger the expected index. Measured Hessian spectra at converged deep-network solutions match the qualitative picture, with a bulk of near-zero eigenvalues (the flat, degenerate directions created by symmetry and overparameterization), a handful of large positive outliers roughly matching the number of classes, and a thin slightly negative tail. Theory for deep linear networks makes the same point exactly: every local minimum is a global minimum, and the non-convexity manifests as saddles rather than as spurious basins.

Left panel: scatter plot of loss value versus index fraction for simulated critical points, forming an upward band so that critical points with zero or near-zero index cluster at the lowest loss values, with a shaded strip marking the index-zero region. Right panel: log-scale histogram of Hessian eigenvalues at a converged solution showing a very tall bulk concentrated at zero, a thin negative tail, and a dozen isolated large positive outliers.

Figure 2: Left, the band structure: critical points with a high fraction of negative curvature directions sit at high loss, and only points near the loss floor are close to index zero, so “escapable” and “bad” are the same set. Right, a representative Hessian spectrum: thousands of near-zero eigenvalues, a few large outliers that set the effective step-size limit, and a small negative tail that keeps the point technically a saddle.

Mathematical Formulation:
$f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)$
$\nabla^2 f(x) \succeq 0$
$\alpha(x) = k_{-}(x) / d$
$\mathbb{E}[f \mid \alpha] \approx f_0 + c\,\alpha$
$P(\alpha = 0) \sim e^{-c d}$

Where:

$f$ is the training loss as a function of the parameter vector, $x, y$ are two parameter settings, and $\lambda \in [0,1]$ interpolates between them; the first line is the definition of convexity and the second its twice-differentiable equivalent.
$\nabla^2 f(x) \succeq 0$ means the Hessian is positive semidefinite everywhere, which is exactly the condition a deep network’s loss fails to satisfy.
$k_{-}(x)$ counts negative Hessian eigenvalues at a critical point, $d$ is the parameter count, and $\alpha(x)$ is the index fraction; $\alpha = 0$ is a local minimum and any $\alpha > 0$ is a saddle.
$f_0$ is the loss floor and $c$ a positive constant, so the fourth line states the band structure: expected critical value increases with index.
The last line is the random-matrix scaling for an index-zero critical point of a Gaussian random field, which is why bad local minima are measure-zero in practice for large $d$ .

Why Non-Convexity Is Still Solvable:
$\|\nabla f(x)\|^{2} \geq 2\mu\,(f(x) - f^{*})$
$f(x_k) - f^{*} \leq (1 - \mu/L)^{k}\,(f(x_0) - f^{*})$
$\|\nabla f(x)\| \leq \epsilon$
$\lambda_{\min}(\nabla^2 f(x)) \geq -\sqrt{\epsilon}$
$T = O(\epsilon^{-2}\log^{4}(d/\epsilon))$

Where:

The first line is the Polyak-Lojasiewicz (PL) inequality with constant $\mu > 0$ and optimal value $f^{*}$ : wherever the loss is far from optimal, the gradient is large.
PL plus $L$ -smoothness yields the second line, a linear convergence rate with no convexity assumption, and wide networks provably satisfy a local PL condition in a neighborhood of their initialization.
The next two lines define an $\epsilon$ –second-order stationary point: small gradient and no strongly negative curvature, which rules out strict saddles rather than merely first-order stalls.
$T$ is the iteration count in which perturbed gradient descent reaches such a point, with only polylogarithmic dependence on the dimension $d$ ; SGD’s minibatch noise plays the same role for free.

The last piece of the empirical story is that the solutions are not isolated points in separate valleys. Naively interpolating linearly between two independently trained networks produces a large loss barrier, which looks like evidence for distinct basins, but that barrier is largely an artifact of the permutation symmetry: after matching the hidden units of one network to the other, the linear path becomes far flatter, and a low-loss quadratic Bezier path can be found between essentially any pair of solutions. Functionally the minima behave like a single connected low-loss manifold, modulo relabeling, which is why techniques that assume a connected solution set (weight averaging, ensembling along a path, cyclical learning rates) work at all. In production this reframes debugging: a run stuck at high loss is almost never in a bad minimum, it is in a plateau caused by dead units, a saturated nonlinearity, a bad initialization scale, or a step size fighting the largest Hessian eigenvalue.

Line chart of training loss along a path between two independently trained solutions as the interpolation coefficient goes from zero to one. The naive linear interpolation curve rises to a tall barrier in the middle, the permutation-aligned linear interpolation curve rises only slightly, and the curved Bezier path stays essentially flat at the endpoint loss, with a double-headed arrow marking the barrier height.

Figure 3: The apparent wall between two solutions is mostly symmetry, not geometry. Naive linear interpolation crosses a large barrier; permutation alignment flattens most of it, and a learned curved path stays at the endpoint loss the whole way, evidence that the low-loss set is connected rather than a collection of isolated basins.

Property	Convex objective (logistic regression, SVM, LASSO)	Non-convex deep network loss
Stationary points	One connected set of global minima; no saddles	Exponentially many critical points, mostly saddles; global minima replicated by permutation symmetry
Optimality certificate	Zero gradient (or a duality gap bound) proves global optimality	None available; you report training loss and validation metrics, not optimality
Effect of initialization	Affects speed only; the solution is unique up to degeneracy	Selects which solution you land in; scale of initialization can decide whether training starts at all
Role of dimension	Higher $d$ costs compute and risks overfitting	Higher $d$ helps: index-zero critical points become rare and a local PL condition appears
What stalls training	Condition number of the Hessian, non-smooth regularizers	Degenerate plateaus, dead or saturated units, exploding curvature at the step-size limit
Reproducibility	Bitwise-comparable solutions across seeds and solvers	Different weights every seed; only the function learned is comparable

Fit

DL0180 Convex vs Non-Convex Optimization Landscapes

Comments

Leave a Reply Cancel reply

More posts

MSD0064 Notification Ranking System

MSD0063 Image Copyright Detection

MSD0062 Ads Ranking System

MSD0061 Nearby Place Recommendation