Week 3: Gradient Descent Theory

Your training loss falls for three steps, then climbs, then prints nan. You halve the learning rate and the same run settles. One number separates those two runs, and this week finds it. The bowl below is the loss $f(x, y) = \frac{1}{2}(x^2 + 4y^2)$, and the amber path is gradient descent from $(2.6, 1.4)$.

Drag the step size and watch the path. Below $1/L$ it slides down without overshoot. Between $1/L$ and $2/L$ it zigzags across the narrow direction and still lands. At $2/L$ it bounces forever, and past it it climbs the wall and leaves the bowl.

Why the line sits at 2/L#

The gradient of the bowl is $(x, 4y)$, so one step of size $\eta$ maps $x \mapsto (1 - \eta)x$ and $y \mapsto (1 - 4\eta)y$. The caption prints both factors. A coordinate shrinks only when its factor has magnitude below 1. For $y$ that needs $|1 - 4\eta| < 1$, so $0 < \eta < 2/4$. The steepest curvature, 4, sets the limit.

Smoothness: a curvature limit for any function#

A general loss has no single curvature. Smoothness puts a ceiling on it. A differentiable $f$ is $L$-smooth if its gradient is $L$-Lipschitz:

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

For $f(x) = \frac{1}{2}x^T Q x$ with $Q \succeq 0$, the gradient is $Qx$, and $\|Q(x - y)\| \leq \lambda_{\max}(Q)\|x - y\|$. So $L = \lambda_{\max}(Q)$. The bowl has $Q = \mathrm{diag}(1, 4)$ and $L = 4$, the curvature of its narrow direction.

Smoothness gives a quadratic upper bound:

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

With the linear lower bound of convexity (Week 2), a convex $L$-smooth function lies between a plane and a bowl of curvature $L$.

The descent lemma#

Put the step $y = x - \eta \nabla f(x)$ into the upper bound:

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

The bracket is positive when $\eta < 2/L$. That is the line you crossed in the bowl, now for every $L$-smooth function. Past $2/L$ the bound promises nothing, and the bowl diverges. The term $\eta(1 - L\eta/2)$ is largest at $\eta = 1/L$, which gives

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

This is the descent lemma. Each step removes at least $\frac{1}{2L}\|\nabla f\|^2$ of loss while the gradient is nonzero.

Convergence for convex smooth functions#

Start at $x_0$ with distance $R = \|x_0 - x^*\|$ to an optimum $x^*$. After $K$ steps of size $\eta = 1/L$ on a convex $L$-smooth function:

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

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

Strong convexity and the condition number#

A function $f$ is $\mu$-strongly convex if, for some $\mu > 0$,

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

For a quadratic, $\mu = \lambda_{\min}(Q)$. The bowl has $\mu = 1$, so its condition number is $\kappa = L/\mu = 4$. The level sets are ellipses with axis ratio $\sqrt{\kappa} = 2$.

With step $\eta = 2/(L + \mu)$, GD converges linearly (Nesterov 2004, Theorem 2.1.15):

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

The error shrinks by a fixed factor every step, so accuracy $\varepsilon$ costs $\mathcal{O}(\kappa \log(1/\varepsilon))$ iterations.

Worked example. For the bowl, $2/(L + \mu) = 2/5 = 0.4$, which is $1.6/L$ on the slider. The factors are $1 - 0.4 = 0.6$ for $x$ and $1 - 1.6 = -0.6$ for $y$. Both have magnitude $(\kappa - 1)/(\kappa + 1) = 3/5$. Now compare $\eta = 1/L = 0.25$. It sends $y$ to 0 in one step but leaves $x$ at factor $0.75$. After 10 steps, $x$ keeps $0.75^{10} \approx 0.056$ of its start, against $0.6^{10} \approx 0.006$. The fastest step balances the flat direction against the steep one, and it is not $1/L$.

Large $\kappa$ is the hard case. For $f(x) = \frac{1}{2}(x_1^2 + 100x_2^2)$, $\kappa = 100$ and the best factor is $99/101 \approx 0.980$. GD then needs about 115 steps to cut the error by a factor of 10. Adding $\frac{\lambda}{2}\|x\|^2$ to a convex objective makes it $\lambda$-strongly convex, which raises $\mu$, lowers $\kappa$, and is why ridge regression (Week 4) converges faster than plain least squares. Momentum (Week 7) cuts the cost to $\mathcal{O}(\sqrt{\kappa} \log(1/\varepsilon))$. Advanced Optimization goes further.

Knowledge Check#

Browser lab: step sizes and the 2/L boundary#

Run GD on 1D quadratic $f(x) = a x^2$ with $L = 2a$. Compare $\eta = 1/L$ (largest guaranteed decrease) 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", "η=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)
    print(f"{lbl:18s} final |x| = {abs(xs[-1]):.3e}  final loss = {vals[-1]:.3e}")

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()

print("Notice: η ≤ 2/L decreases the loss at every step; past 2/L the iterates oscillate and eventually diverge.")

Key takeaways#

• The step size limit comes from the steepest direction. In the bowl, $y$ has factor $1 - 4\eta$ and leaves once $\eta > 2/4$.
• $L$-smoothness bounds curvature. The descent lemma follows: every step with $\eta < 2/L$ decreases the loss.
• Convex and $L$-smooth gives the sublinear rate $\mathcal{O}(1/K)$. Strong convexity upgrades it to a linear rate with factor $(\kappa - 1)/(\kappa + 1)$.
• The fastest constant step, $2/(L + \mu)$, balances the flat and the steep direction. It is not $1/L$.

Further reading#

• Yurii Nesterov, Introductory Lectures on Convex Optimization (Springer, 2004). Chapter 2 defines smoothness and strong convexity and derives the basic gradient-method rates.
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity (2015). Sections 3.1–3.2 prove the $\mathcal{O}(1/K)$ and linear rates for smooth (strongly) convex GD. Freely available at arXiv:1405.4980.
• Jorge Nocedal & Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006). Chapter 3 collects the step-size and convergence theory used here.