Definition
Convex function A function is convex if the chord between any two points of its graph never lies below the graph: for all and all . Its graph is a bowl with no bumps, so there is nowhere for a descent method to get stuck except the bottom.
At a glance
- Notation
- mixes the endpoints ; means the Hessian is positive semidefinite
- Tests
- chord inequality; tangent below graph; (1-D) or everywhere
- Key property
- every local minimum is global, and is sufficient for a global minimum
- Strict / strong
- strict: at most one minimizer; -strong (): exactly one, and GD converges linearly
- Prerequisites
- derivatives & gradients, Taylor approximation
- Used in
- linear & logistic regression, SVMs, lasso, convex relaxations, convergence guarantees
The intuition
Stretch a string between two points on the graph. For a convex function the string always hangs on or above the curve — the curve sags below every chord. A bump would poke through the string; a bump is also exactly what creates a second, worse valley where a downhill walker can stop.
That is why convexity matters in practice: on a convex loss, gradient descent started anywhere ends in the same valley, and "the gradient is zero" certifies that you are done. On a non-convex loss the answer depends on where you start.
The math
- any two points in the domain (the chord's endpoints)
- mixing weight: gives , gives
- height of the chord above that point
Differentiable tests. If is differentiable, convexity is equivalent to every tangent plane lying below the graph; if it is twice differentiable, to non-negative curvature in every direction:
- gradient of at
- Hessian (matrix of second derivatives); means all its eigenvalues are
The tangent condition gives the payoff at once: if , then for every — a stationary point is a global minimum.
Local implies global. Suppose is a local minimum but some has . Points approach as , and the chord inequality gives . So arbitrarily close to there are lower points — contradicting local minimality.
Building convex functions. Non-negative weighted sums, composition with an affine map , and pointwise maxima all preserve convexity. That is how you certify losses without computing a Hessian: (a norm of an affine map), hinge loss , the log-loss and log-sum-exp are all convex in , and adding an L1 or L2 penalty keeps them so.
See it
Worked example
Convex. , , , : the midpoint is with , the chord there is , and . In general , so the inequality holds for every chord.
Non-convex. has for . Its stationary points () are with (global minimum), (local maximum, ) and with (a local minimum that is not global). The chord test fails between the two minima: at the midpoint , but the chord is at — the graph is 2.19 above it.
In code
1import numpy as np2from scipy.optimize import minimize34f = lambda x: x[0]**4 - 3 * x[0]**2 + x[0]5for x0 in [-1.76, -0.88, 0.0, 0.88, 1.76]:6 res = minimize(f, [x0])7 print(x0, res.x.round(3), round(res.fun, 3)) # -1.301 (f=-3.514) or 1.131 (f=-1.07)89# Logistic regression: Hessian of the mean log-loss is X^T S X / n, S = diag(p(1-p))10rng = np.random.default_rng(0)11X, w = rng.normal(size=(200, 3)), rng.normal(size=3)12p = 1 / (1 + np.exp(-X @ w))13H = X.T @ (X * (p * (1 - p))[:, None]) / len(X)14print(np.linalg.eigvalsh(H).min() >= 0) # True at every w: convexWhere it's used
Linear & logistic regression
Squared error and log-loss are convex in the weights, so any solver — closed form, L-BFGS, SGD — reaches the same optimum, and its gradient norm is a valid stopping test.
SVMs and the lasso
Hinge loss plus an L2 penalty, and squared error plus an L1 penalty, are convex but non-smooth; subgradient, coordinate-descent and proximal methods still find the global optimum.
Convex relaxations
Hard problems are replaced by convex surrogates: the L1 norm for the count of non-zeros (sparse recovery), the nuclear norm for rank (matrix completion), hinge for 0–1 loss.
Reading deep-learning theory
Neural-network losses are non-convex, so guarantees are local. Convex results (step size , linear rates under strong convexity) are the baseline that optimizer analyses and learning-rate heuristics start from.
Check yourself
Which function is not convex on all of ?
Check yourself
is convex and differentiable, and . Then is…
Remember
- ✓Convex: every chord lies on or above the graph — .
- ✓Equivalent tests: tangents below the graph; everywhere.
- ✓Local minima are global, and certifies optimality.
- ✓Sums, affine compositions and maxima of convex functions are convex — that is how ML losses are certified.