The curve of the average, and the average of the curve

Draw a curve that bends upwards, pick two points on it, and join them with a straight line. The line stays above the curve for the whole stretch between them. That is the whole of convexity, and almost everything else in this essay is that sentence applied somewhere it was not expected.

The picture is trivial. What is not trivial is how much of analysis turns out to be it in disguise.

Two readings of one inequality #

Written out, the chord condition says that for any two points $a$ and $b$ and any weight $t$ between 0 and 1,

$$f(ta + (1-t)b) \le t f(a) + (1-t)f(b).$$

The left side is the curve of the average: take the average of the two inputs, and see how high the curve is there. The right side is the average of the curve: take the heights at the two inputs, and average those. The inequality says the second is never smaller.

Both sides are averages and they average different things, which is why the two can differ at all. Averaging the inputs and then applying $f$ mixes before the bending happens; applying $f$ and then averaging lets the bending act on each point separately, and a curve that bends upwards is pushed higher by that.

The gap is not small. For the exponential across a modest interval the chord sits at nearly twice the curve, and it is the size of that gap that makes convexity useful rather than decorative: an inequality that is nearly an equality proves nothing anybody wanted.

Three points, then many #

Nothing about the argument needs two points. Take any finite collection of points on the curve and any positive weights adding to one, and form the weighted centroid of those points — a point of the plane, with both coordinates weighted averages.

The centroid of points on a convex curve lies on or above the curve. That is Jensen’s inequality, and it is the two-point statement applied repeatedly: the centroid of $n$ points is the centroid of the first two, re-weighted with the third, and so on down.

Written with a probability in it rather than a list of weights, Jensen’s inequality reads

$$f(\mathbb{E}[X]) \le \mathbb{E}[f(X)],$$

which is the form it is nearly always met in. The random variable’s average goes inside the function on the left and outside it on the right, and the inequality says the order matters and which way.

That is worth pausing on, because it is the source of a great many statements about how a random quantity behaves. How far from the average a thing can be turns Markov’s inequality into Chebyshev’s by applying it to $X^2$ instead of $X$, and squaring is convex; the step that looks like a trick is Jensen with the weights supplied by the distribution.

The direction reverses, and one function does it #

A curve bending downwards has every chord below it, and every inequality above flips. The logarithm is the standard example and the useful one.

Apply Jensen to $\ln$ with equal weights on $n$ positive numbers. The average of the logarithms is at most the logarithm of the average:

$$\frac{1}{n}\sum \ln x_i \;\le\; \ln\!\left(\frac{1}{n}\sum x_i\right).$$

Now exponentiate both sides. The left becomes the $n$-th root of the product; the right becomes the ordinary average. What has been proved is that the geometric mean is at most the arithmetic mean, for any list of positive numbers, with equality exactly when they are all equal.

The arithmetic–geometric mean inequality is usually met as a standalone fact with a clever proof, and there are several good ones — a rearrangement argument, an induction, a smoothing argument that moves two unequal values toward each other. Reading it off the logarithm’s concavity costs nothing extra once Jensen is available, and it explains the equality case for free: equality in Jensen means all the points coincide, which here means all the values are equal.

The tangent, which is the same fact upside down #

There is a second characterisation of convexity that is often easier to use than the chord one: a convex curve lies above every one of its tangent lines.

The two are equivalent, and the equivalence is worth seeing. A chord above the curve everywhere between its ends means the curve’s slope is increasing; an increasing slope means a tangent taken at any point undershoots the curve on both sides. Neither statement mentions the second derivative, which is a convenience rather than a definition — a convex function need not be twice differentiable, or differentiable at all. A curve with a corner at every point is not convex, but $|x|$ is, and it has no derivative at zero.

