1.31 Convex sets and convex functions: study notes

Learn AI by Story

1. The idea in one sentence

A convex set has no dents (a straight line between any two of its points stays inside), and a convex function is shaped like a bowl (a straight line between any two points on its graph never dips below the graph), so a bowl-shaped loss has only one valley and rolling downhill is guaranteed to find the bottom.

2. The story from the video

Rohan drops a marble into a smooth bowl. Wherever he lets go, it rolls to the same single lowest point. Then he drops it into an egg tray: the marble settles in whichever dimple is nearest, and most of those dimples are not the deepest one. The bowl is convex; the egg tray is not. Rohan learns that for a bowl, a local low point is the lowest point anywhere, while for an egg tray he can never be sure he has found the best spot. The same difference decides whether training a model is easy and guaranteed or tricky and luck-dependent.

3. Key definitions (glossary)

Line segment between x and y: all points of the form θx + (1−θ)y with θ between 0 and 1. Plain English: the straight bridge between two points; θ = 0 is at y, θ = 1 is at x, θ = ½ is the midpoint.
Convex combination: a point θx + (1−θ)y with 0 ≤ θ ≤ 1 (or, with more points, nonnegative weights that add to 1). Plain English: a weighted average.
Convex set C: a set where for every x, y in C and every θ in [0, 1], the point θx + (1−θ)y is also in C (Mathematics for Machine Learning, Def. 7.2). Plain English: no dents, no holes, no gaps; you can walk in a straight line between any two points without leaving.
Non-convex set: a set that fails this test for at least one pair of points, such as a crescent, a donut, or two separate blobs.
Convex function f: a function on a convex set where f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y) for all x, y and θ in [0, 1] (MML Def. 7.3). Plain English: the graph between two points lies on or below the straight chord joining them.
Strictly convex: the same inequality with < for x ≠ y and 0 < θ < 1. Plain English: no flat stretches; the bowl is curved everywhere. A strictly convex function has at most one minimiser.
Strongly convex: curves up at least as fast as a quadratic, f(y) ≥ f(x) + ∇f(x)ᵀ(y−x) + (m/2)‖y−x‖² for some m > 0. Plain English: a bowl that is guaranteed not to be too flat, which makes gradient descent converge fast (see 1.32).
Concave function: f is concave when −f is convex. Plain English: an upside-down bowl.
Epigraph: the set of points lying on or above the graph, {(x, t) : t ≥ f(x)}. A function is convex exactly when its epigraph is a convex set (MML sec. 7.3; Boyd sec. 3.1). Plain English: fill the bowl with water; the filled shape has no dents.
Gradient ∇f: the vector of partial derivatives; the direction of steepest increase.
Hessian ∇²f: the matrix of second partial derivatives (see 1.25). Plain English: how the slope itself bends in every direction.
Positive semidefinite (PSD): a symmetric matrix H with vᵀHv ≥ 0 for every vector v; equivalently all eigenvalues are ≥ 0. Plain English: it never bends downward in any direction.
Local minimum: a point no worse than all its close neighbours.
Global minimum: a point no worse than every point in the domain.
Jensen's inequality: for convex f, f(E[X]) ≤ E[f(X)]. Plain English: f of the average is at most the average of f; it is the convexity inequality extended to any weighted average or expectation.
Convex optimisation problem: minimise a convex function over a convex set (for constraints, convex inequality constraints and affine equality constraints).
Feasible set: the set of points that satisfy all the constraints.
Saddle point: a point where the gradient is zero but the surface curves up in one direction and down in another. Plain English: a mountain pass.
Duality / Lagrange dual: the companion problem built from Lagrange multipliers (1.30); for convex problems strong duality usually holds, so the primal and dual optimal values match (MML sec. 7.3; Boyd ch. 5).
Subgradient: a generalisation of the gradient at kinks (like the corner of abs(x)). Plain English: any slope of a line that touches the graph at that point and stays below it.
Projection: the closest point of a convex set to a given point; well defined and unique because the set is convex.

4. Detailed explanation, from basics to the full picture

Step 1: start with sets

