Convex Optimization Basics
Convex sets & functions, first/second-order conditions, global vs. local optima.
On this page
Beginner: a convex function is "bowl-shaped" — pick any two points on its graph and draw a straight line segment connecting them; that segment always stays above (or exactly on) the graph, never dips below it. A convex set is the matching idea for regions instead of functions: a set is convex if, for any two points inside it, the entire straight line between them also lies inside the set. A disk or a filled rectangle is convex; a crescent moon or a star shape is not, because you can find two points inside them where the connecting line exits the shape.
Intermediate: here is why this matters far more than a piece of geometric trivia. For a convex function, any point where the gradient is exactly zero — or, for constrained problems, any point satisfying the KKT conditions covered in a later lesson — is automatically the global minimum, not merely a local one. That single fact quietly removes an entire category of worry: "did gradient descent get stuck in a local minimum" is a question that cannot even arise for a genuinely convex loss. There is no "stuck" to get stuck in — every valley is the same valley.
Advanced: this is not an accident of nature — most classical machine learning losses were deliberately chosen to be convex specifically so this guarantee holds. Squared error (ordinary least squares, ridge regression), logistic / cross-entropy loss, and hinge loss (SVMs, a later module) are all convex in their model parameters. Deep learning breaks this on purpose: the loss landscape of a multi-layer network is emphatically not convex — it is riddled with saddle points, plateaus, and many distinct local minima of different quality. That is exactly why later modules in this course need much more careful optimizer engineering — momentum, adaptive learning rates, learning-rate schedules — even though the basic "follow the negative gradient" idea is unchanged. Convexity is what classical ML gets almost for free; deep learning trades it away for expressive power and has to work much harder at optimization to compensate.
This is the defining inequality of a convex function: the function's value at any blend of two points x and y is never more than the same blend of the function's values at x and y — precisely "the chord lies above the curve." A set S is convex by the matching condition: λx + (1-λ)y stays in S for every x, y in S and every λ in [0,1].
For a differentiable f, this first-order condition is an equivalent characterization: the tangent line (plane, in higher dimensions) drawn at any point x always lies entirely below the function's graph everywhere else. A non-convex function always has some point and some direction where the tangent pokes up through the curve.
For a twice-differentiable f, this second-order condition is a third, equivalent characterization: the Hessian matrix of second derivatives must be positive semi-definite everywhere — in one dimension, that is just the familiar f''(x) ≥ 0, "curving upward or flat, never downward," at every single point.
Take f to be convex and differentiable, and suppose x* is a point where ∇f(x*) = 0. We want to show x* is not just a local minimum but the global minimum — smaller than or equal to f at absolutely every other point in the domain. Start from the first-order convexity condition, which holds for x* and any other point y:
Now substitute in what we know: ∇f(x*) = 0, so the entire second term on the right — the dot product of the zero vector with anything — is exactly zero:
That leaves f(y) ≥ f(x*). Crucially, y here was an arbitrary point — we never assumed y was close to x*, or restricted it to some neighborhood. The inequality holds for every y in the domain simultaneously, which is precisely the definition of a global minimizer. No other proof strategy for gradient-based optimization gets this for free: outside convexity, "gradient is zero" only tells you that you're at a stationary point — it could be a local min, a local max, or a saddle. Convexity is what upgrades "zero gradient" all the way to "global minimum," in three short lines of algebra.
Now, the second-order condition. The (truncated) second-order Taylor expansion of f around a point x, in the direction of another point y, is:
Compare this to the first-order convexity condition, which says f(y) ≥ f(x) + ∇f(x)ᵀ(y − x) for every x and y. Subtracting the shared linear terms f(x) + ∇f(x)ᵀ(y − x) from both the Taylor expansion and the convexity inequality forces the leftover quadratic piece to be non-negative for every choice of direction (y − x):
A matrix that produces a non-negative number when sandwiched this way against every possible vector is exactly what "positive semi-definite" means — so the first-order condition holding everywhere forces the Hessian to be PSD everywhere too. The converse — that a PSD Hessian everywhere implies the first-order (and hence the definition- level) condition — follows by integrating the Hessian condition twice along the line segment from x to y; we won't carry out that integral here, but it is a standard, fully rigorous result, and it is why all three characterizations (the chord inequality, the tangent-line inequality, and the PSD Hessian) are treated as interchangeable in practice.
Where this is used: this is exactly why textbooks are allowed to say "set the gradient to zero and solve" for ordinary least squares, ridge regression, and logistic regression, and then call the result the solution rather than a solution. The loss surfaces in all three cases are convex in the parameters, so the derivation above applies directly — any critical point found by solving ∇L(θ) = 0 is automatically the unique global minimum (or, when the Hessian is only PSD rather than strictly positive definite, one of a connected set of equally good global minima). That uniqueness is a load-bearing consequence of convexity, not a lucky coincidence of these particular problems.
Toggle between the convex bowl and the non-convex two-well curve. Watch the automatic demo roll a ball from several starting points, or drag the ball yourself and release it to watch it roll to wherever local gradient-following takes it.
All three snippets implement the same idea from two different angles. The first two build a convexity checker completely from scratch — no libraries beyond basic math — by directly sampling the definition's inequality across many random point pairs and blend ratios, and running it once on a genuinely convex function and once on a non-convex one. The third switches to a production-realistic angle: rather than testing the definition, it runs a real optimizer, scipy.optimize.minimize, from several different random starting points and prints what it finds — the same empirical point the diagram makes visually, now demonstrated with a real library-grade solver instead of a hand-rolled ball.
import random
def is_convex_numerically(f, domain=(-5.0, 5.0), n_pairs=2000, n_lambdas=9, seed=0):
"""Samples many random (x, y, lambda) triples and checks the convexity
inequality f(lambda*x + (1-lambda)*y) <= lambda*f(x) + (1-lambda)*f(y)
directly, with no calculus and no assumptions about f's shape."""
rng = random.Random(seed)
lo, hi = domain
violations = 0
checks = 0
for _ in range(n_pairs):
x = rng.uniform(lo, hi)
y = rng.uniform(lo, hi)
fx, fy = f(x), f(y)
for i in range(1, n_lambdas + 1):
lam = i / (n_lambdas + 1) # keep lambda strictly inside (0, 1)
lhs = f(lam * x + (1 - lam) * y)
rhs = lam * fx + (1 - lam) * fy
checks += 1
if lhs > rhs + 1e-9: # small tolerance for floating point noise
violations += 1
return violations, checks
def convex_bowl(x):
return x ** 2
def double_dip(x):
return x ** 4 - 3 * x ** 2
for name, fn in [
("f(x) = x^2 (convex)", convex_bowl),
("f(x) = x^4 - 3x^2 (not convex)", double_dip),
]:
violations, checks = is_convex_numerically(fn)
print(f"{name}: {violations} violations out of {checks} sampled (x, y, lambda) triples")- OLS, ridge, and logistic regression all have unique, reliably-found solutions precisely because their loss functions are convex in the parameters — "run the solver, get the answer" only works as a promise because there is exactly one basin (or one connected set of equally-good points) to find.
- Support vector machine training (a later module) is deliberately set up as a convex quadratic program specifically so that off-the-shelf solvers can certify global optimality — not just report a number, but guarantee no better answer exists anywhere in the feasible region.
- Deep neural network training is explicitly not this nice: the loss landscape of a multi-layer network is highly non-convex, full of saddle points and many local minima of varying quality. That is an accepted trade-off — the expressive power gained from stacking nonlinear layers is worth the loss of a global-optimality guarantee, but it is exactly why deep learning optimization is its own deep sub-field rather than "just gradient descent."
- K-means clustering (a later module) is famously not jointly convex in its cluster assignments and centroids together, and can converge to noticeably different final clusterings depending on how the centroids were initialized — the exact same "different starting point, different resting place" behavior the non-convex side of this lesson's diagram demonstrates, just in many dimensions instead of one.
- Lasso regression's L1 penalty is convex but not differentiable at zero — a reminder that convexity and smoothness are separate properties. The global-optimum guarantee from this lesson still applies to lasso, but the "set the gradient to zero" derivation above needs the coordinate and proximal methods covered later in this module, because there is no ordinary gradient at the kink.
- Convex relaxation is an entire sub-field built on this lesson's core idea: when the real problem you want to solve is non-convex and hard (e.g., variants of certain combinatorial or low-rank problems), replace it with a "nearby" convex problem that approximates it and genuinely can be solved exactly — trading a little bit of fidelity to the original problem for the entire toolbox of convex guarantees.
- Assuming a function is convex just because it looks smooth or bowl-shaped in the region you happened to plot. Convexity is a precise algebraic condition (the chord inequality, or an everywhere-PSD Hessian) — "looks fine where I checked" is not a proof, and plenty of functions look locally bowl-shaped while curving the wrong way somewhere else.
- Confusing "the loss function is convex in the parameters" with "this problem is easy." Convexity guarantees you will eventually reach the global optimum — it says nothing about how expensive each iteration is. A convex loss over a billion parameters is still enormously expensive per step; convexity buys you a destination guarantee, not a speed guarantee.
- Forgetting that convexity is a global property of the entire function over its whole domain, not something you can verify by inspecting one region. A function that is convex on the interval you tested can easily be non-convex somewhere else in its domain — the definition explicitly quantifies over every pair of points, not just the ones you looked at.
Going deeper
Convexity is preserved under several genuinely useful operations, and one in particular matters a great deal for later lessons: a non-negative weighted sum of convex functions is itself convex. This is exactly why "loss plus a regularization penalty" — the ridge and lasso objectives from later modules — stays convex whenever the base loss and the penalty term are each convex on their own: you don't have to re-derive convexity for every new regularized objective, you just check that each piece is convex and non-negatively weighted, and the sum inherits the property automatically.
There is also a stronger, quantified version of convexity worth knowing the name of now: strong convexity, which roughly requires the function to curve upward by at least some fixed minimum amount everywhere, not just "upward or flat." Plain convexity only promises that gradient descent will eventually converge to the global minimum — it says nothing about how fast. Strong convexity is what actually gives you a specific, provable convergence rate (typically geometric — the error shrinks by a fixed factor every iteration). The next lesson, 2.2.2 on gradient descent and its variants, uses exactly this property to state the convergence rates it proves.
You're told a loss function L(θ) is convex, and gradient descent converges to a point θ* where the gradient is (numerically) zero. A colleague worries this might just be one of several local minima. Are they right to worry, and why or why not?
No -- for a genuinely convex, differentiable loss, a zero-gradient point is not merely a local minimum, it is provably the global minimum, full stop. The derivation in this lesson shows why directly: the first-order convexity condition f(y) >= f(x*) + grad f(x*)^T (y - x*) holds for every y in the domain, and substituting grad f(x*) = 0 collapses it to f(y) >= f(x*) for every y -- there is no other point anywhere that beats x*. The colleague's worry would be justified for a non-convex loss (like a deep network's), where a zero gradient could indeed be one local minimum among several of differing quality -- but that concern simply does not transfer to a confirmed-convex objective.
Convexity is the single property that upgrades "gradient descent stopped moving" into "gradient descent found the best possible answer" — a zero gradient on a convex function is provably the global minimum, not one of several local ones, which is exactly why OLS, ridge, logistic regression, and SVM training can all promise a unique, reliably-found solution. Deep learning gives up this guarantee for expressive power, which is precisely why its optimizers need to be so much more carefully engineered — and it's exactly why every convergence-rate argument in the rest of this module starts by asking how convex, or how strongly convex, the objective in front of it actually is.