Gradient Descent Explained

What you’ll learn

• the update rule $\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \alpha\nabla J$, derived rather than asserted
• two full iterations computed by hand, matching NumPy to four decimals
• the exact threshold at which a learning rate stops converging and starts exploding
• batch, stochastic and mini-batch descent — the real trade-off between them
• why feature scaling turns a slow ravine into a fast bowl
• learning schedules, and when to stop

Intuition

You are standing on a hillside in fog. You cannot see the valley floor, but you can feel which way the ground slopes under your feet. Take a step downhill. Feel again. Step again.

That is the entire algorithm. The gradient is the direction of steepest ascent, so you move against it. The learning rate is how long a stride you take. Everything else — momentum, Adam, schedules — is refinement of those two sentences.

diagram Diagram mermaid

  flowchart TD
  A["Start from random parameters"] --> B["Compute predictions"]
  B --> C["Compute cost J"]
  C --> D["Compute gradient of J"]
  D --> E["Step against the gradient"]
  E --> F{"Converged?"}
  F -->|no| B
  F -->|yes| G["Return theta"]

The Normal Equation from Multiple Linear Regression already solves linear regression exactly, so why iterate at all? Because inverting an $n \times n$ matrix costs roughly $O(n^3)$. At 100,000 features that is hopeless, and for models with no closed form at all — logistic regression, neural networks, gradient boosting — iteration is the only option. Gradient descent is the workhorse of the entire field; linear regression is just the clearest place to learn it.

The math

The update rule

For a cost $J(\boldsymbol{\theta})$, the gradient collects the partial derivatives:

$$\nabla_{\boldsymbol{\theta}} J = \begin{bmatrix} \dfrac{\partial J}{\partial \theta_0} & \dfrac{\partial J}{\partial \theta_1} & \cdots & \dfrac{\partial J}{\partial \theta_n} \end{bmatrix}^\top$$

and each iteration steps against it:

$$\boxed{\;\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \alpha\,\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta})\;}$$

$\alpha$ is the learning rate. It is the only hyperparameter, and it decides everything.

The gradient of MSE

With $J(\boldsymbol{\theta}) = \frac{1}{m}\lVert\mathbf{X}\boldsymbol{\theta} - \mathbf{y}\rVert^2$, differentiating gives a strikingly simple result:

$$\nabla_{\boldsymbol{\theta}} J = \frac{2}{m}\mathbf{X}^\top\left(\mathbf{X}\boldsymbol{\theta} - \mathbf{y}\right)$$

Read it as English: the residual vector, projected back onto the features, scaled by two over the sample count. Every feature gets pushed in proportion to how much it contributed to the current error.

Where this comes from

The gradient of a quadratic form is derived in Useful Identities for Computing Gradients, and the geometric claim that the gradient points uphill is developed in Partial Differentiation and Gradients.

When does it actually converge?

This is the part most tutorials skip. For a quadratic cost with Hessian $\mathbf{H} = \frac{2}{m}\mathbf{X}^\top\mathbf{X}$, gradient descent converges if and only if

$$0 < \alpha < \frac{2}{\lambda_{\max}(\mathbf{H})}$$

where $\lambda_{\max}$ is the largest eigenvalue. Above that threshold each step overshoots by more than it corrects and the parameters diverge geometrically. The condition number $\kappa = \lambda_{\max}/\lambda_{\min}$ then decides how fast convergence happens: a $\kappa$ of 1 is a round bowl and descent goes straight in, while a $\kappa$ of 1,000 is a narrow ravine that forces a zig-zag.

Both facts have the same practical consequence, and it is the reason for the whole preprocessing phase: scale your features.

Worked example by hand

The five-point dataset with the feature centred ($x_c = x - 3$), so the Hessian is diagonal and the arithmetic stays exact. Parameters are $[b, w]$, starting from $[0, 0]$, with $\alpha = 0.2$.

$i$	$x_c$	$y$
1	−2	2
2	−1	4
3	0	5
4	1	4
5	2	5

The Hessian, and the stability limit.

$$\mathbf{H} = \frac{2}{5}\mathbf{X}^\top\mathbf{X} = \frac{2}{5}\begin{bmatrix} 5 & 0 \\ 0 & 10 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 4 \end{bmatrix}$$

Eigenvalues 2 and 4, so descent diverges for any $\alpha \geq 2/4 = 0.5$. Our 0.2 is comfortably inside. The optimum is $[b, w] = [4, 0.6]$.

Iteration 0. With $\boldsymbol{\theta} = [0, 0]$ every prediction is 0, so the residual is $-\mathbf{y}$:

