Sam Austinon November 13, 202611 min read

Normal Equation vs Gradient Descent for Linear Regression: When Each Wins

Normal Equation vs Gradient Descent for Linear Regression: When Each Wins
Contents

Figure 1: Normal Equation vs Gradient Descent for Linear Regression: When Each Wins — one step to the answer, or a thousand small ones, and the cost of each route is knowable in advance

You can solve linear regression two ways, and textbooks love to make you pick a side. One gives the answer in a single line of linear algebra. The other creeps toward it step by step.

The choice is not a matter of taste. It is a cost comparison you can write down, plus a numerical-stability argument that most tutorials skip entirely.

The Short Answer

  • Normal equation — modest feature count, data fits in memory, want the answer now.
  • Gradient descent — many features, streaming data, or a model with no closed form.
  • In practice — call the library and let it pick a stable solver. LinearRegression already does.

The interesting part is why the boundary sits where it does, and it is not the boundary most courses teach.

What the Normal Equation Is Actually Doing

Start from the loss and differentiate. For L(β) = ‖y − Xβ‖², the gradient is:

∇L = −2Xᵀ(y − Xβ)

Set it to zero:

XᵀXβ = Xᵀy

and solve:

β = (XᵀX)⁻¹Xᵀy

That is the whole derivation. The normal equation is not a trick or a shortcut — it is the first-order condition of a convex quadratic, solved in closed form. "Normal" here is the old geometric sense: perpendicular, because the residual y − Xβ is orthogonal to every column of X.

This only works because the problem is quadratic. The moment the model becomes logistic regression or a neural network, the gradient is no longer linear in the parameters, and there is nothing to isolate.

Why You Should Not Actually Invert It

The formula says (XᵀX)⁻¹. The code should not.

Forming XᵀX squares the condition number. For the design matrix X, the condition number of XᵀX is the square of the condition number of X:

κ(XᵀX) = κ(X)²

In float64 you have about 16 significant digits. If κ(X) = 10³ — which is ordinary for correlated features — then κ(XᵀX) = 10⁶, and you lose roughly six digits before you have done anything. If κ(X) = 10⁶, the squared version is 10¹² and the answer is noise.

An explicit inverse makes it worse, because computing A⁻¹ and then multiplying is a second error-prone operation. np.linalg.solve(A, b) is strictly better than inv(A) @ b — same mathematics, better numerics, and it does not build a matrix you do not need.

The real fix is to avoid forming XᵀX at all. QR and SVD factorisations work on X directly, so they only ever see κ(X), not its square. That is what every serious least-squares routine does [4].

What It Costs

Two terms, and they behave differently:

O(nd²) to form XᵀX, plus O(d³) to factorise or invert it.

The cubic term is the one that bites. Double the feature count and the factorisation cost goes up by about eight times.

But the constraint that usually hits first is memory, not time. XᵀX is a d × d matrix:

Features d Size of XᵀX in float64
1,000 8 MB
10,000 800 MB
100,000 80 GB

At a hundred thousand features the normal equation does not fail because it is slow. It fails because the matrix does not fit. That is the wall, and it arrives before the d³ cost does.

Gradient Descent: The Other Route

Guess the coefficients, measure the error, step downhill. For the same squared loss:

θ ← θ − α · (2/n) Xᵀ(Xθ − y)

Each full-batch step costs O(nd), because you multiply the n × d matrix by a vector twice. Run k steps and the total is O(knd).

With mini-batches of size B, each step costs O(Bd), which is what makes it viable when n is enormous.

One property is worth stating plainly, because the draft version of this argument usually gets it wrong: for linear regression the loss is convex. There are no local minima to get stuck in, no saddle points to escape. Gradient descent either converges to the global least-squares solution, diverges because the step size is too large, or stops early because you did not run enough iterations. Those are the only three outcomes.

The Real Crossover

Put the two costs side by side:

  • Normal equation: nd² + d³
  • Gradient descent: knd

Divide both by nd and the comparison becomes d + d²/n against k. So the normal equation is cheaper when the number of iterations you would need exceeds roughly the feature count — and gradient descent is cheaper when k is small relative to d.

That is the honest version of the rule of thumb. The familiar advice — "use gradient descent past about 10,000 features" — comes from Andrew Ng's classic course, and it was good advice for the regime it described: n large, d in the thousands, and d³ genuinely dominant. It is not a law, and the memory term above often moves the boundary by an order of magnitude.

Conditioning moves it too, in the opposite direction. Gradient descent's iteration count scales with κ, so a badly conditioned problem can need k ≫ d and lose on cost as well as accuracy.

The Failure Modes Are Different

This is where the comparison actually matters, because the two methods break in different ways.

Singular XᵀX

