Machine Learning
Topic 8 · ML foundations · ⏱ about 4 h

Gradient Descent

How almost every ML model, including neural nets, actually learns.

Show:
In this topic
Beginner

Walking downhill

Gradient descent is the algorithm that trains almost every model in modern machine learning, from linear regression to networks with billions of parameters. The idea behind it is easiest to grasp through an analogy.

too small: slowη = 0.06about rightη = 0.3too large: zig-zagη = 0.95
The learning rate controls the step size: too small is slow, too large overshoots and can diverge.

Imagine you are standing somewhere on a hillside in thick fog, and you want to reach the bottom of the valley. You can't see where the valley is, but you can feel the slope of the ground beneath your feet. A sensible strategy is to work out which direction slopes downhill most steeply, take a step that way, and then repeat. Each step takes you lower, and eventually you reach a point where the ground is flat in every direction: the bottom.

In machine learning, the "landscape" is the loss function, whose height at each point is how badly the model performs with those parameter values, and our position is the current set of weights. The gradient ∇L(w)\nabla L(w) is a vector that points in the direction of steepest increase of the loss, so to go downhill we move in the opposite direction. Each step updates the weights as

w←w−η ∇L(w). w \leftarrow w - \eta\,\nabla L(w).

The number η\eta (the Greek letter eta) is the learning rate, and it controls the size of each step. Choosing it well matters a great deal. If η\eta is too small, each step barely moves the weights and training takes an extremely long time. If η\eta is too large, a step can jump right over the bottom of the valley and land higher up on the opposite side; then the next step overshoots even further, and the weights fly off towards infinity. This is called divergence, and you will see it in the demo below. A good learning rate is large enough to make steady progress but small enough to stay stable.

Beginner

Watch it: Gradient descent: rolling downhill on the loss

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Try it

Try it: learning rate

Press Step or Run. Try η = 0.1 (slow), 0.9 (fast), 1.8 (zig-zag), 2.1 (diverges). Switch to the non-convex loss and see how the starting point and step size decide which valley you end up in.

Interactive: this part runs in your browser.

Beginner

Batch, stochastic, mini-batch — and better optimisers

Gradient descent comes in three flavours, which differ only in how much data is used to compute each gradient.

batch GD: smooth, exact steps (expensive)SGD / mini-batch: noisy but cheap steps
Batch gradient descent uses all the data per step; stochastic and mini-batch versions take cheaper, noisier steps that still head downhill on average.

Batch gradient descent computes the gradient using every training example before taking a single step. The gradient is exact, so each step heads in the true downhill direction, but each step is expensive: with a million examples, you must process all million just to move once.

Stochastic gradient descent (SGD), in its original form, goes to the opposite extreme and estimates the gradient from a single randomly chosen example. Each step is very cheap, but the direction is noisy, so the path to the minimum wanders. Surprisingly, this noise is not all bad: it can shake the weights out of shallow local minima and flat regions where batch gradient descent would stall.

Mini-batch gradient descent is the compromise that everyone uses in practice. It computes the gradient on a small random batch, typically between 32 and 512 examples. That is enough to make the direction reasonably reliable, small enough for each step to be fast, and a good fit for GPUs, which process a batch in parallel almost as quickly as a single example. When people say "SGD" today, they usually mean the mini-batch version.

Modern training rarely uses the plain update, though. Momentum keeps a running average of recent gradients and moves in that averaged direction, like a heavy ball rolling downhill. Directions that are consistently downhill build up speed, while directions where the gradient keeps flipping sign (the zig-zags across a narrow valley) cancel out. RMSProp and Adam go further by giving each weight its own effective step size, shrinking the steps for weights whose gradients are usually large and enlarging them for weights whose gradients are usually small. Adam combines momentum with this per-weight scaling and is the default choice for training neural networks.

Two more terms are worth knowing. An epoch is one complete pass through the training data; with 10,000 examples and batches of 100, one epoch is 100 steps. And a learning-rate schedule changes the learning rate during training, typically starting with a short "warm-up" from a small value, then gradually decreasing it so that the weights can settle precisely into a minimum instead of bouncing around it.

Interactive: this part runs in your browser.

Interactive. Three optimisers race down the same narrow valley from the same start.
Intermediate · Maths

Why it works, and how big a step you can take

📐 Maths you'll need: m-calculus · m-optim · m-eigen
💡 The idea in plain words

