Gradient descent

Intuition

You are somewhere on the loss surface and you want the bottom. You cannot see it. What you can compute is the slope where you stand.

So: look at the slope, take a step downhill, look again. Repeat. That is the entire algorithm, and it is the one training almost every model you will meet. Its power is that it needs no global view — only a local slope, over and over.

Formal definition

Each iteration subtracts the gradient, scaled by a learning rate η, from the current parameters. The minus sign is because the gradient points uphill; η decides how far to trust it.

Plain gradient descent computes the gradient over the entire training set before each update — the average of every example's gradient, at a cost that grows linearly with the number of examples [1, §12.4.1]. That is why it is also called batch gradient descent [1, §12.5].

How it works

The learning rate is the whole difficulty. Too small and progress is glacial — each step is safe and you need thousands of them. Too large and the step overshoots the minimum, lands further up the opposite side, and can diverge [1, §12.3.1.1]. When training diverges, the learning rate is the first thing to check.

Convergence guarantees exist, but they apply to convex functions, where any local minimum is the global one [1, §12.2.2.1]. Neural network losses are not convex, so in practice gradient descent finds a good minimum, not the minimum. That turns out to be enough more often than the theory promises: "experts now suspect that, for sufficiently large neural networks, most local minima have a low cost function value" [2, §8.2.2].

Where it's used

• As the base algorithm. SGD, mini-batch SGD, momentum and Adam are all modifications of this update rule.
• Convex problems. Logistic regression and linear SVMs, where the guarantees actually hold.
• Small datasets. When the whole set fits in memory and gradients are cheap, the full-batch gradient is the least noisy direction available.
• Teaching. It is the shortest path to understanding why learning rates and loss landscapes matter.

Why & when

Reach for full-batch gradient descent when the dataset is small, the objective is convex, and you want the most stable possible descent. Every step uses all the information, so the path is smooth and reproducible.

Reach for something else on any realistic dataset. Each update costs a pass over every example, so the cost per step grows with the dataset; stochastic gradient descent reduces that cost to one example per step [1, §12.4.1], and in practice the mini-batch compromise between the two is what trains models [1, §12.5].

Worked example

import numpy as np

def loss(w):      return (w - 3.0) ** 2
def grad(w):      return 2 * (w - 3.0)

for eta in (0.1, 0.5, 0.9, 1.05):
    w = 0.0
    for _ in range(12):
        w -= eta * grad(w)
    print(f"eta={eta:<5} w={w:10.4f}  loss={loss(w):.4g}")

eta=0.1   w=    2.7938  loss=0.0425
eta=0.5   w=    3.0000  loss=0
eta=0.9   w=    2.7938  loss=0.0425
eta=1.05  w=   -6.4153  loss=88.65

The minimum is at 3.0, and each step multiplies the distance to it by 1 − 2η. At η = 0.1 that factor is 0.8: the path crawls toward 3 from one side. At η = 0.5 it is 0, and the first step lands exactly on the minimum. At η = 0.9 it is −0.8: every step overshoots to the other side (5.4, 1.08, 4.54, …), yet the distance shrinks just as fast as at 0.1, so the two end at the same place. Above η = 1 the factor's size passes 1, and at 1.05 every overshoot is larger than the last: the run has diverged to −6.4 after 12 steps.

Pitfalls

The learning rate is the first thing to check when training fails. Loss going to NaN usually means η is too large: with too large a step, "we cannot guarantee that the iteration ... will be able to lower the value" [1, §12.3.1.1].

Unscaled features make the surface a ravine. If one feature spans thousands and another spans fractions, the loss surface is a long narrow valley. The step must then be small enough not to overshoot along the steep direction, which "usually means that the step size is too small to make significant progress in other directions" [2, §4.3.1]. Scaling is not cosmetic here — it can change the number of iterations by orders of magnitude.

A fixed learning rate is a compromise. Large enough to make early progress is usually too large to settle at the end. This is what learning-rate schedules exist to fix [1, §12.11].

Convergence is to a local minimum. On non-convex problems, where you start affects where you end.