Gradient Descent

A gradient tells you which way is uphill. Gradient descent takes a small step the other way, over and over. After this lesson your program fits a line to data by repeated steps, with a learning rate and a batch size you control.

The update rule

For every parameter p with gradient g and learning rate lr:

p  <-  p - lr * g

The gradient says how fast the loss grows as p grows. Subtract it, scaled by lr, and the loss drops, provided the step is small enough that the slope has not changed under your feet. One such step for every parameter at once is one update.

The learning rate decides everything

Minimise f(w) = (w - 3)^2, whose gradient is 2*(w - 3), starting from w = 0. Each update shrinks the distance to the minimum by the factor 1 - 2*lr:

Real losses are not parabolas, but the lesson carries over: too small wastes time, too big overshoots, and the right value depends on how steeply the loss curves. When a loss goes up or turns to nan, suspect the learning rate first.

How much data per update

The gradient of a dataset's loss is the average of the per-example gradients. You choose how many examples to average before each update.

• Full batch: all N examples per update. Smooth and stable, but one update per pass over the data.
• Stochastic (batch size 1): one example per update. Many cheap, noisy updates.
• Mini-batch: B examples (commonly 32 to 256) per update. The noise shrinks roughly like 1/sqrt(B) and the hardware stays busy. This is the default.

One pass over all the data is an epoch. With N = 10 and B = 4, an epoch makes three updates, on examples 1-4, 5-8 and 9-10. The last batch is smaller; its average must divide by its own size, 2.

Fitting a line

Model prediction = w*x + b with loss mean((prediction - y)^2). For a batch of m examples, with err_i = w*x_i + b - y_i, both gradients are averages:

dL/dw = 2 * sum(err_i * x_i) / m
dL/db = 2 * sum(err_i)       / m

Both are computed from the current w and b, and only then are both updated. Start from w = 0, b = 0.

Common mistakes

• Dividing by the full batch size for the final, shorter batch.
• Updating w and then computing the bias gradient from the new w.
• Resetting w and b at the start of each epoch, so only the last epoch counts.
• Forgetting the x_i factor in the weight gradient.
• Summing instead of averaging, which makes the effective learning rate grow with the batch size.

Your exercise

The input gives LR, EPOCHS, BATCH and the DATA points. The starter parses them, calls your train and prints the final w, b and the mean squared error over all data. Implement train, visiting the data in the given order.