Fitting: gradients and the normal equation

Linear regressionabout 10 minutes

Put the features in a design matrix $X$ of shape $(n, d)$ and fold the bias in by adding a column of ones, so a single weight vector $w$ of length $d + 1$ does everything. Then all predictions are $X w$ and the loss is a squared vector length:

L (w) = \frac{1}{n} ∥ X w - y ∥^{2}

The gradient in matrix form

Applying the chain rule to every residual at once gives a compact gradient. Check the shapes: $X^{⊤}$ is $(d, n)$ and the residual vector is $(n)$ , so the result is $(d)$ , one number per weight.

\nabla_{w} L = \frac{2}{n} X^{⊤} (X w - y)

Read it as: each weight's gradient is the correlation between its feature column and the residuals. If a feature is high exactly where the model under-predicts, its weight should go up.

Route 1: solve it exactly

The loss is a bowl (convex), so its minimum is where the gradient is zero. Setting $X^{⊤} (X w - y) = 0$ and solving gives the normal equation:

X^{⊤} X w = X^{⊤} y ⟹ w^{*} = (X^{⊤} X)^{- 1} X^{⊤} y

It is exact and needs no learning rate.
Solving a $(d \times d)$ system costs about $O (d^{3})$ , fine for hundreds or a few thousand features, painful for millions.
It needs $X^{⊤} X$ to be invertible. If two features are perfectly correlated (say, height in cm and height in inches) it isn't, and even nearly-correlated features make the solution numerically unstable. Regularisation (module 3) fixes this.
In code, never form the inverse explicitly: use np.linalg.solve(X.T @ X, X.T @ y) or, better, np.linalg.lstsq(X, y), which is more stable.

Route 2: gradient descent, in batches

Gradient descent scales to any size and is the only option for models with no closed-form solution, which is nearly all of them. Computing the gradient over all $n$ examples every step (batch gradient descent) is wasteful when $n$ is in the millions: the average over a random sample of 32 to 1,024 examples points in nearly the same direction at a tiny fraction of the cost.

variant	examples per step	character
batch GD	all $n$	smooth, exact gradient, slow per step
stochastic GD	1	very noisy, cheap, rarely used alone
mini-batch SGD	32 to 1,024	the standard: cheap, parallel on GPUs, mildly noisy

Full-batch gradient descent walks smoothly downhill. Mini-batch SGD jitters, because each step sees a different sample, but gets close for a fraction of the computation.

One pass through the whole training set is called an epoch. The noise of mini-batches isn't only a cost: it helps neural networks escape saddle points and is thought to bias them toward solutions that generalise better.

try itedit the code and run it, nothing can break

python sleeps until you press run

The gradient of the squared error is $\frac{2}{n} X^{⊤} (X w - y)$ . Set it to zero for the exact answer when features are few; follow it in mini-batches when data or models are big.

← The linear model