Convexity and the optimisation landscape

A function is convex if the line between two points on the graph always lies above the graph — a bowl. The consequence is strong: every local minimum is global. Gradient descent finds the right one wherever you start.

x², eˣ, |x| and −log x are convex. sin x, x³ and nearly all neural networks are not.

Convex problems in ML: linear regression (MSE), logistic regression, SVM, lasso/ridge. That is why they are so stable — the same data gives the same solution every time.

Neural networks are deeply non-convex. The landscape has many minima, saddle points and plateaus. Two runs with different seeds land in different solutions — which nevertheless often perform equivalently.

The definition: $f$ is convex if for all $x, y$ and $\lambda\in[0,1]$: $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda) f(y)$

The test in one dimension: $f''(x) \ge 0$ everywhere. In several dimensions: the Hessian $H$ is positive semidefinite (all the eigenvalues $\ge 0$).

Critical points ($\nabla f = 0$) are classified by the Hessian's eigenvalues:

• all positive → a local minimum
• all negative → a local maximum
• mixed signs → a saddle point

Why saddle points are the real problem in deep learning: in $d$ dimensions all $d$ eigenvalues have to have the same sign for a genuine minimum. The probability of that falls fast with $d$ — so in million-dimensional landscapes the vast majority of critical points are saddle points, not local minima (Dauphin et al. 2014).

The gradient is nearly zero near a saddle point, so the training «gets stuck» — but only temporarily. Momentum and the noise from stochastic gradients get past it. That is one of the reasons SGD with noise works better than you would think.

import numpy as np

# A saddle point: f(x,y) = x² − y², a critical point at the origin
f = lambda x, y: x**2 - y**2
H = np.array([[2.0, 0.0], [0.0, -2.0]])
print(np.linalg.eigvalsh(H))       # [-2.  2.]  ← mixed signs = a saddle point

# Gradient descent from a point near the saddle
x, y, eta = 0.001, 0.001, 0.1
for i in range(60):
    x -= eta * 2 * x               # pulled towards 0
    y -= eta * (-2 * y)            # pushed away from 0
print(round(x, 6), round(y, 3))    # 1e-06  0.115  ← creeps slowly out of the saddle

Near the origin the gradient is small in both directions, and it takes many steps before the y direction picks up speed. It looks as if the training has stalled — but it has not.