Convexity and Optimization — Why Deep Learning Works Even Though It Isn't Convex

Optimization textbooks teach a stark divide: convex problems are solvable, non-convex ones come with no guarantees. So why does deep learning — whose loss surface is provably non-convex — work at all? From convex sets and functions to saddle points and flat minima, this article connects the whole story in the language of landscapes.

Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

The bottom of a bowl, and a mountain range in fog

Imagine playing a game blindfolded: find the lowest point around, using only the slope you feel under your feet.

If the arena is the inside of a salad bowl, the game is easy. Wherever you stand, keep walking downhill and you will reach the bottom — the one and only bottom.

If the arena is a mountain range shrouded in fog, all bets are off. Is the hollow you just walked into really the deepest valley, or just a puddle? The slope under your feet cannot tell you. You might even end up on a strange flat spot along a ridge, with no idea which way to go.

Convexity is the mathematical concept that separates the bowl from the mountains. And the loss surface of deep learning is, unmistakably, the mountains. Yet gradient descent — a method that does nothing but "walk downhill from where you stand" — works remarkably well in practice. This article unravels that puzzle in the language of terrain.

Convex sets and convex functions — shapes with no dents

Two foundational definitions first. Both boil down to nothing more than "connect two points with a line."

A convex set is a region with no dents. A set $C$ is convex when

In plain words: pick any two points $x, y$ inside $C$ and draw the straight segment between them — the entire segment stays inside $C$. Here $\lambda$ (lambda) is a fraction between 0 and 1 marking a position along the segment (0.5 is the midpoint). A disk is convex; a crescent moon is not, because the segment cuts across the missing part.

A convex function is one whose graph is bowl-shaped. A function $f$ is convex when

In plain words: connect any two points on the graph with a chord (a straight line), and the graph always lies on or below that chord. The left side is "the function's value at a blend of the two points"; the right side is "the blend of the function's values," i.e. the height of the chord. The everyday observation that a bowl sags below its rim-to-rim string is the definition. $f(x)=x^2$ is convex; $\sin x$ is not.

If a one-variable function is twice differentiable, the test gets even simpler: $f''(x) \ge 0$ everywhere means convex. If the slope never stops increasing — never turns back downward — the shape is guaranteed to be a bowl.

What convexity buys you

Convex functions have a property that optimization can only dream of elsewhere:

Every local minimum is a global minimum.

Find a spot where no direction leads downhill, and you are guaranteed to be standing at the true bottom. Inside a bowl, being fooled by a puddle simply cannot happen. The reason falls straight out of the definition: if some point B were lower than your bottom A, the chord from A to B would dip below A along the way, so points near A would be lower than A — contradicting "A is a local minimum."

For differentiable convex functions there is also the first-order condition:

In plain words: draw the tangent plane (tangent line) at any point $x$, and the entire function sits above it. $\nabla f(x)$ (nabla, the gradient) is the vector pointing in the steepest uphill direction at $x$. The power of this inequality: plug in $\nabla f(x) = 0$ and the right side collapses to $f(x)$, proving in one line that "a point with zero gradient is a global minimum."

That is why convex problems — linear regression, logistic regression — are safe territory: gradient descent reaches the same answer from any starting point. Feel that safe world for yourself first.

Everything so far is the first half of the textbook: "convex means solvable." The trouble is that deep learning lives outside this safe world.