The tangent version gives a one-line proof of Jensen. Let $m$ be the weighted average of the inputs and take the supporting line at $m$ — the line through $(m, f(m))$ with the curve above it. Then $f(x_i) \ge f(m) + s(x_i - m)$ for every $i$, where $s$ is the line’s slope. Multiply the $i$-th inequality by its weight and add. The weights sum to one, so the constant terms give $f(m)$; the weighted sum of $x_i - m$ is zero by the definition of $m$, so the slope term vanishes entirely. What is left is $\sum w_i f(x_i) \ge f(m)$, which is Jensen.

The step where the slope term vanishes is the whole proof, and it is the reason the supporting line has to be taken at the average rather than anywhere else. The flat map that fits closest is about the tangent as the best local linear approximation; here the tangent is being used for something different — as a global lower bound, which is a property no non-convex function’s tangent has.

The second derivative, which is a test and not a definition #

The usual working rule is that a twice-differentiable function is convex exactly when its second derivative is non-negative, and that is true and useful and the wrong place to start.

It is the wrong place because the definition it replaces is about any function, and a great many convex functions of interest are not twice differentiable. The absolute value is convex; the maximum of two convex functions is convex, and a maximum has corners; a piecewise-linear function with increasing slopes is convex, and every economic cost curve anybody actually writes down is of that kind. A definition that excluded these would have to be repaired immediately.

The second-derivative test also hides what the condition is doing. Non-negative second derivative means the slope is non-decreasing, and a non-decreasing slope is precisely the statement that a chord’s slope is between the slopes at its ends — which is the chord condition, rearranged. So the test is not a separate criterion; it is the definition, expressed in the language of a function that may not exist.

Convex sets, and the other half of the word #

The word is used for two things, and they are related in a way worth stating once.

A set is convex when it contains the whole segment between any two of its points. A function is convex when the region above its graph — its epigraph — is a convex set. The two definitions are one definition, and the second is where the picture at the top of this essay comes from: the chord lies above the curve exactly when the region above the curve contains the chord.

That is more than a restatement, because sets and functions then trade theorems. The fact that a maximum of convex functions is convex becomes the fact that an intersection of convex sets is convex — the epigraph of a maximum is the intersection of the epigraphs. The supporting-line argument above becomes the supporting-hyperplane theorem, which says a convex set has a hyperplane through each boundary point with the whole set on one side.

And the centroid picture in the Jensen figure is the set statement outright: the shaded polygon spanned by four points on the curve is inside the epigraph because the epigraph is convex, so it never dips below the curve, and the centroid is inside the polygon. The most area a fence can hold leans on the set version at a key step — replacing a region by its convex hull never decreases the area and never increases the perimeter — which is a fact about sets doing work in a problem about curves.

Where it fails, and how the failure looks #

Convexity is a property of an interval, not of a point, and a function can bend upwards near each end of an interval and downwards in the middle.

The failure is not subtle once the right pair is found, and finding it is a search rather than an inspection. The two ends of the offending chord sit near the two minima, and the curve rises between them — so the average of the two heights is below the height at the average, which is exactly Jensen reversed.

That is why “locally convex” is not a useful notion for these purposes. A function convex on each of two intervals is convex on neither’s union, and the inequality is about the whole domain over which the average is taken.

What convexity is really doing #

Three inequalities that look unrelated are the same inequality with different functions substituted.

The arithmetic–geometric mean inequality is Jensen for $\ln$, as above.

Cauchy–Schwarz follows from Jensen applied to $x^2$ with weights proportional to one of the two vectors’ entries — or, more transparently, from the observation that a quadratic in $t$ with no real root has a non-positive discriminant, which is convexity again in the form “a parabola opening upwards that never crosses zero has a vertex above zero”.

The bound on entropy — that a distribution on $n$ outcomes has entropy at most $\ln n$ — is Jensen for $\ln$ applied to the reciprocals of the probabilities.

