The Math of Gradient Descent in Ordinary Least Squares

From Calculus to Convergence — How Optimization Finds the Line of Best Fit

Technology: Quantitative Analysis
Skill: Linear Algebra, Optimization

0. Overview

While Ordinary Least Squares (OLS) can be solved analytically as the
[ \hat{\beta} = (X'X)^{-1}X'y ]
it can also be understood through the iterative process of gradient descent.

This approach generalizes far beyond linear regression — it’s the foundation of modern machine learning, from neural networks to large language models.

Here, we connect the dots between OLS, calculus, and the algorithmic idea of walking downhill on an error surface.

1. The Model and Objective

We start with the linear model:

[ y = X\beta + \varepsilon ]

Our goal is to minimize the Mean Squared Error (MSE) loss:

[ J(\beta) = \frac{1}{2n} (y - X\beta)'(y - X\beta) ]

The factor ( \frac{1}{2n} ) simplifies derivatives — it doesn’t change the location of the minimum.

2. The Gradient

Take the derivative of ( J(\beta) ) with respect to ( \beta ):

[ \nabla_\beta J(\beta) = -\frac{1}{n} X'(y - X\beta) ]

or equivalently:

[ \nabla_\beta J(\beta) = \frac{1}{n} X'(X\beta - y) ]

This gradient points in the direction of steepest ascent — to minimize the loss, we move in the opposite direction.

3. The Update Rule

Gradient descent updates parameters iteratively:

[ \beta^{(t+1)} = \beta^{(t)} - \eta , \nabla_\beta J(\beta^{(t)}) ]

where:

• ( \eta ) is the learning rate (step size)
• ( \nabla_\beta J(\beta^{(t)}) ) is the gradient at iteration ( t )

Substituting the gradient expression:

[ \beta^{(t+1)} = \beta^{(t)} - \frac{\eta}{n} X'(X\beta^{(t)} - y) ]

This is the iterative equivalent of the closed-form OLS solution.

4. Intuition: Descending the Error Surface

The MSE surface for linear regression is a convex paraboloid.

It has one unique minimum — no local traps.

Each step of gradient descent moves ( \beta ) downhill toward that minimum:

1. Compute the gradient vector.
2. Step opposite to it (scaled by ( \eta )).
3. Repeat until convergence.

If ( \eta ) is:

• too small → convergence is slow
• too large → the algorithm overshoots and may diverge

5. Convergence to the OLS Solution

At the minimum, the gradient equals zero:

[ \nabla_\beta J(\beta^) = 0 \Rightarrow X'(X\beta^ - y) = 0 ]

This is exactly the normal equation of OLS:

[ X'X\beta^* = X'y ]

Thus, gradient descent converges to the same solution as the analytical formula — just by repeated local updates rather than direct matrix inversion.

6. Variants: Batch, Stochastic, and Mini-Batch Descent

Batch GD yields the exact OLS trajectory, while SGD introduces randomness that can help escape flat regions in more complex (non-convex) models.

7. Learning Rate and Convergence

In OLS, the learning rate ( \eta ) must satisfy:

[ 0 < \eta < \frac{2}{\lambda_{\max}(X'X / n)} ]

where ( \lambda_{\max} ) is the largest eigenvalue of ( (X'X / n) ).

Intuitively:

• The steeper the curvature (larger ( \lambda_{\max} ))

the smaller your learning rate must be for stable descent.

8. Geometric View: Gradient Descent as Projection

Each step of gradient descent can be seen as partial projection toward the subspace spanned by ( X ).

• The full projection (analytical OLS) jumps directly to the foot of the perpendicular.
• Gradient descent walks there gradually — taking one vector-space correction at a time:

[ \Delta \beta = -\eta X'(X\beta - y) ]

As ( \eta \to 0 ) and ( t \to \infty ), these incremental corrections perfectly align with the OLS projection.

9. Computational Perspective

For large datasets, matrix inversion ( (X'X)^{-1} ) is expensive — ( O(p^3) ) complexity.

Gradient descent, on the other hand, only needs matrix-vector multiplications per iteration — ( O(np) ).

That’s why OLS in practice (especially with millions of features) is often solved numerically via gradient-based methods rather than algebraically.

10. TL;DR

Inertia7 Insight:

Gradient descent transforms a static formula into a dynamic process — one that doesn’t just solve OLS but animates it.

Each update step embodies calculus, geometry, and computation in motion:
the slope of the error surface guiding the coefficients toward perfect orthogonality.

[ \beta^{(t+1)} = \beta^{(t)} - \frac{\eta}{n} X'(X\beta^{(t)} - y) ]