Exact collinearity — one column a linear combination of the others — makes XᵀX singular. So does d > n, because the rank cannot exceed n.

Gradient descent does not rescue this. A singular matrix means the least-squares problem has infinitely many minimisers, and gradient descent will converge slowly toward whichever one its starting point points at. You have not removed the degeneracy; you have hidden it.

The real fixes:

  1. A pseudo-inverse or SVD, which returns the minimum-norm solution.
  2. Ridge, which makes the matrix positive definite.
  3. Drop the collinear columns, which is usually what you should have done anyway.

Note the distinction the textbooks blur: exact collinearity makes the matrix singular, while near collinearity makes it ill-conditioned. The second is far more common, and it does not produce an error — it produces enormous, unstable coefficients that look like real answers.

Bad step size

Gradient descent diverges if α exceeds 2/L, where L is the largest eigenvalue of the Hessian — for this problem, 2λ_max(XᵀX)/n. The normal equation has no equivalent failure, which is a genuine advantage: there is no knob to get wrong.

Lost precision

The normal equation loses digits to κ²; gradient descent loses them to accumulated iteration error. Neither is exact in floating point. The normal equation is exact in real arithmetic and merely well-conditioned in practice — those are different claims.

What scikit-learn Actually Does

LinearRegression does not compute (XᵀX)⁻¹Xᵀy. It calls scipy.linalg.lstsq, which defaults to the LAPACK gelsd driver — a divide-and-conquer SVD solver [1][2].

That choice explains a behaviour people find surprising. Fit a model on perfectly collinear columns and LinearRegression does not raise; it returns coefficients. SVD handles rank deficiency by giving you the minimum-norm solution, which is a defensible answer where a naive inverse would fail outright.

There is no solver argument on LinearRegression. It is always the direct SVD route. If you want the iterative route, that is a different class: SGDRegressor, which is stochastic, approximate, and — importantly — needs scaled features and tuned hyperparameters [5].

So the library has already made the choice for you, and it made the numerically better one. The comparison in this article is about knowing when to override it.

Regularization Changes the Closed Form

Ridge keeps a closed form:

β = (XᵀX + λI)⁻¹Xᵀy

And this is stronger than "usually makes it invertible". For any λ > 0, the matrix XᵀX + λI is positive definite, hence invertible, full stop — even when XᵀX is singular and even when d > n. The singularity problem does not get easier with ridge; it disappears [3].

Lasso does not keep a closed form. The absolute value makes the first-order condition non-linear, so libraries use coordinate descent. Elastic net is the same story.

So "closed form versus iterative" is not a property of linear regression. It is a property of the penalty, and it changes the moment you add one.

See Both in Code

import numpy as np

rng = np.random.default_rng(0)
X = rng.normal(size=(1000, 3))
y = X @ np.array([2.0, -1.0, 0.5]) + 3 + rng.normal(0, 0.1, 1000)

Xb = np.c_[np.ones(len(X)), X]          # bias column

# Normal equation: solve, never invert
theta_ne = np.linalg.solve(Xb.T @ Xb, Xb.T @ y)

# The numerically better direct route
theta_lstsq, *_ = np.linalg.lstsq(Xb, y, rcond=None)

# Gradient descent on the mean squared error
theta = np.zeros(Xb.shape[1])
lr = 0.1
for _ in range(2000):
    grad = (2 / len(y)) * Xb.T @ (Xb @ theta - y)
    theta -= lr * grad

print("solve  ", theta_ne)
print("lstsq  ", theta_lstsq)
print("gd     ", theta)
print("kappa  ", np.linalg.cond(Xb))

Three things to notice.

First, solve and lstsq agree to about machine precision on this well-conditioned problem. That is the expected result, and it is the check you should run before trusting either.

Second, gradient descent lands close but not identical — it is an approximation, and the gap depends on the step count and lr, not on the mathematics.

Third, the kappa line is the one that tells you whether to trust any of it. A condition number near 1 means both routes are safe. A condition number of 10⁸ means the solve route has thrown away most of its digits, and lstsq is the honest option.

When to Pick Each

  • A few thousand features, data in memory — use the library's direct solver. It is the normal equation with better numerics.
  • Tens of thousands of features, or data that does not fit — gradient descent or a stochastic variant, and scale your features.
  • Streaming data — online or mini-batch updates. There is no closed form for data you have not seen yet.
  • Collinear columns — ridge plus a direct solver. Do not reach for gradient descent.
  • Teaching or debugging — implement both. The comparison is the lesson.
  • Anything past linear regression — learn gradient descent properly, because you will use it for the rest of your career.

And a warning about the checklist itself: it is a prior, not a measurement. If the run takes ten seconds either way, try both and compare the coefficients. The condition number will tell you which answer to believe.

