# 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

| Type | Gradient Computation | Speed | Noise | Use Case |
| --- | --- | --- | --- | --- |
| **Batch GD** | Uses all \( n \) samples | Slow | None | Exact OLS equivalent |
| **Stochastic GD (SGD)** | One sample per step | Fast | High | Online learning, large data |
| **Mini-Batch GD** | Subsets of data | Balanced | Moderate | Neural networks, scalable regression |

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

| Perspective | Key Equation | Essence |
| --- | --- | --- |
| **Analytic (Closed Form)** | \( \hat{\beta} = (X'X)^{-1} X'y \) | Instant projection |
| **Iterative (Gradient Descent)** | \( \beta_{t+1} = \beta_t - \frac{\eta}{n} X'(X\beta_t - y) \) | Incremental projection |
| **Condition at Optimum** | \( X'(y - X\hat{\beta}) = 0 \) | Residuals orthogonal to regressors |

**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) \]