$$\mathbf{X}^\top(\mathbf{X}\boldsymbol{\theta} - \mathbf{y}) = \begin{bmatrix} -(2{+}4{+}5{+}4{+}5) \\ (-2)(-2) + (-1)(-4) + 0 + (1)(-4) + (2)(-5) \end{bmatrix} = \begin{bmatrix} -20 \\ -6 \end{bmatrix}$$ $$\nabla J = \tfrac{2}{5}\begin{bmatrix} -20 \\ -6 \end{bmatrix} = \begin{bmatrix} -8 \\ -2.4 \end{bmatrix}, \qquad \boldsymbol{\theta} \leftarrow \begin{bmatrix} 0 \\ 0 \end{bmatrix} - 0.2\begin{bmatrix} -8 \\ -2.4 \end{bmatrix} = \begin{bmatrix} 1.6 \\ 0.48 \end{bmatrix}$$

Iteration 1. Predictions are now $1.6 + 0.48x_c$, giving residuals $[-1.36, -2.88, -3.4, -1.92, -2.44]$:

$$\nabla J = \tfrac{2}{5}\begin{bmatrix} -12 \\ -1.2 \end{bmatrix} = \begin{bmatrix} -4.8 \\ -0.48 \end{bmatrix}, \qquad \boldsymbol{\theta} \leftarrow \begin{bmatrix} 2.56 \\ 0.576 \end{bmatrix}$$

The cost falling.

step	$b$	$w$	MSE
0	0.000	0.0000	17.2000
1	1.600	0.4800	6.2688
2	2.560	0.5760	2.5548
3	3.136	0.5952	1.2265
⋮	⋮	⋮	⋮
∞	4.000	0.6000	0.4800

The slope reaches its final value almost immediately while the intercept takes far longer. That is the condition number in action: the eigenvalue along $w$ is twice the eigenvalue along $b$, so the same $\alpha$ makes twice the progress in that direction.

The learning rate

figure Same start, three learning rates, 70 steps each matplotlib

Green (0.03) is still travelling when the budget runs out. Blue (0.20) walks in cleanly. Red (0.46) is near the stability limit of 0.5 and ricochets across the valley on every step.

figure The learning curve tells you immediately which rate is wrong matplotlib

Plot cost against iteration for every run. Flat and high means the rate is too small; a rising line means it is above the stability threshold.

Reading the plots

What you see	What it means	What to do
Cost falls smoothly to a plateau	Healthy	Nothing
Cost falls, very slowly	$\alpha$ too small	Multiply by 3
Cost oscillates but trends down	$\alpha$ just under the limit	Halve it
Cost rises or hits nan	$\alpha$ above $2/\lambda_{\max}$	Divide by 10
Cost falls then flattens high	Underfitting, not an $\alpha$ problem	More features or capacity

A practical recipe: try $\alpha \in \{0.001, 0.01, 0.1, 1\}$, plot all four cost curves on one log axis, and take the largest rate that still descends smoothly.

sketch Gradient descent rolls downhill p5.js Pause Restart

Each step moves against the slope toward the minimum of the loss curve; the steps shrink as the slope flattens.

Notice the steps shrinking on their own as the curve flattens. The learning rate never changes — the gradient shrinks near the minimum, so descent automatically slows down as it arrives.

Why scaling matters

figure The same optimisation problem, before and after scaling matplotlib

Steepest descent goes perpendicular to the contour it stands on. In a ravine that direction points across the valley rather than along it, so the path bounces off the walls and creeps toward the minimum.

Unscaled features produce an elongated cost surface, and the negative gradient points across the valley rather than down it. Standardising makes the contours near-circular and lets descent walk straight in — often an order of magnitude fewer iterations, from the same code.

scaling_and_sgd.py

from sklearn.datasets import load_diabetes
from sklearn.linear_model import SGDRegressor
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
 
X, y = load_diabetes(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)
 
scaled = make_pipeline(
    StandardScaler(),
    SGDRegressor(max_iter=2000, tol=1e-4, eta0=0.01, random_state=0),
).fit(X_train, y_train)
 
raw = SGDRegressor(
    max_iter=2000, tol=1e-4, eta0=0.01, random_state=0
).fit(X_train, y_train)
 
print(f"scaled   R^2 = {scaled.score(X_test, y_test):.4f}")  # 0.4767
print(f"unscaled R^2 = {raw.score(X_test, y_test):.4f}")     # 0.4554
print(f"epochs used  = {scaled[-1].n_iter_}")                # 27

The scaled pipeline converges in 27 epochs and lands on 0.4767 — indistinguishable from the exact Normal Equation answer of 0.4773. The unscaled version burns all 2,000 epochs, emits a convergence warning, and still ends up worse.