Take any two points in a shape and draw the straight segment between them. If the segment never leaves the shape, for every pair, the shape is convex. A filled disc passes: take (1, 0) and (0, 1), which are on the unit circle; the midpoint (0.5, 0.5) is at distance 0.707 from the centre, which is less than 1, so it is inside. A crescent fails: pick one tip of each horn, and the straight line between them cuts across the empty hollow of the moon. Lines, planes, half-spaces, squares, balls and the whole space are all convex.

Step 2: functions inherit the idea through their graphs

Plot y = f(x). Pick two points on the curve and draw the chord. For a bowl (convex), the chord sits above the curve. For a hill-and-valley curve, the chord can sit below the curve somewhere in the middle, and that is the failure of convexity. The formula f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y) just says this: the left side is the height of the curve at the in-between point, the right side is the height of the chord there.

Step 3: the slope-based picture (first-order condition)

For a differentiable convex function, the tangent line at any point lies below the whole graph: f(y) ≥ f(x) + ∇f(x)ᵀ(y−x) (MML sec. 7.3). Why this matters: set the gradient to zero at a point x, and the inequality becomes f(y) ≥ f(x) for every y. So a point with zero gradient is not merely flat; it is the global minimum. That single fact is why convex optimisation is so well behaved.

Step 4: the curvature picture (second-order condition)

For one variable, f is convex exactly when f''(x) ≥ 0 everywhere. For many variables, f is convex exactly when the Hessian is PSD at every point (MML sec. 7.3; Boyd sec. 3.1). Reading the Hessian's eigenvalues tells you the bending along the principal directions: all positive means a bowl, mixed signs means a saddle, all negative means a hill.

Step 5: why local equals global

Suppose x is a local minimum of a convex f but some y has f(y) < f(x). Move a tiny step from x toward y: the point θy + (1−θ)x with θ small. Convexity says f there is at most θf(y) + (1−θ)f(x), which is strictly below f(x). But that point is arbitrarily close to x, contradicting x being a local minimum. So no such y exists. This is the argument behind d2l sec. 12.2 and Boyd sec. 4.2.2 ("Local and global optima").

Step 6: building convex functions from convex blocks

You rarely check the definition directly. Instead you assemble known convex pieces with operations that preserve convexity (Boyd sec. 3.1 and 3.2):

a sum of convex functions is convex;
a nonnegative multiple of a convex function is convex;
the maximum of convex functions is convex;
a convex function of an affine map (Wx + b) is convex;
norms are convex; exp(x), abs(x), x² and x to an even power are convex; log-sum-exp is convex (Boyd sec. 3.1).

An important caution: a composition of convex functions is not automatically convex (for example the sigmoid composed with something, or a neural network with nonlinear layers). Special rules are needed.

Step 7: constraints and projection

If the allowed region is a convex set, you can run gradient descent and, after each step, project back to the closest allowed point (d2l sec. 12.2; Goodfellow ch. 4.4 covers projected gradient descent). Convexity of the set guarantees that the projection is unique and that it never makes you worse off for convex f. This links directly to 1.30 (Lagrange multipliers): a convex objective with convex constraints makes the Lagrange/KKT conditions sufficient, not merely necessary (MML sec. 7.3).

5. Everything the video skipped

Variants and extra properties

Intersection of convex sets is convex (so a feasible region cut out by several convex constraints is convex). The union of convex sets is generally not convex.
Convex hull: the smallest convex set containing a collection of points (stretch a rubber band around nails). Every convex combination of the points lies in it.
Sublevel sets: for convex f, the set {x : f(x) ≤ c} is convex. The reverse is false: a function can have convex sublevel sets and still not be convex (these are called quasiconvex).
Strong convexity and smoothness: a function that is m-strongly convex and L-smooth (gradient changes no faster than L) has a condition number L/m that governs gradient descent speed. This is the bridge to 1.32.
Non-differentiable convex functions such as abs(x) and the hinge max(0, 1−z) have kinks; subgradients take the place of gradients there.
Log-sum-exp (1.29): convex, and satisfies max ≤ LSE ≤ max + ln n (Boyd sec. 3.1). This is why the smooth "soft maximum" is safe to optimise.

Formulas in simple words

