Gradient descent, derived and drawn

Gradient descent is what you do when you cannot solve for the best parameters but you can always tell which way is downhill. Stand somewhere on a bumpy surface in fog, feel the slope under your feet, take a step against it, repeat. That is the whole algorithm. The rest of this note is why the step is what it is, how long it should be, and what goes wrong.

Where the update comes from

Let $L(\theta)$ be the loss and take a small step $\delta$. A first-order Taylor expansion says

$$L(\theta + \delta) \approx L(\theta) + \nabla L(\theta)^{\top} \delta$$

For a step of fixed length, the dot product $\nabla L^{\top}\delta$ is most negative when $\delta$ points exactly against the gradient. So the best small step is $\delta = -\eta \nabla L(\theta)$ and the update is

$$\theta \leftarrow \theta - \eta , \nabla L(\theta)$$

The number $\eta > 0$ is the learning rate. Everything interesting is in choosing it.

One dimension, real numbers

Take $L(w) = (w - 3)^2$, so $L'(w) = 2(w - 3)$, and start at $w_0 = 0$ with $\eta = 0.1$. Each step is $w \leftarrow w - 0.1 \cdot 2 (w - 3)$:

  • $w_1 = 0 - 0.1 \cdot 2 \cdot (-3) = 0.6$
  • $w_2 = 0.6 - 0.1 \cdot 2 \cdot (-2.4) = 1.08$
  • $w_3 = 1.464$, $w_4 = 1.7712$, $w_5 = 2.017$

Look at the distance to the minimum: $3, 2.4, 1.92, 1.536, \dots$ It shrinks by a fixed factor of $0.8$ every step. In general the error $e = w - 3$ obeys $e_{t+1} = (1 - 2\eta), e_t$, so $e_t = (1 - 2\eta)^t e_0$. That one formula explains every learning-rate behaviour:

  • $\eta = 0.5$: the factor is $0$, you land on the minimum in one step.
  • $0 < \eta < 0.5$: smooth convergence. Smaller $\eta$ means slower.
  • $0.5 < \eta < 1$: the factor is negative, so you overshoot and zigzag, but still converge.
  • $\eta = 1$: the factor is $-1$. You bounce between $0$ and $6$ forever.
  • $\eta > 1$: the factor is below $-1$. The error grows. You diverge.

Two dimensions: why scaling matters

Now $L(x, y) = x^2 + 10 y^2$, a bowl that is ten times steeper in $y$ than in $x$. The gradient is $(2x, 20y)$ and one step multiplies $x$ by $(1 - 2\eta)$ and $y$ by $(1 - 20\eta)$.

The steep direction sets the speed limit. To keep $y$ from diverging you need $|1 - 20\eta| < 1$, so $\eta < 0.1$. But at a safe $\eta = 0.05$ the $x$ factor is $0.9$, which is slow. Starting from $(1, 1)$, the $x$ coordinate after 50 steps is $0.9^{50} \approx 0.005$ at $\eta = 0.05$, but still $0.36$ at $\eta = 0.01$. The ratio of steepest to shallowest curvature (here 10) is the condition number, and it is the reason you standardize features before running gradient descent: scaling makes the bowl round.

import numpy as np

def descend(grad, p0, lr, steps):
    p = np.array(p0, dtype=float)
    path = [p.copy()]
    for _ in range(steps):
        p = p - lr * grad(p)
        path.append(p.copy())
    return np.array(path)

grad = lambda p: np.array([2 * p[0], 20 * p[1]])

for lr in (0.01, 0.05, 0.09, 0.11):
    end = descend(grad, [1.0, 1.0], lr, 50)[-1]
    print(lr, end)
# 0.01 -> x still 0.36 after 50 steps (too slow)
# 0.05 -> both near zero
# 0.09 -> both near zero, y zigzags with factor -0.8
# 0.11 -> y is about 9000 and growing (diverged)

Drawing it

Sketch the contours of this bowl as long thin ellipses. Plot the path for $\eta = 0.09$: it zigzags across the narrow direction while crawling along the long one. Now sketch the same bowl after dividing $y$ by $\sqrt{10}$: the ellipses become circles and the path goes straight to the centre. If you remember one picture from this week, make it that pair.

From batch to stochastic

For a dataset of $n$ examples the loss is an average, $L = \frac{1}{n}\sum_i \ell_i$, and the full gradient costs $O(n)$ per step. Mini-batch gradient descent estimates it from a random subset of $B$ examples. The estimate is noisy but unbiased, and it makes each step $n / B$ times cheaper. The noise even helps a little on bumpy losses. You will use full-batch steps in weeks 3 and 4 because the datasets are small and exact gradients make debugging easier.

Common mistakes

  • Wrong sign. You subtract the gradient. If your loss goes up, check this first.
  • No gradient check. Compare against $\frac{L(\theta + \epsilon) - L(\theta - \epsilon)}{2\epsilon}$ with $\epsilon = 10^{-5}$ before you trust any gradient you derived by hand.
  • Unscaled features. One feature measured in thousands and another in fractions gives a very ill-conditioned bowl.
  • Judging by the final loss only. Plot the loss curve. A curve that falls, then rises, means the rate is too big. A curve that is almost flat means it is too small or the features are unscaled.
  • Stopping at the first flat spot. On convex losses (linear and logistic regression) the minimum is global. Beyond them, a flat gradient does not prove you are done.

Check yourself

  • For $L(w) = (w-3)^2$, what is the update factor on the error, and for which $\eta$ does the method diverge?
  • Why does a bowl with condition number 100 force a small learning rate even in its shallow direction?
  • Derive $\nabla_w \frac{1}{2n}\lVert Xw - y \rVert^2$ and explain why it equals $\frac{1}{n} X^{\top}(Xw - y)$.
  • What does standardizing features do to the contours of the loss?