Convex vs Non-Convex Loss Surfaces

Gradient descent's whole strategy is "walk downhill." That strategy comes with an unstated assumption: that any downhill path eventually reaches the one lowest point that exists. For a convex loss — think of a single smooth bowl — that assumption is guaranteed true, no matter where you start. For a non-convex loss — a landscape riddled with hills, ridges and separate dips — it is not, and "walk downhill" can strand you in a valley that is nowhere near the true global minimum, with no signal from the gradient itself telling you that a better valley exists somewhere else.

The analogy: a single valley vs. a mountain range in fog

A convex loss is a single valley: drop a ball anywhere on its slopes and it eventually settles at the one lowest point, whose depth doesn't depend on where you dropped it. A non-convex loss is a mountain range in thick fog: you can only feel the slope under your feet, so you walk downhill and stop where the ground flattens — but that flat spot could be the true lowest valley in the range, or a random pocket a few hundred meters up a different mountain. You can't tell from where you're standing, and your starting point determines which pocket you land in.

The formal distinction

A function $f$ is convex if, for any two points $\theta_1, \theta_2$ and any $t \in [0,1]$:

$$f\big(t\theta_1 + (1-t)\theta_2\big) \le t f(\theta_1) + (1-t) f(\theta_2)$$

In words: the function's value at any point between two other points never sits above the straight line connecting their values — the graph never bulges upward between two points on it, which is exactly the "no separate hill blocking the path between two valleys" property a bowl has and a mountain range doesn't. For a convex loss, every local minimum is automatically the global minimum — there is only ever one basin. Linear regression's squared error and logistic regression's log loss are both convex in their weights. A deep neural network's loss, once you compose enough nonlinear layers together, is not: it has many local minima, saddle points (flat in some directions, sloped in others), and plateaus, and nothing in the formula guarantees they're all equally good.

Worked example 1: a convex bowl by hand

For $f(\theta) = (\theta - 3)^2$, take $\theta_1 = 0$, $\theta_2 = 6$, $t = 0.5$: the midpoint is $\theta = 3$, giving $f(3) = 0$. The convexity inequality's right side is $0.5(9) + 0.5(9) = 9$. Since $0 \le 9$, the inequality holds — and in fact $\theta=3$ is the global minimum, reachable by gradient descent from literally any starting $\theta$, because a parabola has exactly one basin.

Worked example 2: a non-convex surface with a false minimum

Consider $f(\theta) = \theta^4 - 4\theta^2 + \theta$, a landscape with two separate basins. Its derivative $f'(\theta) = 4\theta^3 - 8\theta + 1$ is zero near $\theta \approx -1.47$, $0.13$, and $1.35$ — three flat points, not one. At the two basin bottoms: $f(-1.47) \approx -3.42$ and $f(1.35) \approx -3.05$. Gradient descent started near $\theta = 1.0$ slides into the $\theta \approx 1.35$ basin and reports convergence at loss $-3.05$ — a real local minimum, correctly found, yet worse than the $-3.42$ basin sitting just a few units away. Nothing about the algorithm's behavior at $\theta=1.35$ (zero gradient, positive curvature) reveals a better basin exists elsewhere.

Try starting the descent above from different points on a bumpy loss curve — watch how the final resting point depends on the starting point, which never happens on a single bowl.

What this means in practice

Because deep learning loss surfaces are non-convex, practitioners run training multiple times from different random initializations, use momentum-based optimizers that can carry through shallow bumps, and treat "did it converge" as a much weaker claim than "did it converge to a good solution." Classical models like linear and logistic regression get a much stronger guarantee for free — any solver that converges at all has found the actual best fit, full stop.