Convex Optimization: One Valley Guaranteed, But You Still Need to Walk It Right - AI Engineering Foundations 18

Forum topic · 小凯 · 2026-10-14

Summary

A detailed lesson-by-lesson walkthrough of Lesson 18 (Convex Optimization, 90 minutes, Build-type) from the open-source course AI Engineering from Scratch (58k GitHub stars, MIT license). The author explains how to recognize convex functions (convex sets, chord tests, Hessian eigenvalues), why local minima equal global minima in convex landscapes, and demonstrates hands-on that the famous guarantee covers only the destination, not the step size: gradient descent with learning rate 0.25 diverges even on a mild bowl with condition number 5, while optimal rates converge in 37-684 steps depending on tuning. The post covers Newton's method (one exact step on quadratics at huge memory cost), Lagrange multipliers and KKT conditions, the geometric origin of LASSO sparsity (diamond corners on axes), duality and the kernel trick in SVMs, and three reasons deep learning thrives despite non-convexity. Key numbers: condition number 50 needs 357 steps vs Newton's single step; Rosenbrock Hessian eigenvalues identical at minimum and non-stationary points.

Convex Optimization: One Valley Guaranteed, But You Still Need to Walk It Right

This is lesson 18 (Convex Optimization, Build-type, 90 minutes, prerequisites: calculus and gradient descent) from the series covering the open-source course AI Engineering from Scratch (MIT license, 58k stars on GitHub).

The Course's Boast

The course opens with a boast: convex optimization is the only area of machine learning that dares to write a guarantee - no restarts, no learning-rate schedules, no praying.

Linear regression, logistic regression, SVM, LASSO, and ridge regression all live in this safe. The guarantee is simple: the entire loss landscape has only one valley. Any descent algorithm ends at the same bottom.

The first two and a half claims are true. The last one, the author tests by hand.

Recognizing a Bowl

Three ways to identify a convex function, from cheap to expensive:

1. Convex sets: a set is convex iff the line segment between any two points stays inside. Circles are convex, donuts are not. Convex sets are closed under intersection. 2. Chord test: the line between any two points on the graph must lie above or touch the curve. sin fails. In 1D: second derivative nonnegative everywhere. x² has second derivative 2 (convex); x³ has 6x, negative on the left half-axis (not convex). 3. Hessian test: the matrix of all second partial derivatives must have all eigenvalues nonnegative - "how hard the surface bends" along each direction.

The textbook's practice example f(x, y) = x² + 3xy + y² has Hessian [[2, 3], [3, 2]] with eigenvalues 5 and −1 - mixed signs, meaning it's a saddle surface. The textbook never points out that its own exercise is a ready-made saddle point example.

What the Guarantee Does and Doesn't Promise

The central theorem: a local minimum is the global minimum. No restarts needed; initialization doesn't matter.

"No praying"? Running gradient descent on the course's Build-It bowl f = 5x² + y² (Hessian diag(10, 2), condition number only 5):

Learning rate 0.25: diverges past double overflow to inf within two steps. The red line 2/λmax = 0.2 still applies on convex bowls.
Learning rate 0.19: 139 steps to 10⁻¹⁰.
Optimal rate 1/6: 37 steps.
Learning rate 0.01: 684 steps.

Same bowl, same start - an order-of-magnitude difference in fate depending on step size. Convexity guarantees only that the valley is unique, not your stride. The course itself recommends L-BFGS-B, a solver with built-in line search. Honest engineering: convexity handles *where*, the solver handles *how*.

Newton's Method: The Price of One-Step Arrival

Newton's method uses second-order information: x_new = x − H⁻¹∇f. On quadratics it is exact - one step to zero, not an approximation.

The cost is scale: for a million parameters, the Hessian has 10¹² elements and inversion costs ~10¹⁸ operations. Deep learning can't afford it; moderately sized convex problems get crushed by it. Exercise 2 (50x² + y², condition number 50, start at (10, 10)): Newton takes one step; gradient descent with the precisely optimal learning rate needs 357 steps to reach 10⁻¹⁰.

A quiet easter egg in exercise 5: the Rosenbrock function has identical Hessian eigenvalues at (1, 1) and (−1, 1) - 1001.6 and 0.399, condition number ~2500. But (1, 1) is the global minimum (gradient exactly zero), while (−1, 1) isn't even a stationary point (gradient (−4, 0)). Curvature tells you the shape of the ground; whether you're at the bottom requires the first derivative.

Valleys with Walls

Constrained problems use Lagrange multipliers: fold the constraint into the objective with a "price" variable λ. The textbook example (minimize x² + y², subject to x + y = 1) checks out: solution (0.5, 0.5), λ = −1 - the foot of the perpendicular from the origin to the line. Geometric intuition: at the optimum, the objective's gradient is parallel to the constraint wall's gradient.

For inequality constraints, the KKT conditions apply. Complementary slackness: each constraint either binds (λ > 0, actively managing) or its multiplier is zero (unused). SVM support vectors are the first kind - the entire decision boundary rests on just those points.

Diamond Corners Land on the Axes

Ridge regression: find the lowest-loss point inside a circle - smooth boundary, weights shrink but all survive. LASSO: inside a diamond (|w₁| + |w₂| ≤ t) with four corners exactly on the coordinate axes. Elliptical contours are surprisingly likely to hit a corner - and hitting one zeroes the corresponding weight exactly. Sparsity is not L1 magic; it's geometric inevitability.

Exercise 4 numerically: minimize (x−3)² + (y−2)² subject to |x| + |y| ≤ 1. Optimal solution: (1, 0) - y is strictly zero.

Duality: The Problem's Shadow

Every constrained problem has a dual. For convex problems, strong duality holds - same optimal value (the glossary adds the Slater condition, which the main text omits). The most beautiful application is in SVM: the dual depends only on pairwise dot products xᵢ·xⱼ, which the kernel trick replaces with K(xᵢ, xⱼ) for high-dimensional separability without explicit features.

The textbook's honest aside - "the solution is unique (unless there are flat regions)" - is alive: max(0, x) is convex but its entire negative half-axis is a plateau of global minima. Strict uniqueness belongs to strictly convex functions; LASSO can also have multiple solutions when features outnumber samples.

Why the Non-Convex World Doesn't Collapse

Neural networks violate every convexity guarantee, yet SGD keeps finding good solutions. Three reasons:

1. Critical points that are true minima are rare: the probability all n Hessian eigenvalues are positive is roughly 2⁻ⁿ. In million-dimensional spaces, most critical points are saddle points - and SGD's noise slips off saddles easily. 2. Over-parameterization flattens and connects the landscape. 3. Minibatch noise favors flat minima: "sharp minima overfit, flat minima generalize" is a useful rule of thumb since the 1990s - though recent research finds counterexamples via reparameterization, so it is not a theorem.

Back to the Boast

Exercise 2's answer: as the condition number grows from 5 to 50, steps at the optimal learning rate grow from 37 to 357. Each step compresses error by at most (κ−1)/(κ+1), which approaches 1 as κ grows - nearly wasted steps, even in the best-case convex terrain.

The correct reading of the boast: the valley really is unique, restarts really aren't needed, and the learning-rate schedule really can be dropped - as long as you hand your stride to a solver with line search. Convexity guarantees where; the solver manages how.