Skip to content
learn
  1. Learn
  2. Machine Learning
  3. Regression

Machine Learning ML-03.02

Solving linear regression: normal equation and gradient descent

Solve linear regression exactly with the normal equation, derive the gradient of MSE, and see why big problems use gradient descent instead.

Intermediate 15 min Last reviewed

The big idea

In the last lesson you dragged a line until the error was as small as possible. A computer needs a recipe. For linear regression there are two, and they arrive at exactly the same answer by very different routes.

The first is like solving for the lowest point of a valley with a formula: write down where the slope is zero, solve the equation, done. That is the normal equationA formula that computes the least squares weights of linear regression in one step: w = (X^T X)^-1 X^T y.. The second is like walking down the valley in the fog, one step at a time, always heading downhill: that is gradient descentAn optimisation method that repeatedly moves the parameters a small step in the direction that reduces the loss fastest, the negative gradient.. The formula is perfect for small problems. The walk works for problems of any size and for almost every other model, which is why it is the engine of modern ML.

How it works

Two routes to the same weights Training data X and y feed two routes. The top route, the normal equation, does one large matrix solve whose cost grows with the cube of the number of features. The bottom route, gradient descent, takes many cheap steps, each costing about the number of examples times the number of features. Both arrive at the same weights. one jump step, step, step data X (n x d), y normal equation one solve, cost grows like d^3 gradient descent many steps, each about n x d same weights w = (264, 45, -40) Figure 1. The normal equation reaches the weights in one expensive jump; gradient descent reaches the same weights in many cheap steps. For linear regression the destination is identical.

Step 1: Write the problem in matrix form

Stack the training examples as rows of a matrix (one column per feature) and put the targets in a vector . To fold the bias into the weights, add a column of 1s to ; its weight is the bias. Then all predictions at once are , and the loss is

Step 2: Derive the gradient of MSE

Take one weight . Each squared error has derivative by the chain rule: the outer square gives (error), the inner prediction changes by per unit of . Average over examples, and do it for every weight at once:

Read it in words: take the error on each example, weight it by that example's feature values, and average. Features that are large on examples with big errors get big gradients. The code below checks this formula against a brute-force numerical estimate; they agree to every printed digit.

Step 3: The normal equation: set the gradient to zero

At the bottom of a bowl the slope is zero in every direction. Set :

Because MSE for a linear model is a convex bowl ( Optimization basics ), this single point is the global minimum. One matrix solve and you are done, with no learning rate to tune. In practice you never form the inverse explicitly: you call a solver such as np.linalg.solve or np.linalg.lstsq, which is faster and more numerically stable.

Step 4: Gradient descent: walk downhill instead

Start with any weights, often all zeros, and repeat:

where is the learning rate. Each step costs one pass of matrix-vector products over the data, roughly operations. On the house data (size and age, standardised), the MSE reaches its minimum of 432.8 within 50 steps, and by step 300 the weights match the exact answer to every printed digit:

solve.pyruns with python3 + numpy
import numpy as np

size = np.array([109, 102, 112, 63, 106, 70, 116, 42, 67, 139, 125, 139, 62, 128.0])
age = np.array([12, 30, 5, 40, 35, 22, 8, 50, 45, 3, 18, 25, 33, 10.0])
y = np.array([305, 233, 338, 190, 214, 205, 318, 146, 145, 415, 305, 340, 186, 358.0])

# Standardise features, then add a column of 1s so the bias is just another weight
F = np.column_stack([size, age])
F = (F - F.mean(axis=0)) / F.std(axis=0)
X = np.column_stack([np.ones(len(y)), F])            # shape (14, 3)

# 1. Normal equation: solve (X^T X) w = X^T y in one step
w_exact = np.linalg.solve(X.T @ X, X.T @ y)
print("normal equation  w =", w_exact.round(3))

# 2. Gradient descent on MSE: gradient = (2/n) X^T (Xw - y)
def grad(w):
    return 2 / len(y) * X.T @ (X @ w - y)

w = np.zeros(3)
for step in range(1, 301):
    w -= 0.1 * grad(w)
    if step in (1, 10, 50, 300):
        print(f"GD step {step:>3}      w = {w.round(3)}   MSE {np.mean((X @ w - y) ** 2):8.1f}")

# 3. Check the calculus: compare the formula with a finite-difference estimate
eps, w0 = 1e-5, np.array([1.0, -2.0, 0.5])
mse = lambda w: np.mean((X @ w - y) ** 2)
numeric = [(mse(w0 + eps * e) - mse(w0 - eps * e)) / (2 * eps) for e in np.eye(3)]
print("formula gradient ", grad(w0).round(3))
print("numeric gradient ", np.round(numeric, 3))

