Gradient descent

Most models have no formula for their best parameters. Gradient descent finds them by walking downhill.

Picture the loss as a valley, with the parameters (w, b) as your position. You cannot see the bottom, but you can feel which way the ground slopes under your feet. Take a small step downhill; feel again; repeat. When the ground is flat, you are at the bottom.

The update rule

The gradient is the slope of the loss in each direction: ∂L/∂w ("how much the loss grows if w grows a little") and ∂L/∂b. Go the opposite way, by a step of size α, the learning rate:

w ← w − α × ∂L/∂w
b ← b − α × ∂L/∂b

For a line with the mean squared error, calculus gives:

∂L/∂w = (2/n) × Σ (ŷᵢ − yᵢ) × xᵢ
∂L/∂b = (2/n) × Σ (ŷᵢ − yᵢ)

If the predictions are too high (ŷ − y is positive), the gradient is positive and w and b go down: exactly what is needed.

Step through: the line starts flat at y = 0, swings up towards the points, and the loss on the right falls fast, then slowly. Now pick a learning rate of 0.1 or 0.2: each step jumps past the bottom, further every time, and the loss explodes. With 0.001 it is safe but painfully slow.

points = [(1, 2), (2, 4.5), (3, 5.5), (4, 8.5), (5, 9.5)]
rate = 0.03
n = len(points)

def loss(w, b):
    return sum((w * x + b - y) ** 2 for x, y in points) / n

w, b = 0.0, 0.0
for step in range(1, 31):
    dw = db = 0.0
    for x, y in points:
        error = w * x + b - y
        dw += 2 / n * error * x
        db += 2 / n * error
    w, b = w - rate * dw, b - rate * db
    if step in (1, 2, 5, 10, 30):
        print(f"step {step:2}: w = {w:.4f}, b = {b:.4f}, loss = {loss(w, b):.4f}")

The program is the simulator's calculation, on the same five points with rate 0.03. The least-squares formulas give the best line, w = 1.9 and b = 0.3, with a loss of 0.18. Gradient descent gets close fast: by step 5 the loss is 0.187. The rest is slow: w and b creep along a long, shallow valley, which is why the loss curve flattens out.

Choosing the learning rate

• Too big: the steps overshoot, and the loss grows or jumps around.
• Too small: the loss falls, but takes forever.
• Scaling the features first (previous lessons) lets one learning rate suit every weight.
• In practice: try 0.1, 0.01, 0.001, ..., and watch the loss.

Batches

• Batch gradient descent uses all the examples for each step (as above): smooth, but slow on millions of examples.
• Stochastic gradient descent (SGD) uses one example per step: noisy, but fast, and the noise can help escape bad spots.
• Mini-batch uses a few dozen examples per step: the usual choice, and the one GPUs are built for.

For a line, the MSE valley is a perfect bowl, with one bottom (it is convex). Neural networks have bumpy losses with many valleys, and gradient descent finds a good bottom, not necessarily the best one. That works surprisingly well in practice.

Mark lesson complete