Gradient Descent

OLS gives you the exact answer in one shot — but only for linear regression with MSE. The moment you change the loss function (from MSE to cross-entropy) or the model (from linear to a neural network), there's no algebraic shortcut. You need a general-purpose optimizer that works anywhere. Gradient descent is that algorithm.

Understanding it on linear regression — where you can verify the result against the known OLS solution — is the right place to build intuition before tackling harder problems. The core insight is simple: you compute which direction makes the error decrease fastest, then take a step in that direction, and repeat.

The Plan — Four Steps to Gradient Descent

We'll compute the gradient, see why raw data breaks naive GD, fix it with scaling, then compare the three variants and see how the learning rate controls everything.

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

Step 1 — The Gradient and the Scaling Problem

The gradient tells us which way is uphill. 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. This is not the same as the closed-form OLS, which jumps directly to the minimum in one step. GD takes many small steps, which makes it slower for simple problems but applicable to any differentiable loss function.

Let's compute the gradient for MSE and see what happens when we apply it to raw (unscaled) data:

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.

✓ Step 1 complete. The gradient on raw data is imbalanced — $w_1$ update overshoots by two orders of magnitude. The fix is feature scaling.

Step 2 — 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))

X_scaled: [-1.414 -0.943 -0.314  0.314  0.628  1.257]
y_scaled: [-1.414 -0.943 -0.314  0.314  0.628  1.257]

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).

✓ Step 2 complete. After scaling, $\alpha =0.1$ converges smoothly: $w_1$ reaches 0.9998 in scaled space (equivalent to 0.20 in original space) in 200 iterations.

Step 3 — 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.

✓ Step 3 complete. Batch GD uses all samples for a smooth gradient; SGD uses one for speed; mini-batch balances both. On our 6-sample anchor all converge to the same optimum.

Step 4 — 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}")

w₀=0.0000, w₁=0.9998
Final MSE: 0.000001

We set n_iter=200 because the convergence curve showed most of the improvement happens in the first 50-100 iterations. alpha=0.1 works here because we scaled the data first; on raw data the same learning rate would diverge.

✓ Step 4 complete. Learning rate controls convergence speed. Too small = glacial; too large = divergence. alpha=0.1 on scaled data converges in ~200 iterations to MSE ≈ 0.

Step 5 — Convergence Criteria

In practice, 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

✓ Step 5 complete. GD stops when loss change, weight change, or iteration count crosses a predefined boundary.

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.

A common frustration with gradient descent is discovering that it's hyperparameter-sensitive — not just the learning rate, but the number of iterations and batch size all need tuning. The learning rate in particular can't be chosen independently of scale: if you forget to scale features, what looked like a reasonable $\alpha =0.1$ on scaled data will diverge catastrophically on the raw values. This isn't a bug — it's a structural property of first-order optimization. Adaptive methods like Adam (used in deep learning) mitigate this by normalizing each parameter's gradient separately.

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 }$.