Convexity

You're training a model.

Training means nudging the parameters over and over, chasing the lowest loss.

You already know how to chase: the gradient points steepest uphill, so you walk the opposite way (Topic 11 — it packs all the partial derivatives into one direction vector).

But eventually the loss stops going down. And now the uncomfortable question:

Picture a crumpled landscape with many valleys:

code
Copy
  loss
   ▲
   │   ╲╱╲         ╲╱
   │  ╱  ╲ ╲       ╱  ╲   ← a deeper valley
   │ ╱    ╲ ╲_____╱    ╲     hidden over the ridge?
   │╱      ╲___╱
   │    you stopped here
   └───────────────────────────► parameters

You can only feel the slope under your feet. You can't see over any ridge. In this landscape, "I stopped improving" does NOT mean "I found the bottom."

So one magic question splits all of optimization in two:

If yes — the surface is convex: one smooth bowl, one valley. Gradient descent comes with a promise.

If no — the surface is an egg carton of many cups, and the marble settles wherever you dropped it. That is non-convex — the world of deep learning.

This topic: what convexity really means, how to test it, and why AI gives it up on purpose and trains anyway.

Two definitions build on each other.

Convex set — a shape with no dents:

Disks, rectangles, and half-planes are convex. A crescent or a ring is not — the line between two points can jump outside the shape.

Convex function — a graph that bends upward:

f(tx + (1−t)y) ≤ t·f(x) + (1−t)·f(y)

Unpack it piece by piece:

• x and y: any two input points.
• t: a slider from 0 to 1. tx + (1−t)y is a point on the segment between them.
• Left side: the height of the function at that in-between point.
• Right side: the height of the chord (straight line) connecting the two endpoints, at the same spot.
• The inequality says: the chord never dips below the curve.

code
Copy
  value
    │  ●─ ─ ─ ─ ─ ─●     ← chord: straight line
    │   ╲         ╱
    │    ╲  ╱‾╲  ╱       ← curve: the graph sags
    │     ╲____╱          BELOW the chord
    │   ●           ●     ← the two chosen points x, y
    └──────────────────────► input

Same fact in one more translation: the region above the curve — the epigraph — is a convex set.

The classics: x², |x|, eˣ, x log x are convex. Flip the sign and you get concave functions (those where −f is convex): log x and sqrt x.

One warning: convexity is not about being positive, and not about looking U-shaped near one point. It is a global promise — the chord rule must hold for every pair of points across the entire domain.

Let's actually check the chord rule with numbers. It takes one minute.

Test 1 — f(x) = x², the friendly bowl. Pick the two extreme points x = −3 and y = 3.

• Both endpoints have height 9, so the chord is a flat line at height 9.
• The rule demands: f of any in-between point ≤ 9.
• Try t = 0.5: the point is 0, and f(0) = 0 ≤ 9 ✓
• Try t = 0.25: the point is 1.5, and f(1.5) = 2.25 ≤ 9 ✓
• Squaring anything between −3 and 3 stays at most 9. Passes everywhere. Convex.

Test 2 — g(x) = x⁴ − x², the sneaky one. Near large x the x⁴ term wins (it shoots up), but near 0 the −x² term wins (a little hill).

Pick x = −0.5, y = 0.5, t = 0.5:

• Midpoint of the inputs: 0. Curve side: g(0) = 0.
• Endpoints: g(±0.5) = 0.0625 − 0.25 = −0.1875. Chord side: the average is −0.1875.
• The rule demands 0 ≤ −0.1875. False!

The chord dips below the graph — exactly the bump of a tiny hill at 0. One broken pair is enough: convexity demands the rule hold for every pair everywhere. x⁴ − x² is not convex, even though it is U-shaped far from the origin.

That is the whole lesson: local U-shape ≠ convexity. The marble question ("does it always roll to the same bottom?") can fail because of one small hill you can barely see.

Checking chords one pair at a time is hopeless for real functions. For differentiable functions, three equivalent-style tests are used constantly in ML modeling:

1. First-order test (the tangent trick): f is convex iff it lies above every tangent plane: f(y) ≥ f(x) + ∇f(x)ᵀ(y − x) for all x, y. The tangent line is a global under-estimator of the function.
2. Second-order test (the curvature check): twice-differentiable f is convex iff its Hessian is positive semidefinite everywhere on the domain (the Hessian — the matrix of second derivatives — is Topic 13). For x²: H = 2 > 0, convex. For x⁴ − x²: the second derivative is 12x² − 2, which goes negative near 0 — not convex, matching our −0.1875 counterexample.
3. Closure rules (Lego for proofs): non-negative weighted sums, composition with affine maps, maxima of convex families, and partial minimization all preserve convexity. Build big convex functions from small known ones.

