Convexity, and why it makes optimization tractable · Advanced Calculus Topics

§14.0 closed on an honest limitation: gradient descent only guarantees convergence to a critical point, not necessarily the best one. This lesson identifies the exact extra condition on f that closes that gap entirely — convexity — and it turns out to be nothing more than §3.5's concavity test, renamed and given a sharper geometric meaning.

The definition

A function f is convex if, for any two points x,y in its domain and any t\in[0,1]:

$f\big((1-t)x+ty\big)\le(1-t)f(x)+tf(y)$

Geometrically: the graph of f never lies above the straight-line chord connecting any two of its points — the function is "bowl-shaped," curving upward or staying flat, never dipping into a wave or an S-curve. f is strictly convex if the inequality is strict for x\ne y — a genuine, uninterrupted bowl with no flat stretches.

The second-derivative test for convexity

For a twice-differentiable function of one variable:

$f\text{ is convex}\iff f''(x)\ge0\text{ for every }x\text{ in the domain}$

This is §3.5's "concave up" condition, exactly, just given a formal name and a global (rather than local, interval-by-interval) reading: where §3.5 used f''>0 to identify a stretch of a curve bending upward, convexity asks whether that bending-upward behavior holds everywhere the function is defined. f''(x)>0 everywhere gives strict convexity; f''(x)\ge0 (allowing flat stretches, like f(x)=x^4 at x=0) gives plain convexity.

Recognizable convex functions: f(x)=x^2 (f''=2>0 always), any quadratic ax^2+bx+c with a>0, f(x)=e^x (f''=e^x>0 always). Recognizable non-convex functions: f(x)=x^3 (has an inflection point at x=0, §3.5 — concave down for x<0, concave up for x>0, never uniformly one or the other), f(x)=\sin x (oscillates between concave up and concave down forever).

The payoff: every local minimum is global

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

Why: suppose x^* is a local minimum but not global — some other point y has f(y)<f(x^*). The convexity inequality, applied along the segment from x^* to y, forces f to be below the chord connecting them near x^* (whenever f(y)<f(x^*), the chord dips below f(x^*) moving toward y) — contradicting x^* being a local minimum at all, since points arbitrarily close to x^* in that direction would have to have smaller f-values too. No genuinely separate "worse" local minimum can coexist with a convex shape.

This is exactly what closes §14.0's gap: for a convex f, gradient descent converging to any critical point automatically means it found the minimum — no risk of settling for a lesser local minimum elsewhere, regardless of starting point or learning rate (within the range that guarantees convergence at all, §14.0's own condition).

Why this matters for machine learning

