Convex Sets, Convex Functions & Jensen's Inequality
“Epigraphs, first/second-order convexity conditions, Hessian PSD H >= 0, and Jensen's inequality f(E[X]) <= E[f(X)].”
1.The Foundations of Convex Analysis in Machine Learning
§ 3.1.Convex optimization represents the fundamental boundary between computationally tractable and intractable problems.
Convex Sets:
A set C is convex if the line segment connecting any two points in C lies entirely within C.
Convex Functions:
A function f is convex if its Epigraph epi(f) = { (x, t) : t >= f(x) } is a convex set.
The Three Equivalent Characterizations of Convexity:
1. Zeroth-Order: f(theta x + (1 - theta) y) <= theta f(x) + (1 - theta) f(y) for all theta in [0, 1].
2. First-Order: The tangent hyperplane at any point lies entirely below the function graph: f(y) >= f(x) + grad(f(x))^T (y - x).
3. Second-Order: The Hessian matrix is Positive Semi-Definite (H(x) >= 0) everywhere on its convex domain.
Jensen's Inequality:
For convex f, f(E[X]) <= E[f(X)]. In statistics, this establishes that the arithmetic mean exceeds the geometric mean (AM >= GM), and forms the core of the EM algorithm and Variational Inference.
2. Worked Practice Problem: Proving Convexity via Hessian Matrix
To prove convexity everywhere, verify that all leading principal minors are non-negative for ALL values of (x, y).
Problem: Prove that the function f(x, y) = exp(x - y) + x^2 + 2*y^2 is strictly convex everywhere on R^2.
Step 1: Compute first partial derivatives:
df/dx = exp(x - y) + 2*x
df/dy = -exp(x - y) + 4*y
Step 2: Compute second partial derivatives (Hessian entries):
f_xx = d/dx [exp(x - y) + 2*x] = exp(x - y) + 2.
f_yy = d/dy [-exp(x - y) + 4*y] = exp(x - y) + 4.
f_xy = d/dy [exp(x - y) + 2*x] = -exp(x - y).
Let a = exp(x - y) > 0 for all (x, y) in R^2.
Hessian H = [ [a + 2, -a], [-a, a + 4] ].
Step 3: Test Positive Definiteness via Sylvester's Criterion:
Leading principal minor 1: D1 = f_xx = a + 2.
Since a = exp(x - y) > 0, D1 > 2 > 0 for all (x, y).
Leading principal minor 2: D2 = det(H) = (a + 2)*(a + 4) - (-a)^2.
D2 = (a^2 + 6a + 8) - a^2 = 6a + 8.
Since a > 0, D2 > 8 > 0 for all (x, y).
Step 4: Conclusion on Definiteness:
Both leading principal minors (D1 > 0, D2 > 0) are strictly positive everywhere on R^2.
Thus, the Hessian matrix H is strictly Positive Definite everywhere on R^2.
Conclusion: f(x, y) is strictly convex everywhere on R^2, guaranteeing a unique global minimum.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.