Convexity

Why optimization is easy in theory and hard in practice

Why

Convexity determines whether gradient descent is guaranteed to find the global minimum. Linear regression and logistic regression have convex loss functions — gradient descent always finds the best solution. Neural networks do not — their loss surfaces are riddled with local minima, saddle points, and flat regions. Understanding convexity explains why training a neural net is fundamentally harder than training a linear model, and why we rely on tricks like momentum, normalization, and good initialization.

Intuition

A convex function is shaped like a bowl — any two points on the curve, the line segment between them lies above (or on) the curve. There's only one valley, so wherever you start gradient descent, you'll end up at the same global minimum.

A non-convex function is like a mountain range — full of valleys, peaks, and flat plateaus. Gradient Descent can get trapped in a shallow local valley far from the deepest point. This is the landscape neural networks live in.

Explanation

Formal definition

A function f is convex if for any two points x, y and any λ ∈ [0, 1]:

f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y)

The function value at any interpolated point is at most the interpolated function value — the chord never dips below the curve.

Equivalently: f is convex if f''(x) ≥ 0 everywhere (non-negative second derivative — concave up). For multivariate functions: the Hessian matrix is positive semi-definite everywhere.

Convex vs non-convex in ML

Convex: linear regression (MSE loss), logistic regression (cross-entropy), SVMs, Lasso/Ridge — gradient descent always finds the global optimum
Non-convex: neural networks (any depth ≥ 2 with nonlinear activations) — loss surface has exponentially many critical points
Why non-convex networks still train well: most local minima in high-dimensional spaces are actually close in loss value to the global minimum. Saddle points (not local minima) are the real challenge — gradient descent can stall near them.

Critical points on the loss surface

Local minimum: ∇f = 0, Hessian is positive definite (all eigenvalues > 0) Local maximum: ∇f = 0, Hessian is negative definite (all eigenvalues < 0) Saddle point: ∇f = 0, Hessian has mixed eigenvalues (some + and some -) Plateau: ∇f ≈ 0 over a wide region — gradient descent stalls

In high dimensions (millions of parameters), saddle points are overwhelmingly more common than local minima. The loss at a random saddle point in a deep network is typically close to the global minimum — which is why neural networks can be trained at all despite non-convexity.

Practical implications

Momentum (in SGD with momentum, Adam): accumulates velocity across steps — helps roll through saddle points and flat regions instead of stalling
Batch noise: the randomness of mini-batch gradients helps escape sharp local minima and saddle points
Learning rate warmup: starts with small steps to avoid overshooting early in training when gradients are large
Good initialization: Xavier/He init sets weights so gradients are well-scaled at the start — bad initialization can land near flat or explosive regions of the loss surface

← Previous Practice interview questions →