Convex and Non-Convex Optimization

In convex optimization any local minimum is guaranteed to be global, while non-convex optimization navigates rugged landscapes packed with saddle points and spurious valleys.

A convex bowl with minimum value 4 at minus 1, 3 sits beside a saddle with eigenvalues plus 2 and minus 6, where a small step along the negative curve drops the value from 0 to minus 0.03

Why Does This Exist?

The great watershed in optimization is not between linearity and non-linearity but between convexity and non-convexity.

Classical models, ordinary least squares, logistic regression and SVMs, are deliberately formulated as convex problems. For a convex function any local minimum is guaranteed to be global, so solvers started anywhere converge to the same answer without babysitting.

Deep networks shatter that guarantee. Stacked nonlinearities, normalisation, attention and weight permutation symmetries turn the loss into a non-convex surface with flat plateaus, local valleys and an enormous number of saddle points. Understanding the boundary explains why classical solvers do not transfer, why initialisation matters, and how stochastic noise escapes saddles.

For the shapes and rules underneath, start with convex sets and functions. For the certificate side of the family, see convex optimization.

Think of It Like This

A smooth salad bowl versus an expansive mountain range

Drop a steel marble into a smooth salad bowl. Wherever you release it on the rim, gravity guides it to the single lowest point. No secondary traps, no false basins, no flat ledges. That is convex optimization: downhill motion is guaranteed to find the global best.

Now drop it into a rugged mountain range in fog. It can settle in an elevated lake far above the valley floor, a suboptimal local minimum. It can roll onto a vast mesa where gravity barely pulls, a plateau. Or it can pause on a mountain pass that rises left and right but drops ahead and behind, a saddle.

In the mountains, passive rolling is not enough. You need tremors to bounce out of shallow traps and momentum to ride through passes down to the deep valley. That is non-convex optimization.

Where the analogy stops: mountains have three dimensions, where traps are common. In networks with millions of dimensions, true trapped minima are rare and saddles outnumber minima exponentially, so the marble is usually on a pass rather than in a lake.

How It Actually Works

Convexity conditions

A function $f$ on a convex domain is convex when, for all $\mathbf{x}, \mathbf{y}$ and any $\alpha \in [0, 1]$ :

f(\alpha \mathbf{x} + (1-\alpha)\mathbf{y}) \le \alpha f(\mathbf{x}) + (1-\alpha) f(\mathbf{y})

The chord between any two points sits on or above the graph. For twice-differentiable $f$ , convexity holds exactly when the Hessian is positive semi-definite everywhere:

\nabla^2 f(\mathbf{x}) \succeq 0 \quad \forall \mathbf{x} \iff \lambda_{\min}(\nabla^2 f(\mathbf{x})) \ge 0

Here $\lambda_{\min}$ is the smallest Hessian eigenvalue. Strictly positive definite everywhere means strictly convex and a unique global minimiser.

Critical points in non-convex landscapes

Where the Hessian is indefinite, eigenvalues take both signs depending on position. At a critical point with $\nabla f(\mathbf{x}) = \mathbf{0}$ , the signs classify it, and the full procedure is in critical points and saddle points:

Local minimum: all eigenvalues strictly positive.
Local maximum: all eigenvalues strictly negative.
Saddle point: at least one positive and at least one negative eigenvalue.

Why saddles dominate deep learning

In $d$ dimensions, suppose Hessian eigenvalue signs at a random critical point are roughly equally likely to be positive or negative. The probability that all $d$ come out positive, a true local minimum, is:

P(\text{local minimum}) \approx \left(\frac{1}{2}\right)^d = 2^{-d}

For $d = 10$ that is about 1 in 1,024. For $d = 10{,}000$ it is effectively zero. Critical points at elevated loss are overwhelmingly saddles, and first-order methods with noise or momentum follow the negative-curvature directions downhill toward wide low-loss basins.

Worked example

Two functions, one of each kind, with every number computed.

Convex quadratic. Take $f_1(x_1, x_2) = 2x_1^2 + x_2^2 + 4x_1 - 6x_2 + 15$ . The gradient is:

\nabla f_1 = \begin{bmatrix} 4x_1 + 4 \\ 2x_2 - 6 \end{bmatrix}

Setting it to zero gives $x_1^* = -1$ and $x_2^* = 3$ , so $\mathbf{x}^* = [-1, 3]^T$ . The Hessian is constant:

\mathbf{H}_1 = \begin{bmatrix} 4 & 0 \\ 0 & 2 \end{bmatrix}

Eigenvalues $\lambda_1 = 4$ and $\lambda_2 = 2$ , both positive, so $f_1$ is strictly convex and $\mathbf{x}^*$ is the unique global minimum with value $f_1(-1, 3) = 2(1) + 9 + 4(-1) - 6(3) + 15 = 2 + 9 - 4 - 18 + 15 = 4$ .

