Week 2: Convex Sets and Functions

Fit a logistic regression twice from two random starts and you reach the same loss. Fit a small network twice and you get two models with two different losses. Both runs use gradient descent. The difference is the shape of the loss, and one inequality separates the two shapes. Each surface below has an amber chord from $(y, f(y))$ to $(x, f(x))$, above the same two points $x = (1, 0.5)$ and $y = (-1, -0.5)$.

Slide $\theta$ to move the point $\theta x + (1-\theta)y$ from $y$ to $x$. The short segment joins it to the surface, and the caption prints both heights. On the convex surface the chord stays above the graph at every $\theta$. Switch to the double well, and at $\theta = 0.5$ the chord runs 2.5 under the hump.

The chord test#

A function $f: \mathbb{R}^d \to \mathbb{R}$ is convex if its domain is convex and, for all $x, y$ and $\theta \in [0, 1]$,

$f(\theta x + (1-\theta) y) \leq \theta f(x) + (1-\theta) f(y)$

This is Jensen's inequality, the test you ran in the scene. The left side is the surface under the marked point. The right side is the chord. On the convex surface $f(x) = f(y) = 4.5$, so the chord is flat at 4.5, and at $\theta = 0.5$ the surface is at 0. The double well is $f(u, v) = (u^2 - 2)^2 + 2v^2 + u/2$, with $f(x) = 2$ and $f(y) = 1$. At $\theta = 0.5$ the chord is at 1.5 and the surface at 4, so the inequality fails by 2.5.

Why the quadratic passes: PSD#

The convex surface is $f(x) = x^T Q x$ with $Q = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}$. For any quadratic, expand both sides of Jensen with $d = x - y$:

$\theta f(x) + (1-\theta) f(y) - f(\theta x + (1-\theta)y) = \theta(1-\theta)\, d^T Q d$

In the scene $d = (2, 1)$ and $d^T Q d = 18$, so the gap is $18\,\theta(1-\theta)$, which is 4.5 at $\theta = 0.5$. The gap is nonnegative for every pair exactly when $d^T Q d \geq 0$ for every $d$. That is positive semidefinite (PSDPositive Semidefinite): $x^T Q x$ is convex if and only if the symmetric $Q$ has no negative eigenvalue. Here $\det(Q - \lambda I) = \lambda^2 - 5\lambda + 5$ gives eigenvalues $\frac{5 \pm \sqrt{5}}{2} \approx 3.618$ and $1.382$, both positive.

A twice-differentiable $f$ is convex exactly when its Hessian $\nabla^2 f(x)$ is PSD at every $x$. In one dimension that is $f'' \geq 0$, so $e^x$ and $-\log x$ pass. The double well has Hessian $\mathrm{diag}(-8, 4)$ at the origin. Along the chord's direction, $d^T \nabla^2 f(0)\, d = 4(-8) + 4 = -28$. The surface curves down under the chord.

The common mistake. Each well of the double well is a bowl, and its Hessian is positive definite at both minima. That does not make $f$ convex. Convexity is a claim about every chord, not about the minima, and the chord across the hump breaks it.

First-order condition: the tangent plane#

For differentiable $f$, convexity is equivalent to the first-order condition: the function lies above every tangent plane.

$f(y) \geq f(x) + \nabla f(x)^T (y - x) \quad \text{for all } x, y$

On the convex surface $\nabla f(x) = 2Qx = (7, 4)$, so the tangent plane at $x$ predicts $4.5 - 18 = -13.5$ at $y$. The surface is at 4.5, above it by $d^T Q d = 18$. On the double well $\nabla f(x) = (-3.5, 2)$, so the tangent predicts $2 + 7 - 2 = 7$ at $y$, but $f(y) = 1$. The tangent passes over the surface by 6. Week 3 adds a quadratic floor, strong convexity.

Convex sets#

A set $C$ is convex if $\theta x + (1-\theta)y \in C$ for all $x, y \in C$ and $\theta \in [0, 1]$. Halfspaces, balls and the probability simplex are convex. A donut is not. Intersections of convex sets are convex, so linear constraints always cut out a convex feasible region.

Building convex functions#

These operations preserve convexity:

