Gradient Descent

The OLS closed form gives you the exact answer in one shot — but only for linear regression with MSE. The moment you change the loss function or the model, there's no algebraic shortcut. Gradient descent is the algorithm that works everywhere: logistic regression, neural networks, XGBoost internals. Understanding it on linear regression — where you can verify the result against OLS — is the right place to build the intuition.

The Gradient of MSE

$J(w_0,w_1)=\frac{1}{n}{\sum }_{i=1}^n(y_i-w_0-w_1{x}_i{)}^2$

The gradient is the vector of partial derivatives:

$\frac{\partial J}{\partial w_0}=-\frac{2}{n}{\sum }_{i=1}^n(y_i-w_0-w_1{x}_i)=-\frac{2}{n}\sum {\epsilon }_i$

$\frac{\partial J}{\partial w_1}=-\frac{2}{n}{\sum }_{i=1}^n{x}_i(y_i-w_0-w_1{x}_i)=-\frac{2}{n}\sum x_i{\epsilon }_i$

The gradient points in the direction of steepest ascent. We subtract it to go downhill:

$w\leftarrow w-\alpha \cdot \nabla J(w)$

where $\alpha$ is the learning rate — how big a step we take each iteration.

Anchor dataset: $X=[650,850,1100,1400,1600,1900]$, $y=[180,220,280,340,370,430]$.

Gradient Descent on Unscaled Data — The Scaling Problem

Start with $w_0=0$, $w_1=0$, $\alpha =0.0001$:

Iteration 1:

• Predictions: $\hat{y}=[0,0,0,0,0,0]$
• Residuals: $\epsilon =[180,220,280,340,370,430]$
• $\partial J/\partial w_0=-(2/6)(180+220+280+340+370+430)=-(2/6)(1820)=-606.67$
• $\partial J/\partial w_1=-(2/6)(650\times 180+850\times 220+1100\times 280+1400\times 340+1600\times 370+1900\times 430)$ $=-(2/6)(117000+187000+308000+476000+592000+817000)=-(2/6)(2497000)=-832333$
• Update: $w_1=0-0.0001\times (-832333)=83.23$ ← already exploding

$\alpha =0.0001$ is too large for unscaled data. The scale of $x$ (650–1900) makes the $w_1$ gradient orders of magnitude larger than the $w_0$ gradient. This is why feature scaling is not optional — it's structurally required for gradient descent to work efficiently.

Feature Scaling Before Gradient Descent

from sklearn.preprocessing import StandardScaler
import numpy as np

X_raw = np.array([650, 850, 1100, 1400, 1600, 1900]).reshape(-1, 1)
y_raw = np.array([180, 220, 280, 340, 370, 430]).reshape(-1, 1)

scaler_X = StandardScaler()
scaler_y = StandardScaler()

X_scaled = scaler_X.fit_transform(X_raw).flatten()
y_scaled = scaler_y.fit_transform(y_raw).flatten()

print("X_scaled:", X_scaled.round(3))
print("y_scaled:", y_scaled.round(3))

After scaling, both $X$ and $y$ have mean 0 and standard deviation 1. The gradients are balanced, and $\alpha =0.1$ works smoothly.

Manual Gradient Descent on Scaled Data — 4 Iterations

Start: $w_0=0.0$, $w_1=0.0$, $\alpha =0.1$:

$w_0$ stays at 0 because ${\bar{y}}_{\text{scaled}}\approx 0$ — the scaled target is already centered. $w_1$ converges toward 1.0 in scaled space, which corresponds to $w_1=0.20$ in original space (after unscaling).

The Three Variants of Gradient Descent

For our 6-sample anchor, all three give the same final weights — the difference matters at $n=1,000,000$ where batch GD requires computing gradients over all 1M samples each step.

SGD Step Trace — 1 Sample

On the same unscaled anchor, $\alpha =0.0001$, randomly pick sample 3 ($x=1100$, $y=280$):

With initial $w_0=0$, $w_1=0$: $\hat{y}=0$, $\epsilon =280$

$\frac{\partial J_{\text{SGD}}}{\partial w_0}=-2\times 280=-560$

$\frac{\partial J_{\text{SGD}}}{\partial w_1}=-2\times 1100\times 280=-616000$

$w_0\leftarrow 0+0.0001\times 560=0.056,w_1\leftarrow 0+0.0001\times 616000=61.6$

One sample gives a noisier gradient than the full batch — but costs $1/6$ the computation. The noise averages out over many iterations.

Learning Rate Sensitivity

• $\alpha$ too small: the curve barely moves over 200 iterations — slow but stable.
• $\alpha$ right: rapid descent, converges cleanly around 50–100 iterations.
• $\alpha$ too large: MSE oscillates up and down, potentially diverging — the step overshoots the minimum.

Code Implementation

def gradient_descent(X, y, alpha=0.1, n_iter=200):
    n = len(y)
    w0, w1 = 0.0, 0.0
    history = []

    for _ in range(n_iter):
        y_pred = w0 + w1 * X
        error = y - y_pred
        dw0 = -(2 / n) * error.sum()
        dw1 = -(2 / n) * (X * error).sum()
        w0 -= alpha * dw0
        w1 -= alpha * dw1
        history.append((error ** 2).mean())

    return w0, w1, history

w0_s, w1_s, hist = gradient_descent(X_scaled, y_scaled, alpha=0.1, n_iter=200)
print(f"w₀={w0_s:.4f}, w₁={w1_s:.4f}")
print(f"Final MSE: {hist[-1]:.6f}")

Convergence Criteria

Gradient descent stops when one of three conditions is met:

1. Loss change < threshold: $|J(t)-J(t-1)|<10^{-6}$
2. Weight change < threshold: $\Vert \mathbf{w}(t)-\mathbf{w}(t-1)\Vert <10^{-8}$
3. Max iterations reached — safety stop to prevent infinite loops

Gradient Descent Cheat Sheet

Related Concepts and Honest Limitations

For linear regression, gradient descent and OLS always arrive at the same weights (both find the unique global minimum). The difference is practical: OLS is $O(n{p}^2+p^3)$ — impractical when $p$ or $n$ is large. Gradient descent with mini-batches scales to millions of samples and thousands of features.

The honest limitation of gradient descent is its sensitivity to hyperparameters: learning rate $\alpha$, the number of iterations, and the batch size all require tuning. The learning rate in particular needs to be scaled to the data — which is why feature scaling isn't a preprocessing convenience but a prerequisite for gradient descent to work at reasonable $\alpha$ values.

Test Your Understanding

1. For the anchor data, compute the gradient $\partial J/\partial w_1$ at $w_0=50$, $w_1=0.15$ manually. Confirm the sign: should gradient descent increase or decrease $w_1$ from here?

2. After one mini-batch gradient descent step with batch size 3 (samples 1, 3, 5 of the anchor), how does the update differ from a full-batch step? Which samples were excluded and what bias does that introduce?

3. If you scale only $X$ but not $y$, will gradient descent still converge? Will the learned $w_1$ correspond to the correct unscaled coefficient after inverse-transforming?

4. SGD is described as "noisier" than batch gradient descent. Under what conditions is that noise actually beneficial?

5. The learning rate $\alpha =0.5$ caused oscillation on our anchor. Derive the exact maximum stable learning rate for gradient descent on MSE using the Hessian eigenvalue bound $\alpha <2/{\lambda }_{\max }$.