Output

normal equation  w = [264.143  44.551 -40.361]
GD step   1      w = [ 52.829  15.179 -14.992]   MSE  47750.1
GD step  10      w = [235.781  42.698 -41.161]   MSE   1238.9
GD step  50      w = [264.139  44.338 -40.574]   MSE    432.8
GD step 300      w = [264.143  44.551 -40.361]   MSE    432.8
formula gradient  [-526.286 -156.571  154.029]
numeric gradient  [-526.286 -156.571  154.029]

Step 5: Why not always use the formula?

  • Cost with many features. Solving with , a matrix, costs on the order of . With 100 features that is trivial; with 100,000 features (for example word counts in text) it is about operations, plus storing a matrix of numbers.
  • Data that does not fit in memory. Gradient descent can process the data in mini-batches, streaming from disk, and can keep learning as new data arrives.
  • Other models have no formula. Logistic regression, neural networks and most other models have no closed-form solution. Gradient descent works for all of them, which is why the next lesson treats it as the engine of ML.
  • Ill-conditioning. When features are nearly duplicates, is close to singular and the exact solution becomes unstable. Regularization ( Regularization: ridge, lasso, elastic net ) fixes this for both methods.

Going deeper

What scikit-learn does. LinearRegression uses a least squares solver based on matrix decompositions, not gradient descent; SGDRegressor uses stochastic gradient descent and is meant for very large datasets.

Scaling matters for one route only. The normal equation gives the same predictions whether or not you scale features. Gradient descent is very sensitive to scaling: unscaled features stretch the loss bowl into a narrow ravine and one learning rate cannot suit every direction. That is why the code standardises size and age first.

Geometric view. can only reach predictions that are combinations of the columns of . Least squares picks the combination closest to , which is the projection of onto that space, and the normal equation says the residual vector is perpendicular to every column of .

Trade-offs

OptionWins whenLoses when
Normal equation (direct solver) Up to a few thousand features, data fits in memory, you want the exact answer with no tuning Very many features, streaming data, or nearly duplicate features without regularization
Batch gradient descent Moderate data, you want smooth and predictable convergence Huge datasets, where each step touches every row
Mini-batch or stochastic gradient descent Huge or streaming data, and any model without a formula You need the exact optimum quickly on a small problem

Common mistakes

  • Computing inv(X.T @ X) @ X.T @ y literally instead of using a solver.
  • Forgetting the column of 1s, which forces the line through the origin.
  • Running gradient descent on unscaled features and concluding it "does not converge".
  • Getting the sign wrong in the update, which climbs uphill and makes the loss grow.
  • Assuming gradient descent found a different, worse answer: for linear regression, if it has converged, it found the same minimum.

In the wild

Statistical software computes ordinary least squares with matrix decompositions such as QR, the numerically careful version of the normal equation. Large-scale systems that fit linear models on billions of rows, such as ad click prediction, use stochastic gradient methods instead because the data never fits in memory at once. The gradient formula derived here, error times input averaged over a batch, is the same one backpropagation computes for the last layer of every neural network ( Backpropagation ).

Check yourself

  1. What does the normal equation do?

    Show answer

    B. Sets the gradient of MSE to zero and solves for the weights in one step At the minimum the gradient is zero. Solving X^T X w = X^T y gives that point directly.

  2. The gradient of MSE is (2/n) X^T (Xw - y). Which part is the vector of errors?

    Show answer

    B. Xw - y Xw are the predictions, so Xw - y is the error on each example. X^T then weights each error by the features.

  3. You have 2 million features (sparse text counts). Which method should you use?

    Show answer

    B. Gradient descent (stochastic or mini-batch) The normal equation needs a 2 million by 2 million matrix and cubic work. Gradient descent only ever needs matrix-vector products.

  4. Gradient descent and the normal equation give slightly different weights after 10 steps. What is the likely reason?

    Show answer

    A. Gradient descent has not converged yet MSE for linear regression is convex with one minimum. Run more steps and gradient descent reaches the same weights, as in the code at step 300.

Recap

  • In matrix form, predictions are Xw and the MSE gradient is (2/n) X^T (Xw - y).
  • Setting the gradient to zero gives the normal equation, X^T X w = X^T y, solved in one step.
  • Gradient descent reaches the same weights for linear regression by repeated small steps.
  • The direct solve scales badly with many features and has no equivalent for most models.
  • Use a solver, not an explicit inverse, and scale features before gradient descent.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up