A convex function has a single valley: every downhill walk ends at the same global minimum, and the math can prove it. A non-convex one has many valleys, so the starting point helps pick your ending — and deep learning lives there anyway.
A set is convex when the straight segment between any two of its points stays inside. Boxes, balls and half-spaces pass; donuts, crescents and unions fail. Feasible regions built from budget limits are intersections of half-spaces — and intersections of convex sets are always convex.
t·x + (1−t)·y ∈ S for every t in [0, 1]Connect any two graph points with a straight chord. Convex means the chord never dips below the curve — equivalently f″ ≥ 0 in 1D, or a positive-semidefinite Hessian in many variables. The same statement is Jensen's inequality: averaging inputs can only undershoot averaging outputs.
f(tx + (1−t)y) ≤ t·f(x) + (1−t)·f(y)L2 regularization constrains weights to a circle: the loss contour kisses it smoothly, so weights shrink but stay nonzero. L1 constrains them to a diamond: the first touch is a corner on an axis, so a weight becomes exactly zero. Same idea, different geometry, different model.
diamond → sparse · circle → smallConvexity is a promise — average in, average out, one valley, every local bottom is the global one — and it holds for anything built from quadratics, norms, log-sum-exp and pointwise maxima. The moment you stack nonlinear layers, the promise is off, the start decides, and the surprise is that noisy descent still finds a good valley.
By the end you will be able to test convexity by chord, derivative or Hessian; explain why a convex model has one answer and where the guarantee breaks; tell positive semidefinite from a saddle; read λ as the price of a constraint; and see why L1 zeros weights while the SVM margin depends only on its support vectors.
Convexity starts with a geometric promise: averaging two allowed points is also allowed, and averaging two outputs never beats averaging the outputs. That promise is what makes a whole class of problems easy.
Before any function, a set. A set S is convex if for any two points x and y in S, the straight segment between them also lies in S. In one line: every blend t·x + (1 − t)·y with t between 0 and 1 is still in S. You can always walk from any point to any other without stepping out.
A line, a plane, a rectangle, a ball and a half-space are all convex. So is the intersection of any number of convex sets — a parking-space region bounded by straight curbs is one big intersection of half-planes. A donut, a crescent, and the union of two separate circles are not: each has a hole or a gap that a straight segment can fall into.
A convex set has no dents and no holes: pick any two points and the straight segment between them never leaves.
A function f is convex when its domain is convex and the chord between any two graph points lies on or above the graph:
The usual cast of convex functions, each with its reason: x² (bends up everywhere), |x| and max(0, x) (V-shape, corner allowed), eˣ (its own derivative), −log x for x > 0 (bends up as it dives), and every linear function ax + b — which is both convex and concave, a straight line being the boundary case. Adding convex functions keeps convexity; multiplying them usually does not.
Which of these sets is convex?
One inequality decides convexity, and it is checkable by eye: draw a straight line between two points of the graph. If it ever dips below the curve, convexity is broken.
Take two points on a graph and connect them with a straight line — the chord. A function is convex exactly when every chord lies on or above the graph. The same statement in probability language is Jensen’s inequality: for weights that sum to 1, or more generally for an expectation,
The gap between the two sides is real and has a name for squares. With f(x) = x² and a fair coin between 1 and 3:
Pick two points on the graph and connect them with a straight chord. Convex means the chord never dips below the curve — at any point along the way, not only the midpoint.
For x³ try both points negative (the graph bends down there); for x⁴ − 3x² the middle hump is the giveaway.
All three tests answer the same question. Use the definition when you can only evaluate f, the second derivative when f is smooth in one variable, and the Hessian when there are several variables.
Which function fails the chord test somewhere on its domain?
This is the theorem the whole lesson exists for. Without it, training is a search with no guarantees. With it, walking downhill is a proof of optimality.
A local minimum is a point lower than everything nearby; a global minimum is the lowest point anywhere. For a convex function the two definitions collapse: every local minimum is global. Gradient descent cannot be trapped, so it cannot need a restart, a schedule, or a lucky seed. The answer it walks to is the answer.
Pick a function and a starting point, then run gradient descent. On a convex function every start funnels to the same bottom; on a non-convex one the start decides which valley you keep.
On x⁴ − 2x² + 0.35x, starting left of the hump settles at f ≈ −1.38, starting right of it at f ≈ −0.66 — same function, two different answers, and only one of them is the global minimum. The convex x² always ends at the one bottom, no matter where you start.
Suppose, for contradiction, that a convex f has a local minimum at x* that is not global. Then some point y has f(y) < f(x*).
The fine print. Neural networks are not convex. A network with a hidden layer and a nonlinearity like ReLU has a landscape full of peaks, valleys and saddles, and the value you reach depends on the initialization. The surprise is that this is not fatal:
A non-convex loss has two local minima, one with loss 2.0 and one with loss 2.1. What does gradient descent from a random start guarantee?
Convexity has two calculus fingerprints: every tangent plane lies below the graph, and every Hessian is positive semidefinite. The second one is also a roadmap for a much faster optimizer.
First-order condition. For a differentiable f, convexity is equivalent to this: at every point x, the tangent line (or plane) sits on or below the graph.
Second-order condition. In one variable, f″(x) ≥ 0 everywhere. In several variables the collection of second derivatives is a matrix — the Hessian — and it must be positive semidefinite (PSD) everywhere: all eigenvalues ≥ 0. For a symmetric 2×2 matrix [[a, b], [b, d]] there is a three-check shortcut: a ≥ 0, d ≥ 0, and a·d − b² ≥ 0.
The Hessian is the matrix of second derivatives. Move the evaluation point and watch the local quadratic model: ellipses mean curvature up both ways, hyperbola-like curves mean a saddle.
Try the quartic at (0, 0) — one eigenvalue is negative, so the origin is a saddle — then at (1, 0), where the local model is only semidefinite. Convexity needs PSD everywhere: one bad point is enough to break it.
Newton’s method turns the Hessian into an optimizer. Gradient descent takes a step proportional to the slope; Newton fits the local quadratic bowl and jumps straight to its bottom:
Take f(x, y) = 5x² + y², gradient (10x, 2y), Hessian diag(10, 2).
Rosenbrock check (and a correction). The classic test function f = (1 − x)² + 100(y − x²)² has Hessian [[2 + 1200x² − 400y, −400x], [−400x, 200]]. At the minimum (1, 1): [[802, −400], [−400, 200]], with eigenvalues ≈ 1001.6 and 0.4 — κ ≈ 2508, a valley 2,500 times narrower than it is long, which is why first-order methods zigzag there. The reference notebook’s answer to this exercise says (−1, 1) has a negative eigenvalue; recomputing gives [[802, 400], [400, 200]] there with eigenvalues 1001.6 and 0.4, both positive. A true saddle point on this surface is (0, 2), where the Hessian is [[−798, 0], [0, 200]] with eigenvalues −798 and 200 — one direction up, one down.
import random
def is_convex(f, dim, trials=1000, bounds=(-5, 5)):
"""Empirical chord test: return the first counterexample, if any."""
for _ in range(trials):
x = [random.uniform(*bounds) for _ in range(dim)]
y = [random.uniform(*bounds) for _ in range(dim)]
t = random.random()
mid = [t * a + (1 - t) * b for a, b in zip(x, y)]
if f(mid) > t * f(x) + (1 - t) * f(y) + 1e-10:
return False, (x, y, t)
return True, None
def newton_2d(grad, hess, x, steps=20):
"""x <- x - H^-1 g, using the 2x2 inverse from Lesson 02."""
for _ in range(steps):
g = grad(x)
(a, b), (c, d) = hess(x)
det = a * d - b * c
if abs(det) < 1e-15:
break
dx = [(d * g[0] - b * g[1]) / det,
(-c * g[0] + a * g[1]) / det]
x = [x[0] - dx[0], x[1] - dx[1]]
if g[0] ** 2 + g[1] ** 2 < 1e-12:
break
return x
# f = 5x^2 + y^2: grad (10x, 2y), hess [[10, 0], [0, 2]]
print(newton_2d(lambda v: [10 * v[0], 2 * v[1]],
lambda v: [[10, 0], [0, 2]], [10, 10])) # -> [0.0, 0.0]Most classical ML models are convex on purpose: least squares, ridge, LASSO, logistic regression and the SVM. Each one is built from quadratics, norms, log-sum-exp or a maximum of linear functions — pieces that preserve convexity.
Quadratics: least squares. Fitting a line means minimizing f(w) = ‖Xw − y‖², whose gradient is 2Xᵀ(Xw − y) and whose Hessian is 2XᵀX. That Hessian is always PSD, and the reason is a one-liner: for any direction z, zᵀXᵀXz = (Xz)ᵀ(Xz) = ‖Xz‖² ≥ 0 — a squared length cannot be negative. Least squares is convex no matter what data you feed it.
Norms. ‖w‖₁ and ‖w‖₂ are convex because they obey the triangle inequality ‖a + b‖ ≤ ‖a‖ + ‖b‖ and scale positively. Check it with w = (1, 2) and z = (2, −1): ‖w + z‖₁ = ‖(3, 1)‖₁ = 4, while ‖w‖₁ + ‖z‖₁ = 3 + 3 = 6, so 4 ≤ 6 ✓. Penalties built from norms therefore keep a loss convex while pulling weights toward zero.
Log-sum-exp: the soft maximum. Define LSE(x) = log(Σᵢ e^(xᵢ)). It is convex, it lies between the maximum and the maximum plus log n, and its gradient is the softmax function — so it is also the piece that makes cross-entropy well-behaved.
Logistic regression: convex where it matters. For a single example with score z = wᵀx and label y in {0, 1}, the negative log-likelihood collapses to log(1 + eᶻ) − y·z. Its second derivative in z is σ(z)·(1 − σ(z)) with σ(z) = 1/(1 + e^(−z)) — a product of two positive numbers, so ≥ 0. Composing with the linear score z = wᵀx keeps it convex in the weights.
The working convex vocabulary: quadratic, absolute value, exponential, negative log, and max(0, x). Corners are fine — a kink joins two upward pieces, so convexity survives.
| Problem | Convex? | Why |
|---|---|---|
| Linear regression (MSE) | Yes | Loss is quadratic in the weights |
| Logistic regression (log-loss) | Yes | log(1 + eᶻ) is convex in the linear score |
| SVM (hinge loss) | Yes | Maximum of linear functions |
| LASSO (L1) and ridge (L2) | Yes | Convex loss + convex penalty |
| Neural network, any depth | No | Nonlinear activations between layers |
| k-means | No | Discrete assignment step |
| Matrix factorization | No | Product of two unknowns |
Turn each rule around and it becomes a warning: a difference of convex functions, a product of two unknowns, or a composition through a non-linear non-convex function can all destroy the guarantee. That is exactly the line neural networks cross.
Real problems come with budgets, and a budget bends the answer. Lagrange multipliers turn the boundary into a number, and the KKT conditions tell you exactly which limits are actually doing work.
An unconstrained problem says “go as low as you can”. A constrained problem adds a rule: minimize f(x) subject to g(x) = 0 (equality) or gᵢ(x) ≤ 0 (inequality). The set of points that satisfy the rules is the feasible set, and the answer is the lowest point inside it.
Lagrange multipliers. For an equality constraint, bundle the rule into the objective with a new variable λ:
The circles are level sets of f; the line is the constraint. The constrained minimum is the point where a circle first touches the line — and there the two gradients point along the same line.
Drag the line and the circle centre: the touch point slides until the two arrows line up. λ is the exchange rate — how much f would drop per unit of extra constraint budget.
Problem A (the lesson example). Minimize f(x, y) = x² + y² on the line x + y = 1.
Problem B (exercise 3). Minimize f(x, y) = (x − 3)² + (y − 3)² subject to x + 2y = 4 — the offset bowl from the lab.
KKT conditions. Inequality constraints gᵢ(x) ≤ 0 add a fourth rule. A point is optimal (under mild conditions) when:
At the optimum of a KKT problem, a constraint has g(x) = −4 and λ = 6. What must be true?
Regularization is constrained optimization in disguise, and the shape of the constraint explains sparsity: a diamond has corners on the axes, a circle does not. The same geometry gives the SVM its margin.
Penalty or budget, same problem. “Minimize loss + λ·‖w‖²” and “minimize loss subject to ‖w‖² ≤ t” describe the same family of answers — λ is the Lagrange multiplier of the budget, and choosing one pins down the other. In two dimensions the L2 budget is a circle and the L1 budget is a diamond (a square standing on a corner). The solution is where the smallest loss contour first touches the shape.
The shaded region is the budget; the circles are loss contours. Watch where the smallest contour touches: the diamond at a corner on an axis, the circle at a smooth point with both weights alive.
Both penalties shrink the weights; only L1 can switch a feature off. The corner is the whole story: it is the only place on a diamond where a coordinate can be exactly zero while still touching the boundary.
SVM margins. A support vector machine looks for the separating line (or hyperplane) with the widest possible buffer. For a unit direction w and offset b, the constraints are yᵢ·(wᵀxᵢ + b) ≥ 1; the band between the two dashed lines has width 2/‖w‖. Maximizing the margin is the same as minimizing ‖w‖², so the SVM is a convex quadratic program — and it is the constrained optimization behind the most famous KKT example in ML.
This dataset has a perfect separating line at angle 0. Tilt or shift it and the margin collapses; put it back and the two ringed support vectors alone are holding the boundary in place.
Max-margin at angle 0, b = 0: margin 2, support vectors (1, 0) and (−1, 0). The four handier points have slack ≥ 2 and never appear in the SVM solution — that is complementary slackness in action.
Every constrained problem has a companion dual: maximize over λ ≥ 0 the minimum over x of the Lagrangian. For convex problems the two optima are equal (strong duality), so you may solve whichever is easier. The SVM dual depends on the data only through dot products xᵢᵀxⱼ, and those dot products can be replaced by a similarity function K(xᵢ, xⱼ). That is the kernel trick: a linear method becomes nonlinear without ever building the high-dimensional feature map, because no coefficient ever needs the map explicitly — only the pairwise similarities.
Answer before you look. The complementary-slackness and non-convex-SGD questions are the ones that separate remembering the words from knowing what they do.
0 / 5 answered · 0 correct
01What is the defining property of a convex function?
02Which of these ML problems has a convex loss landscape?
03Newton's method converges to the minimum of f(x) = 5x² + 3x + 1 in how many steps?
04In the KKT conditions, what does complementary slackness (λᵢ·gᵢ(x) = 0) mean?
05Why does SGD find good solutions in non-convex neural network landscapes despite the lack of convexity guarantees?
Click a card to swap the lazy description for what it actually means.
Four problems, all fully worked. The Rosenbrock correction lives in chapter 04; these solutions show every number.
x⁴: f″ = 12x² ≥ 0 everywhere, so convex (the graph flattens at 0 but never bends down). Chord check x = −1, y = 2, t = 0.5: midpoint 0.5, f = 0.0625; chord = 0.5·1 + 0.5·16 = 8.5; 0.0625 ≤ 8.5 ✓. sin x: f″ = −sin x changes sign, so neither convex nor concave; chord check x = 0, y = π, t = 0.5: midpoint π/2, f = 1, chord = 0.5·0 + 0.5·0 = 0, and 1 > 0 — the chord dips below the graph ✗. x² + y²: Hessian 2I has eigenvalues 2, 2 ≥ 0, so convex. x·y: Hessian [[0, 1], [1, 0]] has eigenvalues +1 and −1 — a saddle; check direction (1, 1): f = 1 > 0, direction (1, −1): f = −1 < 0 around the origin. max(x, 0): the maximum of two linear functions is convex (and ReLU inherits it), even though it has a corner at 0; chord check x = −2, y = 1, t = 0.5: midpoint −0.5, f = 0; chord = 0.5·0 + 0.5·1 = 0.5, and 0 ≤ 0.5 ✓.
Newton: ∇f = (100x, 2y) and H = diag(100, 2), so one step x ← x − H⁻¹∇f maps (10, 10) to (0, 0) exactly; the loss is 0 after step 1 because the model is the function. Gradient descent: x ← (1 − 100·lr)·x and y ← (1 − 2·lr)·y, stable only for lr < 0.02. Take lr = 0.015: the x factor is −0.5, so |x| halves each step, while the y factor is 0.97. The y coordinate dominates the loss: 10·0.97ⁿ < 10⁻⁵ needs n = ln(10⁻⁶)/ln(0.97) ≈ 453.6, so about 454 steps — roughly 454× more work than Newton. The Hessian eigenvalues are 100 and 2, so the condition number κ = 50; the number of descent steps grows roughly in proportion to κ, while Newton does not care. At lr = 0.02 or above the x update has |factor| ≥ 1 and the run diverges.
Form L = (x − 3)² + (y − 3)² + λ(x + 2y − 4). Stationarity: ∂L/∂x = 2(x − 3) + λ = 0 → x = 3 − λ/2; ∂L/∂y = 2(y − 3) + 2λ = 0 → y = 3 − λ. The constraint gives (3 − λ/2) + 2(3 − λ) = 4 → 9 − 5λ/2 = 4 → λ = 2, so (x, y) = (2, 1). Checks: 2 + 2·1 = 4 ✓; f(2, 1) = 1 + 4 = 5; ∇f = (2(2 − 3), 2(1 − 3)) = (−2, −4) and ∇g = (1, 2), so ∇f = −2·∇g — parallel with λ = 2 ✓. A nearby feasible point (2.4, 0.8): f = (−0.6)² + (−2.2)² = 0.36 + 4.84 = 5.2 > 5, confirming the minimum; the unconstrained minimizer (3, 3) is not on the line at all (3 + 6 = 9 ≠ 4).
The unconstrained minimizer (3, 2) has |3| + |2| = 5 > 1, so the solution sits on the diamond's boundary. Check the four corners: (1, 0) → 4 + 4 = 8; (0, 1) → 9 + 1 = 10; (−1, 0) → 16 + 4 = 20; (0, −1) → 9 + 9 = 18. A generic edge point (0.8, 0.2) gives 2.2² + 1.8² = 4.84 + 3.24 = 8.08 > 8, so the corner (1, 0) wins, with f = 8 and y = 0 exactly. At (1, 0) the constraint x + y ≤ 1 is active, ∇f = (−4, −4) is parallel to ∇g = (1, 1) (λ = 4), and complementary slackness holds. The diamond's corners lie on the axes, and the loss contours — circles around (3, 2) — reach the constraint set first at that corner. A circle constraint has no corners, so the tangency point is generally smooth with both coordinates nonzero: for ‖w‖₂ ≤ 1 the closest point to (3, 2) is (3, 2)/√13 ≈ (0.83, 0.55) and neither weight is zero. Sparsity is a property of the constraint's shape, not of the penalty constant.
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 01, Lesson 18) and the Math Foundations Notebook reference build. The rolling-bowl hero, chord test, landscape explorer, Hessian checker, Lagrange geometry, L1-vs-L2 and SVM-margin labs are original to this page, as are the convexity gallery, the extra numeric checks inside every derivation, and the correction to the reference notebook's Rosenbrock eigenvalue claim (the saddle used here is (0, 2), not (−1, 1)). Every displayed number is computed in your browser from the values shown. All labs run in your browser.