Convex set: weighted average of two members is a member.
Convex function: the value at the average is at most the average of the values.
First-order test: the tangent line is a floor under the graph.
Second-order test: curvature is never negative (f'' ≥ 0, or Hessian PSD).
Jensen: f(mean) ≤ mean of f.

Limitations

Convexity is a strong, special property. Many interesting models, especially deep networks, give non-convex losses with many local minima, flat saddle regions and plateaus.
A convex function can have no minimum at all (for example eˣ only approaches 0), or a minimum that is reached along a whole flat segment (not strictly convex).
Convex does not mean fast. Very elongated bowls make plain gradient descent zigzag (1.32).

Background (history)

Background: the study of convex sets goes back to classical geometry, and optimisation over convex sets grew into a major field in the 20th century with linear programming and later interior-point methods. The Boyd and Vandenberghe textbook (2004) became the standard reference for turning real problems into convex form. This history is general background and is not taken from the opened sources.

Links on the roadmap

1.25 Jacobian and Hessian: the Hessian is the second-order convexity test.
1.26 Taylor approximation: the first-order condition is exactly the statement that the tangent (first-order Taylor) approximation underestimates a convex function; the second-order Taylor term gives the Hessian test.
1.28 and 1.29: sigmoid, softmax and log-sum-exp; log-sum-exp is convex.
1.30 Lagrange multipliers: convex problems have strong duality in typical cases and KKT conditions become sufficient.
1.32 Gradient descent convergence: step size and curvature (next).
Module 2 (2.05 loss functions), logistic regression and SVM: later uses of convex losses.

6. Worked examples with real numbers

Example A: checking convexity of f(x) = x² with the definition

Take x = −1, y = 3, θ = ½. The in-between point is ½(−1) + ½(3) = 1, so f(1) = 1. The chord height is ½·f(−1) + ½·f(3) = ½·1 + ½·9 = 5. Since 1 ≤ 5, the inequality holds here. The second-derivative test confirms it for all x: f''(x) = 2 ≥ 0. First-order check at x = 1 with slope 2: tangent at y = 3 gives 1 + 2·(3−1) = 5, and f(3) = 9 ≥ 5, so the tangent is below the curve.

Example B: a non-convex function, f(x) = x⁴ − 4x² + x

Setting the derivative 4x³ − 8x + 1 to zero gives three critical points (verified numerically):

x ≈ −1.473, f ≈ −5.444 (the global minimum),
x ≈ 0.126, f ≈ 0.063 (a local maximum),
x ≈ 1.347, f ≈ −2.619 (a local minimum, but not the global one).

Convexity fails. Take x = −1 and y = 1: f(−1) = 1 − 4 − 1 = −4 and f(1) = 1 − 4 + 1 = −2. The midpoint is 0, with f(0) = 0. The chord height is (−4 + −2)/2 = −3. Since 0 > −3, the convexity inequality is violated. Gradient descent (step 0.01, 2000 steps) started at x = 2 ends at 1.347 (value −2.619, the worse valley), while started at x = −2 it ends at −1.473 (value −5.444). Same function, different starting point, different answer: the egg tray.

Example C: a convex loss from data (mean squared error)

Data points (x, y) = (1, 3) and (2, 4), model y = w·x, loss L(w) = average of (w·x − y)². Then L(0) = (9 + 16)/2 = 12.5, L(2) = (1 + 0)/2 = 0.5, and L(4) = (1 + 16)/2 = 8.5. Check convexity with w = 0 and w = 4 and θ = ½: the midpoint is w = 2 with L = 0.5, while the chord height is (12.5 + 8.5)/2 = 10.5, and 0.5 ≤ 10.5. In fact L is a quadratic in w with a positive leading coefficient, so it is convex and w = 2 is the unique global minimum.

Example D: gradient descent on the bowl f(x) = x²

Start at x = 3 with step size 0.1. The gradient is 2x, so each step multiplies x by 0.8: 3 → 2.4 → 1.92 → 1.536 and so on toward 0. No matter where you start, it heads for the one valley.

Example E: a Hessian test in two variables

