Lecture 24 · A quick detour for GMMs

Convex Functions and Jensen's Inequality

The GMM log-likelihood got stuck on a log of a sum. The tool that gets around it is Jensen's inequality: for a concave function like log, it lets you swap the log of a sum for a sum of logs, giving up equality in exchange for an inequality. This lecture covers only the convexity facts needed for that.

Source: this lecture on YouTube (≈15 min). Previous: L23 · GMM likelihood.

1 · Convex and concave: the chord test

Pick two points $a$ and $b$, and draw the straight line (the chord) between $(a,f(a))$ and $(b,f(b))$. Then compare the curve with the chord at the midpoint:

The curve's height at the midpoint is $f\!\big(\frac{a+b}{2}\big)$.
The chord's height there is halfway between $f(a)$ and $f(b)$: $\frac{f(a)+f(b)}{2}$.

Convex

Curve below the chord, for every $a,b$:
$f\!\big(\tfrac{a+b}2\big)\le\tfrac{f(a)+f(b)}2$. A bowl, like $x^2$.

Concave

Curve above the chord, for every $a,b$:
$f\!\big(\tfrac{a+b}2\big)\ge\tfrac{f(a)+f(b)}2$. A dome, like $\log x$.

Both

Equality always, so the curve is the chord: a linear function.

Neither

Below the chord for some pairs, above it for others: a wiggly curve.

Like convex and concave mirrors: a convex function curves up like a bowl, a concave one curves down like a dome.

2 · Any point on the chord, not just the midpoint

Write the midpoint as $\tfrac12a+\tfrac12b$. If the midpoint test holds for every $a, b$, it also holds for any weighting $\lambda\in[0,1]$:

$$\text{convex:}\quad f\big(\lambda a+(1-\lambda)b\big)\;\le\;\lambda f(a)+(1-\lambda)f(b).$$

As λ goes from 1 to 0, the point $\lambda a+(1-\lambda)b$ slides from $a$ to $b$, and the curve stays below the chord the whole way. For concave, flip the inequality. Try it:

a = b = λ =

–

curve: f(λa + (1−λ)b)

–

chord: λf(a) + (1−λ)f(b)

–

at this point

functionchord

3 · Many points: Jensen's inequality

The same holds for any number of points $a_1,\dots,a_K$ with weights $\lambda_k\ge0$ that sum to 1. For a concave function:

$$\boxed{\;f\Big(\sum_{k=1}^{K}\lambda_k a_k\Big)\;\ge\;\sum_{k=1}^{K}\lambda_k f(a_k)\;}$$

(For a convex function, the inequality flips.) The weighted average $\sum_k\lambda_k a_k$ lies somewhere among the points: in 2-D, inside the triangle or polygon they form, which is called their convex hull. A concave function, evaluated there, sits above the flat surface that joins the function values at the points.

In words, for concave f: f of the average is at least the average of the f values.

4 · Why this matters: log is concave

The logarithm is concave (the lecture leaves the proof as an exercise; there's a hint below). So Jensen gives

$$\log\Big(\sum_{k}\lambda_k a_k\Big)\;\ge\;\sum_{k}\lambda_k\log a_k .$$

On the left, a sum inside a log: exactly the shape that blocked the GMM log-likelihood in L23. On the right, the sum is outside the log, and each $\log a_k$ can simplify (a log of a Gaussian density is just a quadratic). The price is that we get "≥" instead of "=". The next lectures show how to work with that inequality to fit a GMM.

Check it with numbers

Three positive numbers with weights λ₁ = 0.2, λ₂ = 0.5, λ₃ = 0.3. Move them and the left side never drops below the right.

a₁ = a₂ = a₃ =

–

log(Σ λₖaₖ): log of the average

–

Σ λₖ log aₖ: average of the logs

–

gap (always ≥ 0)

Make all three equal and the gap becomes 0: equality holds exactly when there's nothing to average.

Exercise from the lecture: why is log concave?

One quick route uses the second derivative: $\frac{d}{dx}\log x=\frac1x$ and $\frac{d^2}{dx^2}\log x=-\frac1{x^2}<0$ for every $x>0$. A function whose slope keeps decreasing bends downward everywhere, so it's concave. (A negative second derivative everywhere is a standard sufficient test; the lecture's chord definition is the underlying idea.)

Key takeaways

Convex: the curve lies below every chord. Concave: above. Linear: both. Some functions are neither.
The chord test works at any weight λ ∈ [0, 1], not just the midpoint.
Jensen (concave f): $f(\sum\lambda_k a_k)\ge\sum\lambda_k f(a_k)$, with λ ≥ 0 and Σλ = 1.
log is concave, so Jensen turns log(sum) into a sum of logs, at the cost of an inequality. That's the way past the GMM bottleneck.

Self-check: is f(x) = −x² convex, concave, both, or neither?

Concave. It's an upside-down bowl, so every chord lies below the curve.

Self-check: when does Jensen's inequality become an equality for log?

When all the aₖ (with non-zero weight) are equal, or when f is linear. Then the average of the logs equals the log of the average.