Gradient Descent
How almost every ML model, including neural nets, actually learns.
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.
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 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
The number (the Greek letter eta) is the learning rate, and it controls the size of each step. Choosing it well matters a great deal. If is too small, each step barely moves the weights and training takes an extremely long time. If 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.
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: 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.
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 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.
Why it works, and how big a step you can take
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
| learning rate (step size) | |
| gradient of the loss at w | |
| smoothness: the maximum curvature | |
| strong convexity: the minimum curvature | |
| largest and smallest Hessian eigenvalues | |
| condition number | |
| 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 , . If we choose the gradient-descent step , then
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 -smooth if its curvature is never more than in any direction (formally, its gradient changes by at most times the distance moved). For such losses, a result called the descent lemma shows that
The bracket is positive whenever , so in that range every step is guaranteed to reduce the loss. The standard safe choice is .
We can see exactly what happens by studying the simplest possible loss, , whose curvature is . Its gradient is , so one step gives . Repeating this times gives
Everything depends on the factor . If , the factor is between 0 and 1, so shrinks steadily towards the minimum at zero. If , the factor is between −1 and 0, so flips sign at every step, zig-zagging from one side of the minimum to the other, but the zig-zags still shrink. If , the factor is less than −1, so each step makes larger in size: the process diverges. In the demo, the bowl has , 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 . Each direction behaves like the one-dimensional case. To avoid divergence in the steepest direction, the learning rate must satisfy . But then the flattest direction only shrinks by a factor per step, which is very close to 1 if is small. With the safe choice , the slowest direction shrinks by per step, where is the condition number. A poorly conditioned problem, a long narrow valley, therefore needs roughly 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 loss | How fast the error shrinks after steps |
|---|---|
| convex and -smooth | |
| -strongly convex and -smooth | : geometric, called "linear convergence" |
| non-convex and smooth | the smallest gradient seen so far shrinks like |
SGD, momentum, Adam and second-order methods
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
| a mini-batch and its size | |
| gradient estimate at step t | |
| velocity (momentum) | |
| momentum coefficient (≈0.9) | |
| Adam's running averages of g and g² | |
| decay rates of those averages | |
| bias-corrected averages | |
| 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 , . Because the batch is chosen at random, 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 , 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); satisfies both. A practical rule of thumb, the linear scaling rule, says that if you multiply the batch size by , you can multiply the learning rate by roughly as well.
Momentum. The momentum method keeps a "velocity" vector , which is a decaying sum of past gradients, and moves the weights by that velocity:
The momentum coefficient , 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, , which lets it correct course slightly earlier. For poorly conditioned problems, momentum reduces the number of steps needed from roughly to roughly , a dramatic improvement when is large.
Adam. Adam keeps two running averages for each weight: , an average of recent gradients (this is momentum), and , an average of recent squared gradients, which measures how large that weight's gradients typically are:
Both averages start at zero, so in the first few steps they are biased towards zero. Adam corrects this by dividing by , a factor that is small at the start and approaches 1 as grows:
The division by 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 just prevents division by zero. The standard settings, , and , 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 , and takes the step . 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 matrix, which takes about 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.
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.
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))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())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…
📚 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.
- Google Machine Learning Crash Course ↗ Free course with exercises
- Dive into Deep Learning (free book with code) ↗ Interactive textbook in PyTorch, by Zhang, Lipton, Li & Smola