Many important loss functions used to train models — including linear regression's mean squared error and logistic regression's log-loss (§14.5's subject) — are convex by construction. This is precisely why gradient descent is trusted to train them reliably: convexity guarantees whatever critical point the algorithm settles on is the actual optimal fit, not an accident of where training happened to start. Non-convex loss functions (as in deep neural networks) lose this guarantee entirely, which is why training such models is empirically harder and more sensitive to initialization — a direct, practical consequence of the theorem above.

Doing it in Python

Confirming a quadratic is convex, and that gradient descent reaches the same global minimum from wildly different starting points:

def f(x):
    return x**2 - 4*x + 5

def f_prime(x):
    return 2*x - 4

# f''(x) = 2 > 0 everywhere -- strictly convex
for x0 in (-10.0, 0.0, 50.0):
    x = x0
    alpha = 0.1
    for _ in range(100):
        x = x - alpha * f_prime(x)
    print(f"starting at x0={x0:>6}: converges to x={x:.6f}, f(x)={f(x):.6f}")

Contrasting with a non-convex function — different starting points land on different local minima with different function values:

def f(x):
    return x**4 - 4*x**2 + x

def f_prime(x):
    return 4*x**3 - 8*x + 1

for x0 in (-2.0, 2.0):
    x = x0
    alpha = 0.01
    for _ in range(2000):
        x = x - alpha * f_prime(x)
    print(f"starting at x0={x0:>5}: converges to x={x:.4f}, f(x)={f(x):.4f}")
print("\ndifferent starting points -> different local minima -- no convexity guarantee")

Verifying f''\ge0 symbolically for a candidate function, as a direct convexity check:

import sympy as sp

x = sp.Symbol('x')
f = sp.exp(x)

f_double_prime = sp.diff(f, x, 2)
print(f"f''(x) = {f_double_prime}")
print("always positive for real x -- e^x is strictly convex everywhere")

Worked example

Show that f(x)=x^2-4x+5 is convex, and find its global minimum.

$f'(x)=2x-4,\qquad f''(x)=2$

f''(x)=2>0 for every x — no exceptions, no sign changes.

$\boxed{f\text{ is strictly convex on all of }\mathbb R}$

Finding the minimum: since f is convex, any critical point is automatically the global minimum (no need for §10.6's separate second-derivative classification — convexity already settles it).

$f'(x)=0\ \Longrightarrow\ 2x-4=0\ \Longrightarrow\ x=2$

$f(2)=4-8+5=1$

$\boxed{\text{global minimum: }f(2)=1}$

Sanity check. Completing the square directly confirms this without calculus at all: f(x)=x^2-4x+5=(x-2)^2+1 — a perfect square plus 1, manifestly minimized at x=2 with minimum value 1, since (x-2)^2\ge0 always. This matches the calculus-based answer exactly, and the "Doing it in Python" demonstration confirmed gradient descent reaches this same x=2 regardless of whether it started at -10, 0, or 50 — the concrete payoff of convexity, verified numerically. ✓

Your turn

1. Determine whether f(x)=e^x-x is convex, using the second-derivative test.

2. Determine whether f(x)=x^3-3x is convex on all of \mathbb{R} (check f''(x)'s sign across the whole domain, not just at one point).

3. True or false: if f and g are both convex, then f+g is also convex.

Solutions

1. f'(x)=e^x-1, f''(x)=e^x. Since e^x>0 for every real x:

$\boxed{\text{convex on all of }\mathbb R}$

2. f'(x)=3x^2-3, f''(x)=6x. This is positive for x>0 but negative for x<0 — the sign changes, so f''(x)\ge0 does not hold everywhere.

$\boxed{\text{not convex on all of }\mathbb R}$

(It is convex on the restricted domain x\ge0 alone, since f''\ge0 holds throughout that half-line — convexity can be a property of a function restricted to part of its domain, not only the whole real line.)

3. True. If f''\ge0 and g''\ge0 everywhere, then (f+g)''=f''+g''\ge0+0=0 everywhere too (sum of nonnegative numbers is nonnegative) — so f+g is convex. This fact is used constantly in machine learning: a loss function built by adding several convex pieces (like a convex data-fit term plus a convex regularization penalty) is guaranteed convex overall, without needing to re-derive convexity for the combined expression from scratch.

Check yourself in code

Confirm f(x)=x^2-4x+5 is convex by checking f''(x), then run gradient descent from x_0=-10 and x_0=50 to confirm both converge to the same minimum.

Print exactly this:

f''(x) = 2
from x0=-10: x=2.0, f(x)=1.0
from x0=50: x=2.0, f(x)=1.0

import sympy as sp

x = sp.Symbol('x')
f_sym = x**2 - 4*x + 5
f_double_prime = sp.diff(f_sym, x, 2)
print("f''(x) = ...")

def f(x):
    return x**2 - 4*x + 5

def f_prime(x):
    return 2*x - 4

for x0 in (-10.0, 50.0):
    xv = x0
    alpha = 0.1
    for _ in range(100):
        xv = xv - alpha * f_prime(xv)
    print(f"from x0={int(x0)}: x=...")

import sympy as sp

x = sp.Symbol('x')
f_sym = x**2 - 4*x + 5
f_double_prime = sp.diff(f_sym, x, 2)
print(f"f''(x) = {f_double_prime}")

def f(x):
    return x**2 - 4*x + 5

def f_prime(x):
    return 2*x - 4

for x0 in (-10.0, 50.0):
    xv = x0
    alpha = 0.1
    for _ in range(100):
        xv = xv - alpha * f_prime(xv)
    print(f"from x0={int(x0)}: x={round(xv,6)}, f(x)={round(f(xv),6)}")

Convexity, f''(x)\ge0 everywhere, is §3.5's concavity test elevated from a local to a global condition, and it guarantees every local minimum is the global minimum — the exact fact that upgrades §14.0's gradient descent from "converges to some critical point" to "converges to the optimum," which is why so many machine-learning loss functions are deliberately designed to be convex. Sums of convex functions stay convex, letting complex loss functions be assembled from simple, independently-verified convex pieces.

Next: derivatives of vector-valued and multi-output functions, organized into matrices — the Jacobian and the Hessian, generalizing this lesson's scalar f'' to functions of many variables at once.

12. Convexity, and why it makes optimization tractable