Convexity

For a convex function, every local minimum is a global minimum.

5 min read519 wordscore3 viewsupdated 2026-10-03

Definition

Convex function A function f:Rn→Rf:\mathbb{R}^n\to\mathbb{R} is convex if the chord between any two points of its graph never lies below the graph: f(θa+(1−θ)b)≤θf(a)+(1−θ)f(b)f(\theta a+(1-\theta)b)\le\theta f(a)+(1-\theta)f(b) for all a,ba,b and all θ∈[0,1]\theta\in[0,1]. 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
θ∈[0,1]\theta\in[0,1] mixes the endpoints a,ba,b; ∇2f⪰0\nabla^2 f\succeq 0 means the Hessian is positive semidefinite
Tests
chord inequality; tangent below graph; f′′≥0f''\ge0 (1-D) or ∇2f⪰0\nabla^2f\succeq0 everywhere
Key property
every local minimum is global, and ∇f(x∗)=0\nabla f(x^*)=0 is sufficient for a global minimum
Strict / strong
strict: at most one minimizer; μ\mu-strong (∇2f⪰μI\nabla^2f\succeq\mu I): 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

f(θa+(1−θ)b) ≤ θf(a)+(1−θ)f(b)∀ a,b∈Rn, θ∈[0,1]f\big(\theta a+(1-\theta)b\big)\ \le\ \theta f(a)+(1-\theta)f(b)\qquad \forall\, a,b\in\mathbb{R}^n,\ \theta\in[0,1]
a,ba,b
any two points in the domain (the chord's endpoints)
θ\theta
mixing weight: θ=1\theta=1 gives aa, θ=0\theta=0 gives bb
θf(a)+(1−θ)f(b)\theta f(a)+(1-\theta)f(b)
height of the chord above that point

Differentiable tests. If ff 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:

f(y) ≥ f(x)+∇f(x)⊤(y−x)⟺∇2f(x)⪰0  ∀xf(y)\ \ge\ f(x)+\nabla f(x)^{\top}(y-x)\qquad\Longleftrightarrow\qquad \nabla^2 f(x)\succeq 0\ \ \forall x
∇f(x)\nabla f(x)
gradient of ff at xx
∇2f(x)\nabla^2 f(x)
Hessian (matrix of second derivatives); ⪰0\succeq0 means all its eigenvalues are ≥0\ge0

The tangent condition gives the payoff at once: if ∇f(x∗)=0\nabla f(x^*)=0, then f(y)≥f(x∗)f(y)\ge f(x^*) for every yy — a stationary point is a global minimum.

Local implies global. Suppose x∗x^* is a local minimum but some yy has f(y)<f(x∗)f(y)<f(x^*). Points zθ=θy+(1−θ)x∗z_\theta=\theta y+(1-\theta)x^* approach x∗x^* as θ→0\theta\to0, and the chord inequality gives f(zθ)≤θf(y)+(1−θ)f(x∗)<f(x∗)f(z_\theta)\le\theta f(y)+(1-\theta)f(x^*)<f(x^*). So arbitrarily close to x∗x^* there are lower points — contradicting local minimality.

Building convex functions. Non-negative weighted sums, composition with an affine map x↦Ax+bx\mapsto Ax+b, and pointwise maxima all preserve convexity. That is how you certify losses without computing a Hessian: ∥Xw−y∥2\|Xw-y\|^2 (a norm of an affine map), hinge loss max⁡(0,1−y w⊤x)\max(0,1-y\,w^\top x), the log-loss log⁡(1+e−y w⊤x)\log(1+e^{-y\,w^\top x}) and log-sum-exp are all convex in ww, and adding an L1 or L2 penalty keeps them so.

See it

ab
chord [-1.28, 1.28]: graph rises 2.231 above it ✗f = x⁴ − 3x² + x · non-convexdrag a and b — the rose stretch is where the graph goes above the chord
gradient descent from the 5 violet starts · fixed η = 0.02
fig.Drag a and b: rose marks where the graph rises above the chord. For x⁴ − 3x² + x with the chord on [−1.28, 1.28] the graph pokes 2.23 above it. Run gradient descent: from five starts it lands at x = −1.30 three times and x = 1.13 twice — two different minima (0.15x² + sin 2x gives three). Switch to x², |x|, eˣ − x or log-sum-exp and every start reaches the same point.

Worked example

Convex. f(x)=x2f(x)=x^2, a=−1a=-1, b=3b=3, θ=12\theta=\tfrac12: the midpoint is x=1x=1 with f(1)=1f(1)=1, the chord there is 12(1+9)=5\tfrac12(1+9)=5, and 1≤51\le5. In general f′′(x)=2>0f''(x)=2>0, so the inequality holds for every chord.

Non-convex. f(x)=x4−3x2+xf(x)=x^4-3x^2+x has f′′(x)=12x2−6<0f''(x)=12x^2-6<0 for ∣x∣<0.707|x|<0.707. Its stationary points (4x3−6x+1=04x^3-6x+1=0) are x=−1.301x=-1.301 with f=−3.514f=-3.514 (global minimum), x=0.170x=0.170 (local maximum, f′′=−5.65f''=-5.65) and x=1.131x=1.131 with f=−1.070f=-1.070 (a local minimum that is not global). The chord test fails between the two minima: at the midpoint x=−0.085x=-0.085, f=−0.107f=-0.107 but the chord is at 12(−3.514−1.070)=−2.292\tfrac12(-3.514-1.070)=-2.292 — the graph is 2.19 above it.

In code

python
1import numpy as np
2from scipy.optimize import minimize
3
4f = 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)
8
9# 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: convex
A local optimizer finds whichever minimum is downhill of its start. The logistic-loss Hessian XᵀSX/n has non-negative eigenvalues for any data, which is the convexity certificate.

Where 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 η<2/L\eta<2/L, 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 R\mathbb{R}?

Check yourself

ff is convex and differentiable, and ∇f(x0)=0\nabla f(x_0)=0. Then x0x_0 is…

Remember

  • ✓Convex: every chord lies on or above the graph — f(θa+(1−θ)b)≤θf(a)+(1−θ)f(b)f(\theta a+(1-\theta)b)\le\theta f(a)+(1-\theta)f(b).
  • ✓Equivalent tests: tangents below the graph; ∇2f⪰0\nabla^2f\succeq0 everywhere.
  • ✓Local minima are global, and ∇f=0\nabla f=0 certifies optimality.
  • ✓Sums, affine compositions and maxima of convex functions are convex — that is how ML losses are certified.
← back to Mathematics roadmap