Gradient descent in one page

In one sentence

To minimise a function, take small steps in the direction where it decreases fastest.

The idea

Imagine standing on a hill in fog. You can’t see the valley, but you can feel which way the ground slopes. Step downhill, check again, repeat. That is gradient descent.

The update rule

For parameters $\theta$, a loss function $L(\theta )$ and a learning rate $\eta$:

$${\theta }_{t+1}={\theta }_t-\eta \nabla L({\theta }_t)$$

• $\nabla L$ (the gradient) points uphill, so we subtract it.
• $\eta$ (the learning rate) sets the step size.

Choosing the learning rate

Too small: progress is painfully slow. Too large: you overshoot the valley and bounce around, or diverge.

Example

Minimise $L(x)=x^2$. The gradient is $2x$. Starting at $x_0=4$ with $\eta =0.1$:

Step	$x$	$L(x)$
0	4.00	16.00
1	3.20	10.24
2	2.56	6.55
3	2.05	4.19

Each step shrinks $x$ by 20%, so it converges to the minimum at $x=0$.

x, lr = 4.0, 0.1
for step in range(50):
    x -= lr * 2 * x   # gradient of x^2 is 2x
print(x)  # ~0.00006

Where it’s used

Every neural network is trained with a variant of this, such as SGD, momentum or Adam. A practical use is in the blog: Why I’m writing in public.