A fourth, less often noticed: the power mean inequality, which says that averaging $p$-th powers and then taking the $p$-th root gives a bigger answer for bigger $p$. It is Jensen applied to $x^{q/p}$, which is convex exactly when $q \ge p$, and it contains the arithmetic–geometric mean inequality as the limiting case at $p \to 0$. Every square is a stack of odd numbers is a rearrangement proof of a different kind and the contrast is instructive: rearrangement proofs are exact and specific, and convexity proofs are inexact and general.

Each of these is proved somewhere without mentioning convexity, and each proof is shorter than the general argument. What the general argument buys is that the three stop being separate facts. A collection of inequalities that all come from one picture is a smaller thing to remember than three clever arguments, and it also predicts new members: any convex function produces an inequality of this shape, whether or not anybody has named it.

The cost, and the shape of what it proves #

Convexity gives inequalities and never equalities, and the inequalities it gives are one-sided by construction. Knowing that $\mathbb{E}[f(X)] \ge f(\mathbb{E}[X])$ says nothing about how much bigger, and the gap can be anything from zero — when $X$ is constant, or $f$ is linear — to unbounded.

The gap has a name, the Jensen gap, and controlling it is a genuinely harder problem than proving the inequality. For the exponential the gap over an interval of width $w$ grows like $e^w$; for the square it is exactly the variance, which is a rare case where the gap is a familiar quantity.

That last case is worth stating on its own, because it is the most-used instance of the whole subject: for $f(x) = x^2$, Jensen’s gap is $\mathbb{E}[X^2] - (\mathbb{E}[X])^2$, which is the variance. So the variance is not merely non-negative by algebra; it is non-negative because squaring is convex, and the two facts are the same fact.

Where it came from #

Jensen published the inequality in 1906, working from the definition via midpoints — a function satisfying the chord inequality at $t = 1/2$ only, which for a continuous function turns out to be enough to give it for every $t$. That the midpoint condition implies the general one is a genuinely non-obvious step and it needs continuity: without it there exist wildly discontinuous functions satisfying the midpoint inequality and nothing else.

Convexity as a subject in its own right is later, and it was pushed by optimisation rather than analysis: a convex function on a convex set has the property that a local minimum is a global one, which turns a search problem into a solvable one. That property is not proved here and belongs to a different ladder, but it is why the word appears far more often in the twentieth century than in the nineteenth.

What the pictures cannot show #

Every curve drawn here is smooth, and convexity does not require smoothness. The chord condition makes sense for any function, and the class of convex functions includes things with corners — where a whole interval of supporting lines exists at a point rather than one tangent. The figures cannot show that, because a corner drawn at the resolution of a page looks like a tight bend.

The Jensen figure draws a weighted centroid of four points, and four is not many. The inequality holds for any number of points and, in the limit, for a probability distribution with no points at all in the ordinary sense — a continuous density. Nothing in the drawing indicates that the finite case is a special case rather than the whole of it.

And the search that finds the bad chord searched a grid. It found a dip of 3.02, which is a genuine dip; it did not find the worst possible dip, only the worst on the pairs tried. The claim asserted is the one the search can support — that this function is not convex — and not the size of its worst violation.

The ladder from here #

Below: the flat map that fits closest, where the tangent line is introduced as an approximation rather than as a bound, and the curve that is its own slope, which supplies the exponential and its inverse. Sideways: how far from the average a thing can be, where Jensen supplies the step from Markov to Chebyshev, and the most area a fence can hold, an extremal problem whose solution is forced by a convexity argument of a different kind. Above: convex sets and supporting hyperplanes, duality, and the reason a convex optimisation problem has no local traps.

What is worth carrying away #

A weighted average is a point on a segment, and applying a function to it is not the same as applying the function to the ends and averaging. Which of the two is larger is decided by which way the curve bends, and by nothing else.

That is a very small observation, and its reach is out of all proportion to its size. It converts a statement about a shape — the chord stays above — into statements about numbers that were proved separately for a century before anybody noticed they were one statement. Averaging and applying a function do not commute, and convexity is the name for knowing which way round they fail to.