Gradient Descent

The Idea: Walking Down a Hill in Fog

Imagine you're standing somewhere on a hillside in thick fog. You can't see the valley, but you can feel the slope under your feet. A sensible plan:

1. Feel which way the ground slopes down.
2. Take a step that way.
3. Repeat until the ground feels flat.

That's gradient descent. The hillside is the cost function bowl, your position is the current values of ${\theta }_0$ and ${\theta }_1$, and "feeling the slope" means computing the gradient.

In the video we freeze ${\theta }_0$ at 22 so the bowl is a simple 2D curve. The real algorithm moves both parameters at once, but the idea is identical.

The Gradient Tells You the Way Down

The gradient is the slope of the cost function at your current point. It's just the derivative.

• If the slope is positive, the cost goes up to the right, so move left (decrease $\theta$).
• If the slope is negative, the cost goes up to the left, so move right (increase $\theta$).
• If the slope is zero, you're at the bottom. Stop.

In both cases you move against the slope. That's why there's a minus sign in the update rule.

The Update Rule

Repeat until the cost stops falling:

• $:=$ means "update to". It's an assignment, not an equation.
• $\alpha$ (alpha) is the learning rate: how big each step is.
• $\frac{\partial J}{\partial {\theta }_j}$ is the gradient for parameter ${\theta }_j$.

For linear regression with $J=\frac{1}{2m}\sum ({\hat{y}}_i-y_i{)}^2$, the derivatives work out to:

Notice the $\frac{1}{2}$ in the cost function has cancelled the 2 from the square. That was the whole reason for putting it there.

One Step by Hand

Same five students: hours 1 to 5, marks 20, 40, 50, 40, 50. Start at ${\theta }_0=0,{\theta }_1=0$ with learning rate $\alpha =0.05$.

Predictions are all 0, so the errors $\hat{y}-y$ are −20, −40, −50, −40, −50.

Starting cost: $J=\frac{1}{10}(400+1600+2500+1600+2500)=860$.

Gradients:

Update:

New cost: the predictions $2+6.6x$ are 8.6, 15.2, 21.8, 28.4, 35, which gives $J=189.98$. One step, and the cost fell from 860 to about 190. Keep going and it slides all the way down to the minimum.

Gradient Descent in NumPy

import numpy as np

x = np.array([1, 2, 3, 4, 5])
y = np.array([20, 40, 50, 40, 50])
m = len(x)

def cost(t0, t1):
    return np.sum((t0 + t1 * x - y) ** 2) / (2 * m)

theta0, theta1 = 0.0, 0.0
alpha = 0.05
history = []

for i in range(5000):
    error = theta0 + theta1 * x - y
    grad0 = error.sum() / m
    grad1 = (error * x).sum() / m
    theta0, theta1 = theta0 - alpha * grad0, theta1 - alpha * grad1   # simultaneous update
    history.append(cost(theta0, theta1))

print(f"start cost:        {cost(0, 0):.1f}")
print(f"after 1 step:      {history[0]:.1f}")
print(f"theta0 = {theta0:.2f}, theta1 = {theta1:.2f}")
print(f"final cost:        {history[-1]:.1f}")

start cost:        860.0
after 1 step:      190.0
theta0 = 22.00, theta1 = 6.00
final cost:        24.0

Gradient descent found θ0 = 22 and θ1 = 6, the same line we got by hand with least squares, and the same minimum cost of 24.

The Learning Rate α

The learning rate is the most important knob in gradient descent.

Why do the steps shrink on their own even with a fixed $\alpha$? Because the step is $\alpha \times$ gradient, and the gradient gets smaller as you approach the flat bottom.

Watching It Blow Up

Change one number, alpha = 0.2, and print the cost for the first three steps:

theta0, theta1, alpha = 0.0, 0.0, 0.2
for i in range(3):
    error = theta0 + theta1 * x - y
    theta0, theta1 = theta0 - alpha * error.sum() / m, theta1 - alpha * (error * x).sum() / m
    print(f"step {i + 1}: cost = {cost(theta0, theta1):.1f}")

step 1: cost = 1554.1
step 2: cost = 2851.6
step 3: cost = 5275.2

The cost almost doubles every step. Let it run for 5000 steps and the numbers overflow to inf and nan. If your cost goes up, lower the learning rate first.

Gradient Descent vs the Formula

For simple linear regression we already had a formula (least squares). So why bother?

scikit-learn's LinearRegression uses a direct solver. But almost every other model you'll meet, logistic regression and every neural network included, is trained with gradient descent or one of its cousins.

The Three Flavours

Summary

• Gradient descent repeats ${\theta }_j:={\theta }_j-\alpha \frac{\partial J}{\partial {\theta }_j}$ until the cost stops falling.
• The gradient points uphill, so we step the opposite way.
• The learning rate $\alpha$ controls step size: too small is slow, too big diverges.
• On our data it reaches the same line as least squares: $\hat{y}=22+6x$.
• Next: how do we say how good that line is? With R squared.