ML2.3 · LESSON 3 OF 6

Gradient descent from scratch

Fit a linear predictor by hand, implement its loss and gradient, then compare with a library solution.

THE IDEA

Finding the bottom of the bowl by walking downhill

Every pair (w, b) has a loss. Draw the pairs as a map with w across and b up, and the loss becomes terrain. For squared error with a line the terrain is a single smooth bowl. The contour lines in the picture connect pairs with the same loss; they are ovals closing in on the lowest point. Gradient descent starts anywhere and repeatedly takes a step downhill.

The gradient is the vector of slopes of the loss in each direction. For the mean squared error with residual rᵢ = w·xᵢ + b − yᵢ:

The gradient of MSE and the update rule

dL/dw = (2/n) * sum( r_i * x_i )
dL/db = (2/n) * sum( r_i )

w = w - lr * dL/dw
b = b - lr * dL/db

The learning rate lr sets the step length. Check with tiny numbers: x = [1, 2], y = [2, 4] and the starting point w = 1, b = 0 give residuals -1 and -2, so dL/dw = (2/2)(−1·1 + −2·2) = −5 and dL/db = (2/2)(−1 − 2) = −3. With lr = 0.1 the new point is w = 1.5, b = 0.3, and the MSE falls from 2.5 to 0.265.

learning rate = 0.1

iteration = 0 (w, b) = (-1.000, -3.000) loss = 74.723 gradient = (-38.305, -7.533) lowest possible loss = 1.881

Step through gradient descent on the real 12-point data. Change the learning rate: too small is slow, near 0.1 is quick, above about 0.16 it diverges.

Step 1 of 4

Pick a start. Start at w = -1, b = -3. The loss there is 74.72.

The learning rate is a speed limit

On this problem the largest learning rate that still converges is 0.157. Below it, the loss shrinks each step. Above it, every step overshoots the valley by more than it started with, and the loss grows without bound. This limit is set by the steepest direction of the bowl, so it depends on the data.

Predict first. You raise the learning rate from 0.1 to 0.2 on this data and run 6 steps. What do you expect?

Chapter context

Linear regression fits a weighted sum of features. The model is simple enough to inspect numerically, making it a useful bridge between geometry, optimization and software implementation.

TRY IT YOURSELF

Part 1. Do it with the visual

The slider sets the learning rate and restarts the path. Step and Run 10 extend the path with that rate.

learning rate = 0.05

iteration = 0 (w, b) = (-1.000, -3.000) loss = 74.723 gradient = (-38.305, -7.533) lowest possible loss = 1.881

To do: Take a first step from the start point and see the loss go down
To do: Pick a learning rate that gets within 0.01 of the lowest possible loss in at most 25 steps
To do: Make it diverge: a learning rate so large that after 6 steps the loss is higher than where you started
To do: Show that a tiny rate is safe but slow: a rate of 0.01 or less, 25 steps, loss lower than at the start but still more than 1 above the minimum

Part 2. Do it in code

gradient(w, b, x, y) returns (dw, db), the derivatives of MSE = mean((w * x + b - y) ** 2): dw = 2 * mean(r * x), db = 2 * mean(r) where r = w * x + b - y.
gradient_descent(x, y, lr, n_iter, w0=0.0, b0=0.0) repeats w -= lr * dw, b -= lr * db for n_iter iterations and returns (w, b, losses). losses has n_iter + 1 entries: the MSE before any step, then after each step.
It must not crash when the learning rate is too large: the losses should simply blow up.

import numpy as np

def gradient(w, b, x, y):
    # return (dw, db)
    pass

def gradient_descent(x, y, lr, n_iter, w0=0.0, b0=0.0):
    # return (w, b, losses)
    pass

print(gradient(1.0, 0.0, [1, 2], [2, 4]))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

For one residual -2 and feature 3, what is the contribution to d(residual squared)/dw?

A2*(-2)*3 = -12: the derivative of r squared is 2r, times the feature value because dr/dw = x.B-6, because the derivative of r squared is 2r and the feature value is not involved.C-4, because the contribution is the residual times 2 and the feature value is added, not multiplied.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

\hat y_i=x_i^Tw+b,\quad L=\frac1n\sum_i(\hat y_i-y_i)^2.

\nabla_w L=\frac2nX^T(Xw+b\mathbf1-y),\quad \partial_bL=\frac2n\sum_i(\hat y_i-y_i).

When invertible, a no-intercept least-squares solution is $(X^TX)^{-1}X^Ty$ . Use a pseudoinverse or suitable solver otherwise.

Worked example

Use x=[1,2], y=[2,4], w=1 and b fixed at zero. Predictions [1,2] give residuals [-1,-2], so MSE=(1+4)/2=2.5. The w gradient is 2/2×(−1×1−2×2)=−5. With eta=0.1, w becomes 1.5 and MSE falls to (0.25+1)/2=0.625.

Reference code

The following example uses the Python standard library and does not call a remote service.

x, y, w = [1,2], [2,4], 1.0
mse = lambda weight: sum((weight*a-b)**2 for a,b in zip(x,y))/len(x)
grad = 2/len(x)*sum((w*a-b)*a for a,b in zip(x,y))
assert mse(w) == 2.5 and grad == -5
w -= .1*grad
assert w == 1.5 and mse(w) == .625

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A low residual does not show that a weight is causal. The closed form is not always a literal matrix inverse in reliable code. Include or exclude bias consistently in derivations.