Each step of gradient descent assumes the slope stays the same for the length of the step. If the step is too long for how curved the valley is, you overshoot the bottom, and if it's far too long you climb up the other side further than you started: divergence. The steepest curvature sets the speed limit, and the flattest direction sets how long you'll be travelling.

🔤 Symbols in this section
η\etalearning rate (step size)
∇L(w)\nabla L(w)gradient of the loss at w
β\betasmoothness: the maximum curvature
μ\mustrong convexity: the minimum curvature
λ1, λd\lambda_1,\ \lambda_dlargest and smallest Hessian eigenvalues
κ=λ1/λd\kappa = \lambda_1/\lambda_dcondition number
L∗L^*the minimum possible loss

This section explains, mathematically, why gradient descent works, and exactly how large the learning rate can be before it breaks down.

The starting point is the first-order Taylor expansion. For a small step hh, L(w+h)≈L(w)+∇L(w)⊤hL(w + h) \approx L(w) + \nabla L(w)^\top h. If we choose the gradient-descent step h=−η∇L(w)h = -\eta\nabla L(w), then

L(w−η∇L)≈L(w)−η ∥∇L(w)∥2. L(w - \eta\nabla L) \approx L(w) - \eta\,\lVert\nabla L(w)\rVert^2 .

The second term is negative whenever the gradient is non-zero, so a sufficiently small step always reduces the loss. The word "approximately" is the catch: the approximation ignores curvature, and for a large step the curvature can undo the progress.

To make this precise we need a bound on the curvature. A loss is called β\beta-smooth if its curvature is never more than β\beta in any direction (formally, its gradient changes by at most β\beta times the distance moved). For such losses, a result called the descent lemma shows that

L(wt+1)≤L(wt)−η(1−βη2)∥∇L(wt)∥2. L(w_{t+1}) \le L(w_t) - \eta\Big(1 - \frac{\beta\eta}{2}\Big)\lVert\nabla L(w_t)\rVert^2.

The bracket is positive whenever η<2/β\eta < 2/\beta, so in that range every step is guaranteed to reduce the loss. The standard safe choice is η=1/β\eta = 1/\beta.

We can see exactly what happens by studying the simplest possible loss, L(w)=12aw2L(w) = \tfrac12 a w^2, whose curvature is aa. Its gradient is awaw, so one step gives wt+1=wt−ηawt=(1−ηa) wtw_{t+1} = w_t - \eta a w_t = (1 - \eta a)\,w_t. Repeating this tt times gives

wt=(1−ηa)t w0. w_t = (1 - \eta a)^t\, w_0 .

Everything depends on the factor 1−ηa1 - \eta a. If 0<η<1/a0 < \eta < 1/a, the factor is between 0 and 1, so ww shrinks steadily towards the minimum at zero. If 1/a<η<2/a1/a < \eta < 2/a, the factor is between −1 and 0, so ww flips sign at every step, zig-zagging from one side of the minimum to the other, but the zig-zags still shrink. If η>2/a\eta > 2/a, the factor is less than −1, so each step makes ww larger in size: the process diverges. In the demo, the bowl has a=1a = 1, which is exactly why it blows up once the learning rate passes 2.

In many dimensions, a quadratic bowl has a different curvature along each eigenvector of its Hessian, given by the eigenvalues λ1≥⋯≥λd>0\lambda_1 \ge \dots \ge \lambda_d > 0. Each direction behaves like the one-dimensional case. To avoid divergence in the steepest direction, the learning rate must satisfy η<2/λ1\eta < 2/\lambda_1. But then the flattest direction only shrinks by a factor (1−ηλd)(1 - \eta\lambda_d) per step, which is very close to 1 if λd\lambda_d is small. With the safe choice η=1/λ1\eta = 1/\lambda_1, the slowest direction shrinks by (1−1/κ)(1 - 1/\kappa) per step, where κ=λ1/λd\kappa = \lambda_1/\lambda_d is the condition number. A poorly conditioned problem, a long narrow valley, therefore needs roughly κ\kappa times as many steps, which is why feature scaling speeds training up so dramatically.

These ideas lead to the standard convergence results, summarised below. For non-convex losses such as neural networks, the guarantee is weaker: gradient descent will find a point where the gradient is nearly zero, but that could be a local minimum or a saddle point rather than the best possible solution.