For f(x, y) = x² + xy + y², the Hessian is [[2, 1], [1, 2]] with eigenvalues 1 and 3, both positive, so f is convex (a bowl). For f(x, y) = x² − y², the Hessian is [[2, 0], [0, −2]] with eigenvalues 2 and −2; one is negative, so it is not convex: it is a saddle, like a horse saddle, bending up along x and down along y.

Example F: Jensen's inequality with eˣ

Take X equal to 0 or 2 with equal probability. The mean is 1, so f(E[X]) = e¹ ≈ 2.718. The average of f is (e⁰ + e²)/2 = (1 + 7.389)/2 ≈ 4.195. Indeed 2.718 ≤ 4.195, as Jensen predicts for a convex function.

7. Comparison tables

Convex versus non-convex (the bowl and the egg tray)

Property	Convex (bowl)	Non-convex (egg tray)
Number of valleys	One connected set of minimisers	Possibly many
Local minimum	Is a global minimum	May be worse than the global one
Zero gradient means	Global minimum	Minimum, maximum, or saddle
Starting point matters?	No (for the final value)	Yes
Typical examples	Least squares, logistic regression, SVM hinge	Deep neural networks, mixtures of experts
Guarantees	Strong convergence theory	Mostly empirical

Ways to test convexity

Test	Applies to	Condition	Good for
Definition (chord test)	Any function	Value at average at most average of values	Proofs, finding counterexamples
First-order	Differentiable functions	Tangent line below the graph	Showing zero gradient is optimal
Second-order, 1 variable	Twice differentiable	f'' at least 0	Quick check on curves
Second-order, many variables	Twice differentiable	Hessian PSD (eigenvalues at least 0)	Multi-parameter losses
Building blocks	Compound formulas	Combine convex pieces with allowed rules	Real models

Common convex building blocks

Function	Convex?	Note
x²	Yes	f'' = 2
abs(x)	Yes	Kink at 0, subgradients
eˣ	Yes	f'' = eˣ is positive
log-sum-exp	Yes	Smooth soft maximum, between max and max + ln n
Any norm ‖x‖	Yes	From the triangle inequality
max of convex functions	Yes	Hinge loss is a max of two lines
Nonnegative weighted sum	Yes	How regularised losses stay convex
Sigmoid σ(x)	No	Curves up then down (neither convex nor concave overall)
log(x)	No (it is concave)	Negative of it is convex
sin(x)	No	Alternates up and down

8. Common mistakes and myths

Myth: convex means "curves outward like a lens". In optimisation, a convex function curves upward like a bowl; the everyday geometry word is easy to flip. If you remember only one picture, remember the chord lying above the graph.
Mistake: using the definition with the inequality reversed. Reversed gives concave.
Mistake: thinking a convex function must have a minimum. eˣ and 2x do not.
Mistake: thinking the minimiser is always unique. Only strictly convex functions guarantee uniqueness; a flat-bottomed bowl has many minimisers (all equally good).
Mistake: assuming a sum of convex and non-convex pieces is convex. Only the convex ones can be combined freely; a negative multiple flips convexity.
Mistake: calling the sigmoid or a neural network convex. A network with nonlinear activations is generally non-convex in its weights, even if each loss term looks nice in the outputs.
Myth: non-convex means impossible to train. Deep networks train well in practice despite non-convexity; we just lack the clean guarantees.
Mistake: forgetting the domain. The function must be defined on a convex set for the definition to make sense.
Mistake: forgetting that zero gradient is only a global minimum for convex functions. For others it can be a maximum or a saddle.

9. Real-life and AI uses

Linear regression with squared error: a convex quadratic, so solving it gives the one best answer.
Logistic regression: its loss (negative log-likelihood) is convex in the weights, which is why it trains reliably (the loss uses log-sum-exp style terms; see 1.28 and 1.29).
Support vector machines: hinge loss plus a squared norm penalty is convex; the dual problem built with Lagrange multipliers is the one in MML sec. 12.3.
Regularisation: adding λ‖w‖² (ridge/weight decay) or λ·sum of abs(w) (lasso) to a convex loss keeps it convex; the squared-norm term even makes it strongly convex.
Constrained problems: a norm-ball constraint is a convex set, and projected gradient descent (Goodfellow sec. 4.4) works on it.
Deep learning: the loss surface is non-convex, but convex ideas still guide us: local quadratic approximations, learning-rate choices tied to curvature, and convex subproblems in layers (for example the last layer alone with fixed features is a convex problem).
Engineering and finance: portfolio optimisation, resource allocation and control problems are routinely formulated as convex programs (Boyd and Vandenberghe).

