A1 · Supervised Machine Learning in Depth

Gradient Descent for Linear Regression

Gradient descent is an iterative optimisation method that repeatedly moves the parameters a small step in the direction of the negative gradient of the loss. For mean squared error in linear regression, the update is w ← w − η·(2/n)·Xᵀ(Xw − y), where η is the learning rate. Mini-batch and stochastic variants use a subset of rows per step.

15 min Advanced Jump to the activity

What you need: The earlier topics of this module, and its prerequisites.

Definition

How does a model find the best weights when the formula is too expensive to compute?

Gradient descent is an iterative optimisation method that repeatedly moves the parameters a small step in the direction of the negative gradient of the loss. For mean squared error in linear regression, the update is w ← w − η·(2/n)·Xᵀ(Xw − y), where η is the learning rate. Mini-batch and stochastic variants use a subset of rows per step.

In simple words

Imagine standing on a foggy hillside, wanting the valley floor. Feel which way is downhill, take a step, and repeat. The gradient says which way is uphill; you go the opposite way. Too big a step and you overshoot and bounce around; too small and it takes forever.

Why it matters

The normal equation costs about p³ operations and needs all data in memory. Gradient descent scales to millions of rows and features, and the same idea trains logistic regression and every neural network.

Key terms

Cost function
A number measuring total error, such as mean squared error, that training minimises.
Gradient
The vector of partial derivatives showing how the cost changes with each weight.
Learning rate
The step size α in the update w ← w − α∇J(w).
Batch, stochastic and mini-batch
Using all rows, one row, or a small group of rows to compute each gradient step.
Convergence
When further steps no longer reduce the cost meaningfully.
Convexity
A bowl-shaped cost with a single minimum, which least squares has.

Explained in detail

Walking downhill on the cost surface

The normal equation solves linear regression in one step, but inverting XᵀX becomes slow and memory-hungry when there are millions of rows or many thousands of features. Gradient descent instead starts from any weights, computes the gradient of the mean squared error, and takes a small step in the opposite direction, repeating until the cost stops falling. For MSE with predictions ŷ = Xw, the gradient is (2/n)Xᵀ(ŷ − y): each weight moves in proportion to how much its feature correlates with the current errors. Because the least-squares cost is convex, a bowl with a single bottom, gradient descent with a suitable learning rate is guaranteed to approach the same answer as the normal equation.

Choosing the learning rate and batch size

SettingEffect
Learning rate too smallVery slow progress; may stop before reaching the minimum
Learning rate too largeOvershoots the minimum, oscillates or diverges to infinity
Batch gradient descentSmooth, exact steps but each step reads all data
Stochastic (one row)Very noisy steps but cheap; noise can help escape flat regions
Mini-batch (32 to 512 rows)The practical compromise used in deep learning

Feature scaling has a dramatic effect. If one feature ranges up to 100,000 and another up to 5, the cost bowl becomes a long, narrow valley, and gradient descent zigzags slowly across it; standardising the features makes the bowl rounder so steps point more directly at the minimum. Monitor the cost every epoch: it should fall steadily and level off. If it rises, lower the learning rate. Learning-rate schedules, momentum and adaptive optimisers such as Adam extend this basic idea and are covered later in the deep-learning modules, but they all rest on the same rule: move each weight a little against its gradient.

A worked step makes this concrete. Take one feature with x = [1, 2, 3], y = [2, 4, 6], starting weights w = 0 and b = 0, and learning rate 0.1. Predictions are all 0, errors are −2, −4 and −6, the gradient for w is (2/3)(1·−2 + 2·−4 + 3·−6) = −18.67 and for b is (2/3)(−12) = −8. The update gives w = 1.87 and b = 0.8, already much closer to the true w = 2 and b = 0. Repeating this a few hundred times converges to the exact answer, which is how every neural network is also trained, just with many more weights and a more complicated gradient.

How it works

  1. Start with w = 0.
  2. Compute predictions Xw and the error Xw − y.
  3. Compute the gradient (2/n)Xᵀ(Xw − y).
  4. Update w ← w − η × gradient.
  5. Repeat until the loss stops decreasing.

The maths

Mean squared error
Its gradient
The update rule
The learning rate: the step size

In code

Batch gradient descent from scratch, with three learning rates, compared with the exact least-squares answer. The largest rate overshoots and the loss explodes.

gradient_descent.py
import numpy as np

rng = np.random.default_rng(0)
n = 100
x = rng.uniform(-2, 2, n)
y = 3 * x + 2 + rng.normal(scale=0.3, size=n)
X = np.column_stack([np.ones(n), x])

def gradient_descent(lr, steps=300):
    w = np.zeros(2)
    for step in range(steps):
        gradient = 2 / n * X.T @ (X @ w - y)
        w -= lr * gradient
    return w, float(np.mean((X @ w - y) ** 2))

exact = np.linalg.lstsq(X, y, rcond=None)[0]
print("Exact least squares:", np.round(exact, 3))
for lr in [0.01, 0.1, 0.8]:
    w, loss = gradient_descent(lr)
    print(f"lr = {lr:<4} -> w = {np.round(w, 3)}, final MSE = {loss:.4g}")

w = np.zeros(2)
for step in range(1, 51):
    w -= 0.1 * 2 / n * X.T @ (X @ w - y)
    if step in (1, 5, 10, 50):
        print(f"step {step:>2}: loss {np.mean((X @ w - y) ** 2):.4f}")

Output

Exact least squares: [1.978 2.99 ]
lr = 0.01 -> w = [1.975 2.991], final MSE = 0.08461
lr = 0.1  -> w = [1.978 2.99 ], final MSE = 0.0846
lr = 0.8  -> w = [-1.74076932e+54 -5.15840624e+54], final MSE = 4.661e+109
step  1: loss 9.4811
step  5: loss 0.6169
step 10: loss 0.1071
step 50: loss 0.0846

Try it yourself

What does the learning rate do?

Match each learning-rate setting to its typical behaviour.

  • Very small (0.0001)
  • Well chosen (0.1 on scaled data)
  • Too large
  • Decaying over time

Common mistakes

  • Forgetting to scale features, so convergence is painfully slow.
  • Using one learning rate without checking the loss curve.
  • Updating weights one at a time with stale values instead of all together.

Check yourself

Question 1

1. Which way does gradient descent move the weights?

Question 2

2. If the loss grows every step, the learning rate is probably…

Question 3

3. Why use gradient descent instead of the normal equation?

Summary

  • Gradient descent steps against the gradient: w ← w − η∇J.
  • For MSE, ∇J = (2/n)Xᵀ(Xw − y).
  • Scale features and tune the learning rate by watching the loss.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Goodfellow et al., Deep Learning, chapter 4 · James et al., An Introduction to Statistical Learning