Type of lossHow fast the error shrinks after tt steps
convex and β\beta-smoothL(wt)−L∗=O(1/t)L(w_t) - L^* = O(1/t)
μ\mu-strongly convex and β\beta-smoothO((1−μ/β)t)O\big((1 - \mu/\beta)^t\big): geometric, called "linear convergence"
non-convex and smooththe smallest gradient seen so far shrinks like O(1/t)O(1/t)
Key takeaway. Gradient descent is safe for η < 2/(max curvature); its speed is governed by the condition number, so well-scaled problems converge much faster.
Advanced

SGD, momentum, Adam and second-order methods

📐 Maths you'll need: m-prob · m-optim
💡 The idea in plain words

Plain gradient descent has two problems: computing the exact gradient on all the data is slow, and in long thin valleys it zig-zags. SGD uses a cheap, noisy gradient from a small batch. Momentum lets the steps build up speed like a rolling ball, smoothing out zig-zags. Adam also gives each weight its own step size, based on how big its gradients usually are.

🔤 Symbols in this section
B, ∣B∣B,\ |B|a mini-batch and its size
gtg_tgradient estimate at step t
vtv_tvelocity (momentum)
μ\mumomentum coefficient (≈0.9)
mt, vtm_t,\ v_tAdam's running averages of g and g²
β1, β2\beta_1,\ \beta_2decay rates of those averages
m^t, v^t\hat m_t,\ \hat v_tbias-corrected averages
H−1H^{-1}inverse Hessian (Newton's method)

Plain gradient descent has two practical weaknesses: computing the exact gradient over a huge dataset is slow, and in narrow valleys it wastes effort zig-zagging. The methods in this section address both.

Stochastic gradients. Suppose that instead of the full gradient we use the average gradient over a random mini-batch BB, g=1∣B∣∑i∈B∇ℓi(w)g = \frac{1}{|B|}\sum_{i\in B}\nabla \ell_i(w). Because the batch is chosen at random, gg is an unbiased estimate of the true gradient: on average it points in exactly the right direction. Its noise, measured by its variance, shrinks in proportion to 1/∣B∣1/|B|, by the averaging rule from the probability topic. The noise has one consequence that must be managed: with a fixed learning rate, SGD never settles exactly at the minimum, but keeps jittering in a small region around it. Gradually reducing the learning rate fixes this. A classic condition that guarantees convergence is that the learning rates add up to infinity (so the algorithm can travel any distance) while their squares add up to a finite number (so the noise eventually dies out); ηt∝1/t\eta_t \propto 1/t satisfies both. A practical rule of thumb, the linear scaling rule, says that if you multiply the batch size by kk, you can multiply the learning rate by roughly kk as well.

Momentum. The momentum method keeps a "velocity" vector vv, which is a decaying sum of past gradients, and moves the weights by that velocity:

vt+1=μvt−η∇L(wt),wt+1=wt+vt+1. v_{t+1} = \mu v_t - \eta\nabla L(w_t), \qquad w_{t+1} = w_t + v_{t+1}.

The momentum coefficient μ\mu, typically 0.9, controls how much of the old velocity is kept. In a direction where the gradient points the same way step after step, the velocity keeps growing, so the algorithm accelerates along the valley floor. In a direction where the gradient flips sign each step, successive contributions cancel, damping the zig-zag. The Nesterov variant computes the gradient at the point the momentum is about to carry us to, wt+μvtw_t + \mu v_t, which lets it correct course slightly earlier. For poorly conditioned problems, momentum reduces the number of steps needed from roughly κ\kappa to roughly κ\sqrt\kappa, a dramatic improvement when κ\kappa is large.

Adam. Adam keeps two running averages for each weight: mtm_t, an average of recent gradients (this is momentum), and vtv_t, an average of recent squared gradients, which measures how large that weight's gradients typically are:

mt=β1mt−1+(1−β1)gt,vt=β2vt−1+(1−β2)gt2. m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t, \qquad v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2.

Both averages start at zero, so in the first few steps they are biased towards zero. Adam corrects this by dividing by 1−βt1 - \beta^t, a factor that is small at the start and approaches 1 as tt grows:

m^t=mt1−β1t,v^t=vt1−β2t,wt+1=wt−η m^tv^t+ϵ. \hat m_t = \frac{m_t}{1-\beta_1^t}, \qquad \hat v_t = \frac{v_t}{1-\beta_2^t}, \qquad w_{t+1} = w_t - \eta\,\frac{\hat m_t}{\sqrt{\hat v_t} + \epsilon}.

The division by v^t\sqrt{\hat v_t} is the key idea. A weight whose gradients are usually large gets its step scaled down, and a weight whose gradients are usually small gets its step scaled up, so every weight moves at a sensible pace without hand-tuning. The tiny constant ϵ\epsilon just prevents division by zero. The standard settings, β1=0.9\beta_1 = 0.9, β2=0.999\beta_2 = 0.999 and ϵ=10−8\epsilon = 10^{-8}, work well for most problems. RMSProp is essentially Adam without the momentum term.

Newton's method. All the methods above use only the slope. Newton's method also uses the curvature, through the Hessian HH, and takes the step wt+1=wt−H−1∇Lw_{t+1} = w_t - H^{-1}\nabla L. Dividing by the curvature automatically takes large steps in flat directions and small steps in steep ones, so it is unaffected by poor conditioning and converges extremely quickly near a minimum. The cost is that it must store and invert a d×dd\times d matrix, which takes about d3d^3 operations; for a model with millions of weights that is impossible. Approximations such as L-BFGS, which build up a cheap estimate of the curvature from recent gradients, are popular for medium-sized problems.

Key takeaway. Mini-batch SGD trades exactness for speed; momentum smooths and accelerates; Adam adapts the step per weight; Newton uses curvature but is too expensive for big models.
Code

Code: GD, mini-batch SGD and Adam from scratch

All three optimise the same linear-regression loss. Change lr to see divergence, or compare how many epochs each needs.

Python · NumPy from scratch
import numpy as np

rng = np.random.default_rng(1)
n, d = 1000, 5
X = rng.normal(size=(n, d)) * np.array([1, 2, 5, 10, 0.5])   # badly scaled features
w_true = rng.normal(size=d)
y = X @ w_true + rng.normal(scale=0.1, size=n)

def loss(w):            return np.mean((X @ w - y) ** 2)
def grad(w, idx=None):
    Xi, yi = (X, y) if idx is None else (X[idx], y[idx])
    return 2 / len(yi) * Xi.T @ (Xi @ w - yi)

# Safe step size from the largest Hessian eigenvalue (beta-smoothness)
H = 2 / n * X.T @ X
eig = np.linalg.eigvalsh(H)
print("condition number:", round(eig[-1] / eig[0], 1))
lr_gd = 1 / eig[-1]

# --- batch gradient descent ---
w = np.zeros(d)
for t in range(500):
    w -= lr_gd * grad(w)
print("GD   loss:", loss(w))

# --- mini-batch SGD with momentum ---
w, v = np.zeros(d), np.zeros(d)
for epoch in range(20):
    for idx in np.array_split(rng.permutation(n), n // 32):
        v = 0.9 * v - lr_gd * grad(w, idx)
        w += v
print("SGD+momentum loss:", loss(w))

# --- Adam ---
w, m, s = np.zeros(d), np.zeros(d), np.zeros(d)
b1, b2, eps, lr = 0.9, 0.999, 1e-8, 0.05
t = 0
for epoch in range(20):
    for idx in np.array_split(rng.permutation(n), n // 32):
        t += 1
        g = grad(w, idx)
        m = b1 * m + (1 - b1) * g
        s = b2 * s + (1 - b2) * g ** 2
        m_hat, s_hat = m / (1 - b1 ** t), s / (1 - b2 ** t)
        w -= lr * m_hat / (np.sqrt(s_hat) + eps)
print("Adam loss:", loss(w))
Open in playground ↗
Python · PyTorch (same idea, autograd computes the gradient)
import torch

Xt, yt = torch.tensor(X, dtype=torch.float32), torch.tensor(y, dtype=torch.float32)
w = torch.zeros(d, requires_grad=True)
opt = torch.optim.Adam([w], lr=0.05)          # try torch.optim.SGD([w], lr=..., momentum=0.9)

for step in range(2000):
    opt.zero_grad()
    loss = ((Xt @ w - yt) ** 2).mean()
    loss.backward()                           # autograd fills w.grad
    opt.step()
print(loss.item())
This code needs PyTorch, which cannot run inside a web page. To run it, press Copy, then paste it into a new notebook in Google Colab ↗ (free; Runtime → Change runtime type → GPU for deep learning).
Check yourself

Quiz

1. The loss keeps increasing every step. Most likely cause?

2. Mini-batch gradient descent uses…

3. One epoch means…

4. For L(w) = ½·a·w², gradient descent diverges when η exceeds…

5. Adam divides by (1 − β₁ᵗ) because…

6. Momentum improves the condition-number dependence from κ to roughly…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready