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.

Deep learning's loss surface is non-convex — with a proof

That a neural network's loss function (input: the parameters; output: the training error) is not convex can be shown by a short argument, not just a vibe. The key is permutation symmetry.

Swap hidden neuron #1 with hidden neuron #2 — carrying their attached weights along — and the network computes exactly the same function. So parameter space contains a huge number of distinct locations with exactly equal loss. Now take a minimum $\theta_A$ and one of its permuted copies $\theta_B$, and consider the midpoint of the segment between them. If the loss were convex, equation (2) says the midpoint's loss is at most that of the endpoints — the midpoint would be a minimum too. In reality the midpoint is a half-and-half mixture of mismatched weights, and its loss jumps sharply. The definition of convexity is violated, so the loss surface is not convex. QED.

With convexity gone, every textbook guarantee evaporates. A point of zero gradient (a critical point) need not be the bottom. So what does gradient descent actually get stuck on? For years the standard answer was "local minima." Then, in the mid-2010s, that folklore got overturned.

The real villain isn't local minima — it's saddle points

Critical points can be classified by the eigenvalues of the Hessian, the matrix of second derivatives (for what eigenvalues and eigenvectors mean in the first place, see Linear Algebra for AI). Each eigenvalue tells you how the surface curves along one direction:

• all eigenvalues positive → curves upward every way you slice it: a local minimum (a hollow)
• all eigenvalues negative → curves downward every way: a local maximum (a peak)
• mixed signs → a valley in some directions, a ridge in others: a saddle point

A saddle point is shaped like a horse's saddle — dipping front-to-back, rising side-to-side. The gradient there is zero, so gradient descent slows to a crawl and seems stuck, yet a downhill escape direction still exists.

This is where high dimensionality kicks in. Dauphin et al. (2014), drawing on random matrix theory from physics, argued as follows. With a million parameters, a critical point can only be a local minimum if all one million eigenvalues are positive — a coincidence like flipping a million coins and getting all heads, vanishingly unlikely in regions where the loss is still high. So in high dimensions, the overwhelming majority of critical points that impede training are saddle points, not local minima.

And that is good news. A saddle always has an escape route (the direction of a negative eigenvalue), and the noise that SGD (stochastic gradient descent) injects with every mini-batch tends to shove the parameters onto it. One reason non-convex optimization succeeds despite the theory saying "no guarantees": the enemy turned out to be not a dead end, but a landing with a hidden staircase.

Not all valleys are equal — flat minima

A non-convex landscape has many valleys, which raises a new question: if two valleys are equally deep, does it matter which one you land in?

Apparently, yes. The clue is the valley's width. A sharp minimum shaped like a slot canyon and a flat minimum shaped like a broad basin can have the same training error yet perform differently on unseen (test) data — the flat one tends to generalize better. This hypothesis is decades old; Keskar et al. (2017) gave it modern teeth by studying why very large batch sizes hurt test accuracy, observing that large batches — with less SGD noise — tend to fall into sharp valleys.

The intuition: training data and test data are similar but not identical, so at test time the loss surface shifts slightly sideways. Standing at the bottom of a slot canyon, even a small shift slams you into a wall. At the bottom of a basin, a small shift leaves you still at the bottom.

SAM (Sharpness-Aware Minimization, 2021) bakes this idea into the training algorithm itself: instead of lowering the loss at the current point, it lowers the loss at the worst point in a small neighborhood, explicitly seeking flat valleys. In fairness, there is a theoretical critique that "flatness" changes with how you scale the parameters (reparameterization), and what truly explains generalization remains an active research question.

See it in code — the dead water around a saddle

The feeling of "stall, then escape" needs only two variables. $f(x,y) = x^2 - y^2$ has a saddle at the origin (a valley along $x$, a ridge along $y$).

import numpy as np

w = np.array([1.0, 1e-8])          # start almost exactly on the ridge
for t in range(60):
    g = np.array([2*w[0], -2*w[1]])  # gradient of f = x^2 - y^2
    w -= 0.1 * g
    if t % 10 == 0:
        print(t, w)

Run it and $x$ collapses to 0 within a few steps, while $y$ grows from $10^{-8}$ at a glacial pace — for a long stretch the point barely moves near the origin. Judged by gradient norm alone it looks "converged": that is the dead water of a saddle. Change the initial $10^{-8}$ to $10^{-2}$ — simulating a noise kick off the ridge — and the escape happens dramatically sooner.

How this is used in practice

This terrain view feeds directly into the daily judgment calls of anyone training models.

• Don't diagnose "loss stopped falling" as a local minimum. Reflexively lowering the learning rate at a plateau can be exactly wrong. If you are in the dead water of a saddle or plateau, what you need is a push: momentum=0.9 in torch.optim.SGD, a learning-rate warmup, or a temporary bump (warm restarts). Lower the rate and you take up permanent residence in the stall.
• When you raise the batch size, audit generalization in the same breath. If test accuracy drops right after scaling to large batches, suspect sharp minima and consider learning-rate scaling or SAM-style methods (rho is the neighborhood-radius knob) — a standard checklist item for ML engineers setting up distributed training.
• The Adam-vs-SGD choice is also about terrain. Adam handles wildly different curvatures per direction (ill-conditioning) and is fast early on, while SGD with momentum has repeatedly been reported to win on final generalization; choosing AdamW (the correct way to apply weight_decay) is part of the same conversation.
• A classic interview question — "the loss surface is non-convex, so why can deep networks be trained at all?" — can be answered straight from this article: (1) in high dimensions most bad critical points are saddles with escape directions, (2) SGD's noise helps take them, and (3) you never needed the global optimum anyway — a good flat valley is enough.

Takeaways

• Convexity means "the chord between any two points lies above the graph." For convex functions, local = global, and gradient descent comes with guarantees
• Deep learning's loss surface is non-convex — permutation symmetry proves it — so those guarantees vanish
• But in high dimensions, most critical points in the way are not dead-end local minima; they are saddle points with escape routes, and SGD's noise helps find them
• Which valley you land in matters: flat minima are believed to generalize better, and methods like SAM seek them on purpose

Gradient descent itself is derived in Loss Functions and Optimization, and the calculus underneath it in Calculus for AI. To dig into why flat valleys survive the shift to real-world data, continue with Overfitting and Evaluation Design.