Saddle. Take $f_2(x_1, x_2) = x_1^2 - 3x_2^2$ . The gradient is $[2x_1, -6x_2]^T$ , zero only at the origin. The Hessian is:

\mathbf{H}_2 = \begin{bmatrix} 2 & 0 \\ 0 & -6 \end{bmatrix}

Eigenvalues $+2$ and $-6$ have opposite signs, so the origin is a strict saddle. Along $x_1$ the surface curves up ( $f_2(x_1, 0) = x_1^2$ ); along $x_2$ it curves down ( $f_2(0, x_2) = -3x_2^2$ ). A step of $0.1$ along the $x_2$ eigenvector drops the value from $0$ to $0 - 3(0.1)^2 = -0.03$ , which is the escape the diagram shows.

Code

The point of this snippet is the classification check: given a Hessian, read its eigenvalues and name the point, then verify the escape direction actually descends.

1import numpy as np2
3
4def analyze_critical_point(hessian: np.ndarray) -> tuple[str, np.ndarray, bool]:5    """Classify a critical point using Hessian eigenvalues."""6    eigenvalues = np.linalg.eigvalsh(hessian)7
8    all_positive = bool(np.all(eigenvalues > 1e-8))9    all_negative = bool(np.all(eigenvalues < -1e-8))10    has_mixed = bool(np.any(eigenvalues > 1e-8) and np.any(eigenvalues < -1e-8))11
12    if all_positive:13        return "Local/Global Minimum", eigenvalues, True14    if all_negative:15        return "Local Maximum", eigenvalues, False16    if has_mixed:17        return "Saddle Point", eigenvalues, False18    return "Degenerate / Valley", eigenvalues, bool(np.all(eigenvalues >= -1e-8))19
20
21h_convex = np.array([[4.0, 0.0], [0.0, 2.0]])22print(analyze_critical_point(h_convex)[0])     # -> Local/Global Minimum23print(analyze_critical_point(h_convex)[1])     # -> [2. 4.]24
25h_saddle = np.array([[2.0, 0.0], [0.0, -6.0]])26print(analyze_critical_point(h_saddle)[0])     # -> Saddle Point27print(analyze_critical_point(h_saddle)[1])     # -> [-6.  2.]28
29step = 0.1 * np.array([0.0, 1.0])              # along the lambda = -6 eigenvector30print(float(step[0] ** 2 - 3 * step[1] ** 2))  # -> -0.03  escape descends

The eigenvalues $[2, 4]$ and $[-6, 2]$ match the hand computation, and the escape step reproduces the $-0.03$ drop.

Watch Out For

Mistaking a saddle plateau for a bad local minimum

When the loss flatlines, the usual verdict is "trapped in a bad local minimum". In over-parameterised networks genuine bad minima, all eigenvalues positive at high loss, are extraordinarily rare. The stall is almost always a saddle or an ill-conditioned ravine where the gradient norm drops below $10^{-5}$ along flat directions while a descent direction still exists.

Do not add capacity to bypass a minimum that is not there. Instead introduce momentum such as Polyak momentum or Adam, shrink the minibatch to raise stochastic noise so updates jitter along the negative-curvature escape directions, or use warm-up with cosine annealing to carry the run through the flat stretch.

Trusting a zero gradient as a certificate outside convex problems

On a convex problem a zero gradient certifies a global minimum. On a neural loss it certifies almost nothing: the point can be a saddle, a plateau, or a sharp valley with far better basins nearby. Teams that port the convex stopping rule verbatim stop at the first flat spot and ship an undertrained model.

Pair the gradient norm with curvature evidence or with continued progress checks. If the norm is small but the loss is far above known-good values, treat the run as stalled on a saddle, not converged, and restart with momentum or noise before accepting the point. The certificate logic that applies here is in convex optimization; everywhere else it is only a candidate filter.

The Quick Version

Convex means chords sit above the graph, equivalently a positive semi-definite Hessian everywhere.
Any stationary point of a convex problem is a global minimum. That certificate is what non-convex problems lose.
Deep losses are non-convex: stacked nonlinearities and permutation symmetries alone guarantee repeated equivalent minima.
At a zero gradient, Hessian signs classify the point: all positive is a minimum, mixed is a saddle.
Saddles dominate in high dimensions: all $d$ eigenvalues positive happens with probability about $2^{-d}$ .
The worked pair shows both sides: minimum value 4 at $(-1, 3)$ with eigenvalues 4 and 2, and a saddle at the origin with eigenvalues $+2$ and $-6$ .
Escape uses momentum and minibatch noise, which follow negative-curvature directions downhill.
A flat loss with a tiny gradient is usually a saddle, not a trap, so keep patience long and the gradient norm logged.