10. Self-check questions (with answers)

State the test for a convex set. For any two points in the set, the whole segment between them is in the set (θx + (1−θ)y for θ in [0, 1]).
Is a crescent convex? No; a line between the two tips passes through the hollow, outside the shape.
State the definition of a convex function. f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y): the graph lies on or below every chord.
For f(x) = x², x = −1, y = 3, θ = ½, compute both sides. Left side f(1) = 1; right side (1 + 9)/2 = 5; 1 ≤ 5 holds.
How do you test convexity using derivatives? One variable: f'' ≥ 0 everywhere. Many variables: Hessian is PSD (all eigenvalues ≥ 0) everywhere.
Why is a local minimum of a convex function global? If a better point existed, a small step toward it would give a lower value by convexity, contradicting local minimality.
Why does f(x) = x⁴ − 4x² + x fail convexity? Give a numeric check. At x = −1 and 1 the chord height is −3 but f(0) = 0, which is above it. It also has two valleys (values −5.444 and −2.619).
What is the Hessian's role, and what do mixed-sign eigenvalues mean? It gives curvature in all directions; mixed signs mean a saddle, not a bowl.
Name three ML losses that are convex and one model class that is not. Least squares, logistic loss, hinge loss; deep neural networks (non-convex in the weights).
Which operations preserve convexity? Nonnegative sums and scalings, the pointwise maximum, composition with an affine map; intersections preserve convexity of sets.
What does Jensen's inequality say? For convex f, f(E[X]) ≤ E[f(X)].

11. Key takeaways, go deeper, next

Key takeaways

Convex set: no dents. Convex function: chord above the graph, bowl-shaped.
For convex functions, any local minimum is a global minimum, and zero gradient means you have found it.
Quick tests: f'' ≥ 0, Hessian PSD, or assemble from convex blocks.
Least squares, logistic regression and SVM losses are convex; deep nets are not.
Convex problems also pair nicely with Lagrange duality (1.30).

Go deeper

Read the convexity chapter of d2l (sec. 12.2) and try the exercises on projection.
Read Boyd and Vandenberghe sec. 3.1 for the long list of convex examples and rules.
Plot f(x) = x⁴ − 4x² + x and run gradient descent from several starts, as in Example B.
Compute Hessian eigenvalues with numpy for a few two-variable functions.

Next on the roadmap: 1.32 Gradient descent convergence: step size and curvature.

12. Sources and further reading

Deisenroth, Faisal and Ong, Mathematics for Machine Learning (2020), https://mml-book.github.io/book/mml-book.pdf : sec. 7.3 "Convex Optimization" (Def. 7.2 convex set, Def. 7.3 convex function, epigraph, first- and second-order conditions); sec. 7.2 "Constrained Optimization and Lagrange Multipliers"; sec. 12.3 "Dual Support Vector Machine".
Zhang, Lipton, Li and Smola, Dive into Deep Learning, sec. 12.2 "Convexity", https://d2l.ai/chapter_optimization/convexity.html (convex sets and functions, Jensen's inequality, local minima are global minima, constraints, projections).
Boyd and Vandenberghe, Convex Optimization (2004), https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf : sec. 2.1 "Affine and convex sets"; sec. 3.1 "Basic properties and examples" (definition, first/second-order conditions, examples incl. log-sum-exp); sec. 4.2.2 "Local and global optima"; ch. 5 "Duality", sec. 5.1 "The Lagrange dual function".
Goodfellow, Bengio and Courville, Deep Learning (2016), https://www.deeplearningbook.org : ch. 4 "Numerical Computation", sec. 4.4 "Constrained Optimization" (feasible points, projected gradient descent, KKT approach).

Accuracy note: Definitions and conditions follow MML sec. 7.3, d2l sec. 12.2 and Boyd and Vandenberghe; numbers in the worked examples were checked in Python; the history paragraph is general background and not from the opened sources.

Convex sets and convex functions: study notes