Convexity and the geometry of loss surfaces

Training a model means minimizing a loss function. Everything that follows in this module — learning rates, momentum, Adam, the pathologies of deep-net training — is determined by the geometry of that loss surface. Convexity is the cleanest geometry there is, and it is the right place to start for two reasons: it is the setting where optimization has actual guarantees, and it supplies the two constants ($\mu$ and $L$) that will quantify the behaviour of every algorithm in this module, convex or not.

Convex sets and convex functions

A set $C \subseteq \mathbb{R}^d$ is convex if the line segment between any two of its points stays inside it:

A function $f:\mathbb{R}^d \to \mathbb{R}$ is convex if its graph never dips below any of its chords — Jensen’s inequality in its simplest form:

If the inequality is strict for $x \neq y$, $f$ is strictly convex (at most one minimizer). Geometrically: a convex function is a bowl, possibly a degenerate one with flat directions.

The first-order condition: tangents are global underestimators

For differentiable $f$, convexity is equivalent to

Read this carefully, because it is the engine behind every convergence proof you will meet: the tangent plane at any point lies below the entire function. The local linear model that gradient descent trusts is never optimistic. It has an immediate, famous consequence:

If $\nabla f(x^\star) = 0$ at some point of a convex function, then $f(y) \ge f(x^\star)$ for every $y$. Every stationary point is a global minimum. There is nothing to get trapped in.

This single line is what non-convex optimization gives up.

The second-order condition, and the two constants that matter

For twice-differentiable $f$, convexity is equivalent to the Hessian being positive semidefinite everywhere: $\nabla^2 f(x) \succeq 0$, i.e. every eigenvalue of the curvature matrix is $\ge 0$. Two refinements bound the curvature from both sides, and these bounds are the module’s recurring characters:

$\mu$-strong convexity — curvature bounded below:

The function is at least as curved as a quadratic bowl of curvature $\mu$; minimizers are unique, and distance to the optimum is controlled by the gradient norm.

$L$-smoothness — curvature bounded above (gradient is $L$-Lipschitz):

The function is never curvier than a quadratic of curvature $L$; overshooting a step is bounded, which is what will make a constant learning rate legal.

Their ratio is the condition number

the single most important scalar in this module. $\kappa = 1$ is a perfectly round bowl; large $\kappa$ is a long narrow ravine — steep across, flat along. In the next lesson $\kappa$ will appear, exactly, in the convergence rate of gradient descent; in the momentum lesson its square root will appear in the convergence rate, and that square root is the whole reason momentum exists.

Where ML sits on the convexity spectrum

Two things to take from the table. First, the classical ML core is convex — which is why those methods come with guarantees and reliable solvers, and why understanding the convex case is not an academic detour. Second, everything with a hidden layer is not, yet we will train it with the same family of algorithms. The honest framing for deep learning is: we run methods with convex-case guarantees on non-convex problems, and we study (the non-convex landscapes lesson) why that works far better than it has any right to.

What convexity buys — and the price of losing it

For a convex, $L$-smooth $f$, plain gradient descent with $\eta = 1/L$ satisfies $f(x_t) - f^\star \le \frac{L\lVert x_0 - x^\star\rVert^2}{2t}$ — a global guarantee from purely local steps, with no initialization cleverness required. Add strong convexity and the rate becomes geometric. Lose convexity and the honest statement collapses to: gradient descent converges to a stationary point, $\lVert \nabla f \rVert \to 0$ — which could be a minimum, a plateau, or a saddle. The gap between those two statements is the intellectual territory of this module.

Exercises