1.9 Convexity and the shape of loss surfaces

What this is and why it exists

When an optimizer stops, did it find THE answer or AN answer? Convexity is the property that makes those the same thing — and knowing whether your problem has it tells you how much to trust a converged loss. This topic maps the loss-surface landscape: convex bowls where guarantees live, and the non-convex terrain of deep learning, which works anyway for reasons worth stating honestly.

The vocabulary

• Convex set — contains the whole line segment between any two of its points; no dents.
• Convex function — the chord between any two graph points lies on or above the graph; bowl-shaped, with no false valleys.
• Local vs global minimum — the best point in a neighbourhood versus the best point anywhere; convexity makes every local one global.
• Saddle point — flat but not a minimum: downhill exists in some direction (ca1's mixed Hessian).
• Plateau — a wide, nearly flat region where gradients are tiny and progress crawls.
• Lipschitz continuity — a speed limit on how fast the function (or its gradient) can change; the constant that calibrates safe step sizes.

The mental model

Convexity is the no-false-valleys guarantee. In a convex bowl, any point where descent cannot improve is THE bottom — a converged optimizer has provably finished. Linear regression's squared loss, logistic regression, SVMs: convex, which is why classical ML came with theorems. The chord test is the working definition, and a twice-differentiable function is convex exactly when its Hessian is positive semidefinite everywhere — la4's language again: bowl-shaped in every direction, at every point.

Deep losses are NOT convex: compose linear maps with nonlinearities and symmetries alone (swap two hidden units — same function, different weights) manufacture multitudes of minima. So why does training work? The honest, evidence-shaped answers: in very high dimensions the typical zero-gradient hazard is a SADDLE, not a bad minimum — some direction descends, and noisy gradients (ca4's stochasticity) jiggle you off the flat spot; empirically, the local minima of big networks tend to be of similar, good quality, so WHICH valley you land in matters less than classical fears assumed; and plateaus — vast flat mezzanines — waste more of training's time than false valleys do, which is why optimizer design obsesses over speed on flats. "Non-convex and still trainable" is an empirical fact with partial theory, and it is honest to say so.

Lipschitz thinking calibrates the step size. A bound on how fast the GRADIENT can change is a bound on how quickly the slope you measured goes stale — steps should be roughly the reciprocal of that bound. Step too far and you leap across the valley to higher ground: divergence (ca4's symptom list). The named constant rarely gets computed for a real network, but the intuition — sharper curvature demands smaller steps — is the daily bread of learning-rate tuning.

What you should now be able to explain or do

Test convexity by chord or by Hessian on small examples. State what convexity buys a converged optimizer. Give the two honest reasons deep training works without it, and say why saddles beat bad minima as the typical hazard. Connect Lipschitz bounds to step-size choice in one sentence.

Check yourself