Key ML examples to memorize:

• MSE for linear regression: convex (quadratic in the weights, PSD Hessian).
• Logistic / softmax cross-entropy loss: convex in the logits (log-sum-exp is convex — it is the smooth maximum).
• Hinge loss (SVM): convex but not differentiable at the margin.
• eˣ, −log x (barrier), x log x: convex building blocks of information-theoretic losses.

import numpy as np

def jensen_holds(f, x, y, ts=np.linspace(0, 1, 101)):
    for t in ts:
        z = t * x + (1 - t) * y
        if f(z) > t * f(x) + (1 - t) * f(y) + 1e-12:
            return False
    return True

x, y = -3.0, 3.0
print("x^2 convex?  ", jensen_holds(lambda v: v**2, x, y))        # True
print("cos convex?  ", jensen_holds(np.cos, x, y))                # False
print("exp convex?  ", jensen_holds(np.exp, x, y))                # True

Carry one picture through everything: a marble on a surface.

code
Copy
     CONVEX (bowl)                NON-CONVEX (egg carton)

        ╲          ╱                ╲_╱ ╲_╱ ╲_╱
         ╲   ●→→→ ╱← rolls here     ╲_╱ ╲_╱ ╲_╱
          ╲_____═╱                    ╲_╱ ● ╲_╱
         one bottom, always           ╲_╱ ╲_╱ ╲_╱
                                     stuck in whatever cup
                                     it started in

In the bowl, the downhill direction −∇L funnels the marble to the same unique bottom no matter where you place it. Gradient descent IS the marble.

In the carton, every cup is a perfectly good local bottom. The marble freezes in the first cup it entered — which one depends entirely on where you started (initialization) and how you walked (the optimizer).

Notice what the two pictures are guarantees about:

• Convex: the answer to "did I find the best valley?" is yes, by construction — math backs you.
• Non-convex: the answer is "probably good, no proof" — you rely on empirical behavior instead of theorems.

Keep the marble in mind for the next two sections: it explains both why convex people are smug and why deep-learning people obsess over initialization.

Convexity is the boundary between optimization problems we can solve reliably and problems we must solve hopefully:

• Every local minimum is a global minimum. There are no deceptive valleys; a method that stops improving has truly converged. The marble can't get stuck in a bad cup because there is only one cup: the whole bowl.
• Gradient descent comes with rates. For L-smooth, μ-strongly convex objectives, GD converges at rate ((κ−1)/(κ+1))ᵏ per step where κ = L/μ is the condition number; accelerated methods (Nesterov) reach O(1/k²).
• Duality is clean. Convex problems with inequality constraints have Lagrangian duals; weak duality always holds, and strong duality (zero gap) holds under Slater's condition — this is exactly how the SVM dual and kernel machines are derived.
• Verification: you can certify solutions, which matters for engineering systems, control, and convex relaxations (semidefinite and linear-programming relaxations appear in robust ML and combinatorics).

Strict convexity (a unique minimizer) and strong convexity (curvature bounded below by μ > 0) are the upgrades that buy fast, stable convergence — the reason L2 regularization is not just a modeling trick but an optimizer's friend. It literally adds λ‖w‖² curvature to the bowl, deepening the bottom so nothing stays flat.

Here is the twist. A neural network with even one hidden ReLU layer and two weight matrices has products of parameters in its output — the loss is no longer convex in the weights. We deliberately threw away the bowl. So why does training work?

• Saddles beat bad minima. In high dimensions, critical points are far more likely to have mixed-sign Hessian eigenvalues (saddles — the marble balances on a pass, not a cup) than all-positive ones; gradient noise helps escape them (Dauphin et al., 2014).
• Overparameterization helps. With abundant parameters, local minima found by SGD empirically generalize well, and much of the landscape flattens into wide, good valleys.
• No free ride. Non-convexity is exactly why initialization, learning-rate schedules, normalization layers, and careful architectures matter: they shape the carton SGD must navigate — where the cups are and how deep they run.
• Convexity still sneaks in: linear probes, logistic heads, optimal transport losses, kernel methods, and convex relaxations for verification of trained networks all exploit the convex toolkit.

So the honest summary: convexity gives guarantees; breaking it buys expressiveness (hierarchy, attention, generation); and the missing guarantees get paid back with engineering discipline — init schemes, schedules, normalization, and monitoring.