Week 3: Gradient Descent Theory

Smoothness (L-Lipschitz Gradient)#

A differentiable function $f$ is $L$-smooth if its gradient is $L$-Lipschitz continuous:

$\|\nabla f(x) - \nabla f(y)\|_2 \leq L \|x - y\|_2 \quad \text{for all } x, y$

In plain terms: the gradient cannot change too fast. If you move a small distance, the gradient changes by at most $L$ times that distance.

This implies a powerful quadratic upper bound (sometimes called the descent lemma):

$f(y) \leq f(x) + \nabla f(x)^T (y - x) + \frac{L}{2}\|y - x\|_2^2$

The convex first-order condition says $f(y) \geq \text{linear}$. Smoothness adds the reverse: $f(y) \leq \text{linear} + \frac{L}{2}\|y-x\|^2$. Together, $L$-smooth convex functions are sandwiched between two quadratics of curvature $L$.

Worked example: Is $f(x) = \frac{1}{2}x^T Q x$ with $Q \succeq 0$ smooth?

The gradient is $\nabla f(x) = Qx$, and $\|\nabla f(x) - \nabla f(y)\| = \|Q(x-y)\| \leq \|Q\|_{\text{op}} \|x-y\|$. So $f$ is $L$-smooth with $L = \|Q\|_{\text{op}} = \lambda_{\max}(Q)$, the largest eigenvalue of $Q$.

For the 2D quadratic from Week 1, $Q = \begin{pmatrix}1 & 0\\ 0 & 2\end{pmatrix}$, so $L = 2$.

Descent Lemma#

Plugging the GD update $y = x - \eta \nabla f(x)$ into the quadratic upper bound:

$f(x - \eta \nabla f(x)) \leq f(x) + \nabla f(x)^T (-\eta \nabla f(x)) + \frac{L}{2}\|-\eta \nabla f(x)\|^2$ $= f(x) - \eta \|\nabla f(x)\|^2 + \frac{L\eta^2}{2} \|\nabla f(x)\|^2$ $= f(x) - \eta\left(1 - \frac{L\eta}{2}\right)\|\nabla f(x)\|^2$

For the decrease term to be meaningful (negative), we need $1 - \frac{L\eta}{2} > 0$, i.e. $\eta < 2/L$. The optimal choice minimises the coefficient: $\eta = 1/L$ gives

$f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2$

This is the descent lemma: with step size $\eta \leq 1/L$, GD guarantees a decrease of at least $\frac{1}{2L}\|\nabla f\|^2$ per iteration. As long as the gradient is nonzero, we make progress.

Convergence for Convex Smooth Functions#

Starting from $x_0$ with distance $R = \|x_0 - x^*\|$ to an optimum $x^*$, after $K$ iterations of GD with $\eta = 1/L$ on a convex $L$-smooth function:

$f(x_K) - f(x^*) \leq \frac{2L\|x_0 - x^*\|^2}{K}$

This is the $\mathcal{O}(1/K)$ sublinear rate. To halve the optimality gap, you need about twice as many iterations. To reach accuracy $\varepsilon$, you need $K \propto \frac{L R^2}{\varepsilon}$ iterations.

What this means in practice: GD on a convex problem is reliable but not fast. Early iterations reduce the loss quickly; later iterations are slow. If you need high accuracy (small $\varepsilon$), GD alone is expensive.

Strong Convexity#

A function $f$ is $\mu$-strongly convex if there exists $\mu > 0$ such that:

$f(y) \geq f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2}\|y - x\|_2^2$

This is the convex first-order condition plus a quadratic lower bound. The function must curve upward at rate at least $\mu$ everywhere.

For quadratics $f(x) = \frac{1}{2}x^T Q x$, strong convexity means $Q \succeq \mu I$, i.e. $\lambda_{\min}(Q) \geq \mu > 0$. The 2D quadratic from Week 1 has $Q = \begin{pmatrix}1 & 0\\ 0 & 2\end{pmatrix}$, so $\mu = 1$.

Adding $\ell_2$ regularisation $\frac{\lambda}{2}\|x\|^2$ to any convex objective makes it $\lambda$-strongly convex. This is why ridge regression (Week 4) has better convergence than plain least squares.

With $\mu$-strong convexity, GD with $\eta = 2/(L + \mu)$ achieves linear convergence:

$f(x_K) - f(x^*) \leq \left(\frac{\kappa - 1}{\kappa + 1}\right)^{2K} (f(x_0) - f(x^*))$

where $\kappa = L/\mu$ is the condition number. The gap shrinks by a constant factor every iteration, giving $\mathcal{O}(\log(1/\varepsilon))$ complexity.

Condition Number#

The condition number $\kappa = L/\mu$ governs how fast GD converges:

• $\kappa$ small (well-conditioned): GD converges quickly. The loss surface is roughly spherical.
• $\kappa$ large (ill-conditioned): GD converges slowly. The loss surface has elongated valleys where GD zigzags.
• $\kappa = 1$: The function is perfectly spherical; GD converges in one step with the right $\eta$.

GD's $\mathcal{O}(\kappa \log(1/\varepsilon))$ complexity for strongly convex functions is why we later introduce momentum (Week 7 — reduces to $\mathcal{O}(\sqrt{\kappa})$) and adaptive methods (Week 8).

Worked example: For the 2D quadratic $f(x) = \frac{1}{2}(x_1^2 + 2x_2^2)$:

• $L = 2$ (largest eigenvalue)
• $\mu = 1$ (smallest eigenvalue)
• $\kappa = 2$ — well-conditioned, GD converges quickly
• A less friendly case: $f(x) = \frac{1}{2}(x_1^2 + 100x_2^2)$ with $\kappa = 100$, where GD will creep along the narrow valley

Browser lab#

Run GD on 1D quadratic $f(x) = a x^2$ with $L = 2a$. Compare $\eta = 1/L$ (safe, optimal) vs $\eta = 1.8/L$ (near-divergence) vs $\eta = 2.1/L$ (divergence).

import numpy as np
import matplotlib.pyplot as plt

a = 5.0
L = 2 * a
x0 = 4.0
K = 20

def run_gd(eta, x0, K):
    x = x0
    vals = [a * x**2]
    xs = [x]
    for _ in range(K):
        g = 2 * a * x
        x = x - eta * g
        xs.append(x)
        vals.append(a * x**2)
    return np.array(xs), np.array(vals)

etas = [0.5/L, 1/L, 1.8/L, 2.1/L]
labels = ["η=0.5/L", "η=1/L (safe)", "η=1.8/L (osc)", "η=2.1/L (diverge)"]

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4.5))
ks = np.arange(K + 1)

for eta, lbl in zip(etas, labels):
    xs, vals = run_gd(eta, x0, K)
    ax1.plot(ks, vals, "o-", markersize=3, label=lbl)
    ax2.plot(ks, np.abs(xs), "o-", markersize=3, label=lbl)

ax1.set_xlabel("Iteration k"); ax1.set_ylabel("f(x_k)")
ax1.set_title(f"Loss vs iteration (L={L})")
ax1.set_yscale("log"); ax1.legend()
ax2.set_xlabel("Iteration k"); ax2.set_ylabel("|x_k|")
ax2.set_title("Distance to optimum")
ax2.set_yscale("log"); ax2.legend()
plt.tight_layout()
plt.show()