Gradient Descent — Learning by Walking Downhill

Start here Imagine you are on a foggy hill and want to reach the valley. You can’t see far, but you can feel which way the ground slopes under your feet. So you take a small step downhill, feel again, and repeat. That is gradient descent. This page shows why “downhill” means “opposite to the gradient”, using a short Taylor-series argument, and then works it out for the sigmoid neuron.

Find a better way to move on the error surface, so we reach the minimum quickly, without brute-force search.

Put all parameters in one vector: $\theta = [w, b]$ (start randomly).

We will move by a small change $\Delta \theta = [\Delta w, \Delta b]$. To be careful, we move only a small amount $\eta$ (eta, the learning rate) in that direction:

$\theta _{\mathrm{new}} = \theta + \eta \cdot \Delta \theta$

The question: what is the right $\Delta \theta$? The answer comes from the Taylor series.

A Taylor series approximates a smooth function L(w) near a point $w_{0}$ using polynomials. Higher degree → better approximation.

$L(w) = L(w_{0}) + L'(w_{0})/1! \cdot (w - w_{0}) + L''(w_{0})/2! \cdot (w - w_{0})^{2} + L'''(w_{0})/3! \cdot (w - w_{0})^{3} + \ldots$

• Linear approximation (degree 1):$L(w) \approx L(w_{0}) + L'(w_{0})(w - w_{0})$
• Quadratic approximation (degree 2): add the L″ term.

Close to $w_{0}$, even the straight-line approximation is very good.

Everyday example On a small patch of a curved road, the road looks straight. The smaller the patch, the better a straight line fits it.

Write $\Delta \theta =$ u. From the Taylor series (for many variables):

$L(\theta + \eta u) = L(\theta ) + \eta \cdot u^{T}\nabla \theta L(\theta ) + (\eta ^{2}/2!) \cdot u^{T}\nabla ^{2}L(\theta )u + \ldots$

$\eta$ is small, so $\eta ^{2}, \eta ^{3}, \ldots$ are tiny and can be dropped:

$L(\theta + \eta u) \approx L(\theta ) + \eta \cdot u^{T}\nabla \theta L(\theta )$

The move is good only if the new loss is smaller: $L(\theta + \eta u) - L(\theta ) < 0$, which means

$u^{T}\nabla \theta L(\theta ) < 0$

How negative can it be? $Let \beta$ be the angle between u and $\nabla \theta L(\theta )$:

$-1 \le \cos \beta = u^{T}\nabla \theta L(\theta ) / (\Vert u\Vert \cdot \Vert \nabla \theta L(\theta )\Vert ) \le 1$

Multiply by $k = \Vert u\Vert \cdot \Vert \nabla \theta L(\theta )\Vert$:

$-k \le k \cos \beta = u^{T}\nabla \theta L(\theta ) \le k$

The change in loss is most negative when $\cos \beta = -1, i$.e. $\beta = 180{}^\circ$.

Move opposite to the gradient:

• $w_{t+1} = w_t - \eta \nabla w_t$
• $b_{t+1} = b_t - \eta \nabla b_t$

where $\nabla w_t = \partial L(w, b)/\partial w$ and $\nabla b_t = \partial L(w, b)/\partial b$, both evaluated at $w = w_t, b = b_t$.

t ← 0;  max_iterations ← 1000
w, b ← random
while t < max_iterations:
    w ← w − η ∇w
    b ← b − η ∇b
    t ← t + 1

Now we need $\nabla w$ and $\nabla b$ for our sigmoid neuron.

Model: $f(x) = \frac{1}{1 + e^{-(wx + b)}}$. Take one point (x, y) and loss $L = \frac{1}{2} (f(x) - y)^{2}$. (The ½ makes the 2 from the square cancel.)

Step 1 — outer part (chain rule):

$\nabla w = \partial /\partial w [\frac{1}{2} (f(x) - y)^{2}] = \frac{1}{2} \cdot 2 (f(x) - y) \cdot \partial /\partial w (f(x) - y) = (f(x) - y) \cdot \partial f(x)/\partial w$

Step 2 — derivative of the sigmoid with respect to w:

$\partial /\partial w [\frac{1}{1 + e^{-(wx+b)}}] = -\frac{1}{1 + e^{-(wx+b)}}^{2} \cdot \partial /\partial w [e^{-(wx+b)}] = -\frac{1}{1 + e^{-(wx+b)}}^{2} \cdot e^{-(wx+b)} \cdot \partial /\partial w [-(wx + b)] = -\frac{1}{1 + e^{-(wx+b)}}^{2} \cdot e^{-(wx+b)} \cdot (-x) = [\frac{1}{1 + e^{-(wx+b)}}] \cdot [e^{-(wx+b)}/(1 + e^{-(wx+b)})] \cdot x =$f(x) · (1 − f(x)) · x

(because $e^{-z}/(1 + e^{-z}) = 1 - \frac{1}{1 + e^{-z}} = 1 - f(x)$.)

Result for one point:

• $\nabla w = (f(x) - y) \cdot f(x) \cdot (1 - f(x)) \cdot x$
• $\nabla b = (f(x) - y) \cdot f(x) \cdot (1 - f(x))$ (same, but $\partial (wx + b)/\partial b = 1$ instead of x)

For two (or N) points, add them up:

$\nabla w = \sum _{i} (f(x_{i}) - y_{i}) \cdot f(x_{i}) \cdot (1 - f(x_{i})) \cdot x_{i} \nabla b = \sum _{i} (f(x_{i}) - y_{i}) \cdot f(x_{i}) \cdot (1 - f(x_{i}))$

• $\nabla w = -0.003446 + (-0.002046) =$−0.005492
• $\nabla b = -0.006893 + (-0.000818) =$−0.007711
• $w_{\mathrm{new}} = -2 - 1 \times (-0.005492) =$−1.99451
• $b_{\mathrm{new}} = -2 - 1 \times (-0.007711) =$−1.99229

The loss goes from 0.41581 to 0.41573 — a very small improvement, because the starting point is on a flat part of the surface (tiny gradients).

Lecture example — running it Running the full loop (computed in code): loss after 10 steps $\approx 0.4148$ (still flat), after 100 steps $\approx 0.0177$, after 1000 steps $\approx 0$ with $w \approx 1.792, b \approx -2.282$ — the exact best answer. Slow at first on the flat region, then fast.

Later in the course we study gradient descent and its variants in much more detail (Week 4). For now we have an algorithm to learn the parameters of a sigmoid neuron.

In one line: Gradient descent repeatedly moves the parameters a small step $\eta$ opposite to the gradient, because that direction reduces the loss fastest.

Exam words: gradient descent, learning rate $\eta$, Taylor series, linear approximation, gradient $\nabla \theta L$, angle $\beta = 180{}^\circ$, update rule, $\nabla w = (f - y) f (1 - f) x, \nabla b = (f - y) f (1 - f)$, epoch.