The three variants

How much data does one gradient use?

diagram Diagram mermaid

  flowchart TD
  A["Batch GD
all m rows per step"] --> A2["Smooth, expensive steps
settles exactly on the minimum"]
  B["Stochastic GD
1 random row per step"] --> B2["Cheap, noisy steps
bounces around the minimum forever"]
  C["Mini-batch GD
32 to 256 rows per step"] --> C2["Balanced; vectorises well on GPUs
the default everywhere"]

$$\text{Batch: } \nabla J = \frac{2}{m}\mathbf{X}^\top(\mathbf{X}\boldsymbol{\theta} - \mathbf{y}) \qquad \text{SGD: } \nabla J^{(i)} = 2\,\mathbf{x}^{(i)}\!\left(\boldsymbol{\theta}^\top\mathbf{x}^{(i)} - y^{(i)}\right)$$

The stochastic gradient is an unbiased estimate of the batch gradient — right on average, wrong on any individual step. That noise is not purely a cost: it lets SGD escape shallow local minima that would trap batch descent on non-convex problems, which is exactly why deep learning uses it.

	Batch	Stochastic	Mini-batch
Rows per step	$m$	1	32–256
Cost per step	High	Very low	Low
Path	Smooth	Very noisy	Slightly noisy
Settles exactly?	Yes	No, needs a schedule	Nearly
Out-of-core	No	Yes	Yes
Hardware fit	Poor	Poor	Excellent
scikit-learn	LinearRegression	SGDRegressor	SGDRegressor.partial_fit

sketch Gradient descent paths in parameter space p5.js Pause Restart

Batch GD takes a smooth path and stops at the minimum; Stochastic GD is noisy and keeps wandering; Mini-batch GD lands in between. Click to restart.

Learning schedules

Because SGD never settles, the standard fix is to shrink the learning rate over time:

$$\alpha_t = \frac{\alpha_0}{1 + \text{decay} \cdot t}$$

Early on the steps are long enough to cover ground; later they are short enough to sit still. Decay too fast and it freezes before arriving; too slowly and it keeps bouncing. SGDRegressor exposes this as learning_rate="invscaling" with eta0 and power_t.

From scratch

gradient_descent.py

import numpy as np
 
 
def batch_gradient_descent(X, y, lr=0.2, n_iter=50):
    """Plain batch gradient descent. X must already include the bias column."""
    m = len(y)
    theta = np.zeros(X.shape[1])
    history = []
 
    for _ in range(n_iter):
        residual = X @ theta - y
        history.append(float((residual**2).mean()))
        gradient = (2 / m) * X.T @ residual
        theta = theta - lr * gradient
 
    return theta, history
 
 
x_centred = np.array([1.0, 2.0, 3.0, 4.0, 5.0]) - 3.0
X = np.c_[np.ones(5), x_centred]
y = np.array([2.0, 4.0, 5.0, 4.0, 5.0])
 
theta, history = batch_gradient_descent(X, y, lr=0.2, n_iter=50)
 
print(theta.round(4))            # [4.  0.6]
print([round(h, 4) for h in history[:4]])
# [17.2, 6.2688, 2.5548, 1.2265]
 
# The stability limit, computed rather than guessed
hessian = (2 / len(y)) * X.T @ X
print(f"max stable lr = {2 / np.linalg.eigvalsh(hessian).max():.3f}")   # 0.500

The first four cost values reproduce the hand-computed table exactly, and after 50 iterations the parameters have reached the Normal Equation’s answer of $[4, 0.6]$.

pch.algoTag Batch Gradient Descent Optimisation · First-order

pch.algoApi sklearn.linear_model.SGDRegressor (stochastic and mini-batch variants)

pch.algoAssumes

• The cost is differentiable with respect to the parameters
• The learning rate is below 2 over the largest Hessian eigenvalue
• Features are on comparable scales, or convergence will be slow

pch.algoCost

pch.algoTrain

O(m·n) per iteration

pch.algoPredict

O(n)

pch.algoMemory

O(n)

m = samples, n = features; total cost is per-iteration cost times the iteration count

pch.algoHyperparams

• learning_rate (alpha, eta0) default 0.01 The one that matters. Too small crawls, too large diverges. Tune on a log grid.
• max_iter default 1000 Iteration budget. Pair it with tol so training stops when progress stalls.
• tol default 1e-3 Stop when the loss improves by less than this for n_iter_no_change epochs.
• batch size default 1 for SGDRegressor Larger batches mean smoother gradients and better hardware use; 32 to 256 is the usual range.

pch.algoReachFor

• You have too many features for a closed-form solution
• The data does not fit in memory and must stream
• The model has no closed form at all — logistic regression, neural networks
• You want to warm-start or update a model online

pch.algoLookElsewhere

• The problem is small and a closed form exists — just use LinearRegression
• You cannot scale the features
• You need bit-for-bit reproducibility without pinning every random seed

Pitfalls

Not scaling before gradient descent

This is the single most common mistake. With features spanning wildly different ranges the cost surface becomes a ravine, and descent either crawls or diverges. Put StandardScaler in the pipeline. Note this does not apply to the Normal Equation, which is scale-invariant — a genuine difference between the two methods.

A cost that is nan means the learning rate, not the data

Divergence overflows to infinity within a handful of steps. Before hunting for bad rows, divide $\alpha$ by 10 and rerun.

Never use the test set as your convergence check

Watching test loss to decide when to stop leaks the test set into training. Hold out a separate validation split, or use the training-loss plateau via tol.

SGD without a schedule never settles

A constant learning rate leaves stochastic descent bouncing around the minimum indefinitely. It may be close enough — but if you need the actual optimum, decay the rate.

pch.quizTag pch.quizDefaultTitle

1. Why does the update rule subtract the gradient instead of adding it?

   A To keep the parameters positive B Because the gradient points in the direction of steepest increase, and we want to decrease the cost C Because of the minus sign in the residual D It is a convention with no mathematical basis
   pch.quizShowAnswer

   B — Because the gradient points in the direction of steepest increase, and we want to decrease the cost — The gradient is the direction of steepest ascent. Minimising means walking the other way.

2. Your cost becomes nan after four iterations. What is the most likely cause?

   A The dataset contains missing values B The learning rate exceeds the stability threshold, so each step overshoots more than the last C You need more iterations D The features are correlated
   pch.quizShowAnswer

   B — The learning rate exceeds the stability threshold, so each step overshoots more than the last — Above 2 divided by the largest Hessian eigenvalue, the iteration diverges geometrically and overflows within a few steps. Reduce the learning rate by a factor of ten.

3. What is the practical effect of feature scaling on gradient descent?

   A It changes the final fitted parameters to better values B It makes the cost contours rounder, so descent needs far fewer iterations to reach the same minimum C It removes the need for a learning rate D It has no effect; scaling only matters for the Normal Equation
   pch.quizShowAnswer

   B — It makes the cost contours rounder, so descent needs far fewer iterations to reach the same minimum — Scaling does not change where the minimum is in terms of predictions — it changes the shape of the path to it. Rounder contours mean the negative gradient points at the minimum instead of across the valley.

4. Why does stochastic gradient descent still work despite using one row per step?

   A Because one row is usually representative of the whole dataset B Because the single-row gradient is an unbiased estimate of the full gradient, so the noise averages out over many steps C Because the learning rate compensates for the missing data D It does not work; it only approximates the answer badly
   pch.quizShowAnswer

   B — Because the single-row gradient is an unbiased estimate of the full gradient, so the noise averages out over many steps — Each step is wrong individually but right on average. Over many cheap steps the errors cancel, and the noise even helps escape shallow minima on non-convex problems.

🧪 Try It Yourself

Exercise 1 – One batch gradient step

pch.exerciseTag pch.exerciseTitle

Exercise 2 – Watch the cost fall

pch.exerciseTag pch.exerciseTitle

Exercise 3 – Compute the stability limit

pch.exerciseTag pch.exerciseTitle

Exercise 4 – Push it past the limit

pch.exerciseTag pch.exerciseTitle

Exercise 5 – Scaling changes everything for SGD

pch.exerciseTag pch.exerciseTitle

Recap

• The update rule is $\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \alpha\nabla J$, and for MSE the gradient is $\frac{2}{m}\mathbf{X}^\top(\mathbf{X}\boldsymbol{\theta} - \mathbf{y})$.
• Convergence requires $\alpha < 2/\lambda_{\max}(\mathbf{H})$ — on the worked example, 0.5.
• Two hand iterations at $\alpha = 0.2$ take the cost from 17.20 to 6.27 to 2.55, matching NumPy exactly.
• Scaling controls the condition number, which controls how many iterations you pay for.
• Batch is smooth and expensive, stochastic is noisy and cheap, mini-batch is the default.
• Plot cost against iteration on every run; the shape of that curve diagnoses the learning rate immediately.

Exercise 6 – Find the learning rate that breaks it

pch.exerciseTag pch.exerciseTitle

Next

Continue to Regularization - Ridge and Lasso Regression — add a penalty term to the same cost and watch overfitting recede.