• Nonnegative weighted sums $\sum_i w_i f_i$ with $w_i \geq 0$.
• Pointwise maxima $\max_i f_i(x)$, which is why hinge loss is convex.
• Affine composition $f(Ax + b)$.
• Norms: the triangle inequality and $\|\theta x\| = |\theta|\,\|x\|$ give $\|\theta x + (1-\theta)y\| \leq \theta\|x\| + (1-\theta)\|y\|$, so $\|x\|_1$ and $\|x\|_2$ are convex penalties (Week 10).

Nonlinear composition need not: $|t - 1|$ and $x^2$ are convex, but $|x^2 - 1|$ is not.

Local equals global#

Theorem: For a convex $f$, every local minimum is a global minimum.

Proof sketch: Suppose $x^*$ is a local minimum and some $y$ has $f(y) < f(x^*)$. By convexity, for every $\theta \in (0, 1]$,

$f((1-\theta)x^* + \theta y) \leq (1-\theta)f(x^*) + \theta f(y) < f(x^*)$

Small $\theta$ gives points arbitrarily close to $x^*$ with lower loss, which contradicts local minimality. $\square$

The double well shows what nonconvexity costs. Its global minimum is at $(-1.44, 0)$ with $f = -0.71$, and its other minimum at $(1.38, 0)$ has $f = 0.70$. The gradient at $x = (1, 0.5)$ is $(-3.5, 2)$, so small-step gradient descent from $x$ settles in the worse well. Least squares and logistic regression have no such trap. Week 13 returns to the nonconvex case.

Knowledge Check#

Browser lab: tangents and the first-order condition#

Plot three convex functions and one nonconvex function on the same axes, and verify the first-order condition: the tangent line at any point always lies below a convex function's graph.

import numpy as np
import matplotlib.pyplot as plt

def f1(x): return x**2
def f2(x): return np.exp(x)
def f3(x): return -np.log(x)   # domain: x > 0
def f4(x): return x**3 - 3*x

fig, axes = plt.subplots(2, 2, figsize=(10, 8))
axes = axes.flat

for ax, fn, name, grad_fn, xr, x0 in [
    (axes[0], f1, "$x^2$", lambda x: 2*x, (-2.0, 4.0), 2.0),
    (axes[1], f2, "$e^x$", lambda x: np.exp(x), (-2.0, 4.0), 2.0),
    (axes[2], f3, "$-\\log x$", lambda x: -1/x, (0.05, 4.0), 2.0),
    (axes[3], f4, "$x^3-3x$", lambda x: 3*x**2 - 3, (-2.0, 4.0), -1.0),
]:
    xs = np.linspace(*xr, 300)
    ys = fn(xs)
    ax.plot(xs, ys, label=name)
    tangent = fn(x0) + grad_fn(x0) * (xs - x0)
    ax.plot(xs, tangent, "--", color="tab:orange", label=f"tangent at x={x0}")
    ax.axvline(x0, color="gray", linewidth=0.5, linestyle=":")
    ax.legend(fontsize=9)
    ax.set_title(f"{'Convex' if name != '$x^3-3x$' else 'Nonconvex'}: {name}")

plt.tight_layout()
plt.show()

print("Notice: for the three convex panels the tangent line stays below (or touches) the curve —")
print("        that is the first-order condition. For x^3-3x, where f''(-1) < 0, the tangent at -1")
print("        lies above the curve on (-2, 2) and crosses it at x = 2.")

Key takeaways#

• $f$ is convex when every chord lies on or above its graph.
• For $x^T Q x$ the chord gap is $\theta(1-\theta)\,d^T Q d$, so convexity is $Q \succeq 0$. In general the Hessian must be PSD everywhere.
• A bowl at every minimum is not convexity. The double well fails the chord test across its hump.
• For a convex function every local minimum is global.

Further reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004). Chapters 2 and 3 cover convex sets and functions. Free at stanford.edu/~boyd/cvxbook.
• Yurii Nesterov, Introductory Lectures on Convex Optimization (Springer, 2004). Chapter 2 covers smooth and strongly convex functions.
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity (2015). A concise free treatment, at arXiv:1405.4980.