Common Pitfalls

  • Writing inv(X.T @ X) @ X.T @ y. It is slower and less accurate than solve, and much less accurate than lstsq.
  • Assuming "exact" means exact in floating point. It means exact in real arithmetic; the computed answer loses digits at a rate set by κ².
  • Using gradient descent to fix a singular matrix. It does not. Use SVD, ridge, or drop the columns.
  • Forgetting the bias column. Without a column of ones there is no intercept, and the model is quietly wrong.
  • Not scaling features before gradient descent. The exact solution is scale-invariant; the iterative one is not.
  • Setting lr by guesswork. Try a log-spaced grid and watch the loss; the stable range is bounded by 2/L.
  • Blaming the solver for unstable coefficients. That is collinearity, and no solver fixes it.
  • Confusing LinearRegression with SGDRegressor. Different algorithms, different assumptions, different failure modes.

Best Book to Read

CoverBookDescriptionGet it
Cover of “Linear Algebra and Learning from Data” Linear Algebra and Learning from Databy Gilbert Strang least squares, the normal equations, QR, and SVD built from the ground up, with the numerical reasoning that this article only sketches. View on Amazon

As an Amazon Associate I earn from qualifying purchases. Links on this page are affiliate links, and I may earn a commission at no extra cost to you.

Read the least-squares and QR chapters together. Strang is unusually good at showing why the factorisation matters and not just how to compute it, which is exactly the gap between the textbook formula and production code. His MIT lectures cover the same material for free.

Wrapping Up

The normal equation is the first-order condition of a convex quadratic, solved exactly. It costs nd² + d³, needs d² memory, and loses precision at a rate of κ².

Gradient descent is the same condition approached iteratively. It costs knd, needs O(d) memory, and loses precision to iteration count instead.

The crossover is not "10,000 features". It is k versus d, adjusted for memory and conditioning — and in practice the memory term usually decides first.

Most of the time you should not choose at all. LinearRegression already routes to an SVD solver, which is the right answer for almost every dataset that fits in memory. The knowledge is for the cases where it does not fit, or where the coefficients come back strange.

If you want the model itself built from scratch, linear regression from scratch to scikit-learn walks through that. For the optimizer side of the iterative route, gradient descent from derivative to update rule has the full derivation, and ridge vs lasso covers what happens when you add the penalty.

Now go fit something and print the condition number.

Frequently Asked Questions

Is the normal equation always better than gradient descent?

No. It is faster when the feature count is modest, but it needs the whole dataset in memory, forms a d × d matrix that grows quadratically in memory, and loses numerical precision when the columns are correlated. Gradient descent wins when the feature count is large or the data arrives in batches.

Why should I use solve instead of inverting X transpose X?

Because forming XᵀX squares the condition number of the design matrix, and an explicit inverse adds another error-prone step. Solving the system directly, or better, using a QR or SVD decomposition, keeps more of the available floating-point precision. In float64 you have about 16 digits, and squaring a condition number of a thousand costs you half of them.

Does gradient descent work when X transpose X is singular?

Not well. A singular matrix means the least-squares problem has infinitely many solutions, and gradient descent will converge slowly toward one of them depending on where it started. The right fixes are a pseudo-inverse, ridge regularization, or dropping the collinear columns.

What does scikit-learn's LinearRegression actually use?

It calls scipy.linalg.lstsq, which defaults to the LAPACK gelsd driver, a divide-and-conquer SVD solver. It never forms an explicit inverse. That is why LinearRegression still returns sensible coefficients when the design matrix is rank deficient, giving the minimum-norm solution.

Why does gradient descent need feature scaling but the normal equation does not?

The exact least-squares solution is invariant to rescaling a feature, so the normal equation returns the same coefficients either way. Gradient descent is not invariant: unscaled features make the loss surface a long narrow valley, and the step size that is stable along the steep axis crawls along the flat one.

Sources

  • [1] scikit-learn, LinearRegression — the implementation notes and the call into scipy.linalg.lstsq: scikit-learn.org
  • [2] SciPy, scipy.linalg.lstsq — the gelsd, gelsy, and gelss drivers and their numerical properties: docs.scipy.org
  • [3] Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning — chapter 3 derives least squares, the normal equations, and ridge from the same first-order condition: hastie.su.domains/ElemStatLearn
  • [4] Strang, Linear Algebra and Learning from Data — least squares, QR, and SVD with the numerical reasoning behind each factorisation: math.mit.edu/~gs/learningfromdata
  • [5] scikit-learn, SGDRegressor — the stochastic route, its hyperparameters, and the feature-scaling requirement: scikit-learn.org

What are You Looking For?

esc