Gradient descent is almost embarrassingly simple: compute the slope, take a small step downhill, repeat. Yet a variant of it trains every large neural network. In this lecture we analyse it properly — why it works, how to choose the step size, what happens when gradients are noisy, and how fast it converges.
The algorithm#
To minimise a differentiable function $f(\mathbf{w})$:
where $\eta > 0$ is the learning rate (step size).
Why it decreases the loss#
By Taylor expansion, for small $\eta$:
The decrease is proportional to the squared gradient norm — guaranteed descent as long as the step is small enough that the linear approximation holds.
Choosing the learning rate#
If $f$ is $L$-smooth (its gradient is $L$-Lipschitz), the descent lemma gives
So any $\eta < 2/L$ guarantees decrease, and $\eta = 1/L$ gives the best guaranteed decrease of $\frac{1}{2L}\|\nabla f\|^2$ per step.
For a quadratic $f(\mathbf{w}) = \frac{1}{2}\mathbf{w}^\top\mathbf{H}\mathbf{w}$, analysing each eigen-direction separately shows the update multiplies the component along eigenvector $i$ by $(1 - \eta\lambda_i)$:
- $\eta < 2/\lambda_{\max}$: all components shrink — convergence.
- $\eta > 2/\lambda_{\max}$: the steepest direction oscillates with growing amplitude — divergence.
- Small $\lambda_{\min}$: the flattest direction shrinks very slowly — the condition number bottleneck.
Convergence rates#
For gradient descent with $\eta = 1/L$:
| Function class | Rate | Iterations for accuracy $\epsilon$ |
|---|---|---|
| Convex, $L$-smooth | $f(\mathbf{w}_T) - f^* = O(1/T)$ | $O(1/\epsilon)$ |
| $\mu$-strongly convex, $L$-smooth | $O\big((1 - \mu/L)^T\big)$ — linear | $O(\kappa\log(1/\epsilon))$ |
| Non-convex, $L$-smooth | $\min_t \|\nabla f(\mathbf{w}_t)\|^2 = O(1/T)$ | finds approximate stationary points |
Nesterov's accelerated gradient improves the convex rate to $O(1/T^2)$ and the strongly convex rate to depend on $\sqrt{\kappa}$ instead of $\kappa$ — provably optimal among first-order methods.
Stochastic gradient descent#
In ML, the loss is an average over $n$ training examples: $f(\mathbf{w}) = \frac{1}{n}\sum_i \ell_i(\mathbf{w})$. Computing the full gradient costs $O(n)$ per step — prohibitive for millions of examples. Stochastic gradient descent (SGD) uses a random mini-batch $\mathcal{B}$:
The mini-batch gradient is an unbiased estimate with variance proportional to $1/|\mathcal{B}|$.
Key consequences:
- Cheap steps, many of them. SGD makes progress long before a full pass over the data.
- Noise floor. With a constant learning rate, SGD does not converge exactly — it bounces around the minimum in a region whose size scales with $\eta \times$ gradient variance. Hence learning-rate decay.
- Robbins–Monro conditions for convergence: $\sum_t \eta_t = \infty$ and $\sum_t \eta_t^2 < \infty$ (e.g. $\eta_t \propto 1/t$).
- Implicit regularisation. SGD's noise may help it find flatter minima that generalise better — an active research topic.
import numpy as np
rng = np.random.default_rng(0)
n, d = 10_000, 5
X = rng.normal(size=(n, d)); w_true = rng.normal(size=d)
y = X @ w_true + 0.5 * rng.normal(size=n)
def run(batch, lr, epochs=5):
w = np.zeros(d)
for epoch in range(epochs):
idx = rng.permutation(n)
for start in range(0, n, batch):
b = idx[start:start + batch]
grad = 2 * X[b].T @ (X[b] @ w - y[b]) / len(b)
w -= lr * grad
return np.linalg.norm(w - w_true)
for batch in [1, 32, 1024, n]:
print(f"batch {batch:>5}: error {run(batch, lr=0.01 if batch < 100 else 0.1):.4f}")Linear scaling and large batches#
Doubling the batch halves gradient variance. A useful heuristic — the linear scaling rule — increases the learning rate proportionally to the batch size, with a warm-up period at the start of training. Beyond a "critical batch size", however, bigger batches give diminishing returns: you save wall-clock time on parallel hardware but spend more total computation.
Beyond plain gradient descent#
Plain SGD struggles with ill-conditioning and noisy gradients. The deep-learning track covers the fixes:
- Momentum and Nesterov momentum — accumulate velocity to move faster along consistent directions.
- Adaptive methods (AdaGrad, RMSProp, Adam, AdamW) — per-parameter step sizes.
- Schedules — warm-up, step decay, cosine annealing.
- Second-order ideas — Newton, quasi-Newton (L-BFGS), and approximate curvature methods.