Gradient Descent

The blind search that becomes impossible

When we have only two dials and try a hundred positions for each, we get ten thousand combinations. A modern computer runs through them in an instant — that is exactly how the automatic search in lesson 11 worked. But what happens when the model has ten dials? The number of combinations leaps to a hundred billion billion.

And today’s great language models have hundreds of billions of parameters. Trying at random or testing every combination is no longer merely slow but physically impossible: the number of attempts would far exceed the number of atoms in the observable universe.

We are obliged to fall back on a far wiser and more modest strategy: we start from some point and make small adjustments, using only the clues we can gather right where we stand. This method is called gradient descent (or gradient descent). It is exactly as if you stood on a mountain wrapped in dense fog: you cannot see the village in the valley, but if you feel with your feet that the ground falls away to the left, you take a cautious step in that direction.

The slope of a single dial

Let us simplify: we leave one dial quite still and play only with the other. At that moment the cost becomes a simple curve — one value of the error for each position of the active dial. In reality we do not know that curve in advance in its entirety; to draw it beforehand would mean testing every position, exactly the waste we want to avoid.

All we can find out is strictly local. We move the dial a fraction of a millimetre to the left, then a fraction to the right, and compare the two costs. The difference tells us at once which way the ground falls and how fast the error drops. That measure — by how much the error changes for a minute movement of one parameter — is the slope or, in mathematical language, the the derivative. You need no complicated formulas to understand it: the derivative is simply the tilt of the ground you feel under your feet.

When both feet come to the same horizontal level, the slope becomes zero: any movement one way or the other would mean climbing. There you have reached the bottom of the valley for that dial.

The gradient: the compass that shows the way

Every dial has its own slope, measured independently, holding the others still. If we put all these tilts together, we obtain a single arrow pointing in the direction in which the cost rises most steeply. That combined arrow is called the gradient.

If we have two dials, the gradient is an arrow on a flat map. If we have a billion dials, the gradient is still a mathematical arrow, only it lives in a space of a billion dimensions. The human mind cannot picture such a space, but the algorithm has no need to see it: it needs only the numbers of that arrow.

The golden rule is charmingly simple: we take the step exactly against the arrow. We compute the gradient at the point where we stand, take a small step downhill against it, recompute the slope in the new place and repeat the process.

The two axes of the landscape are drawn at different scales, because otherwise the valley would not fit in the picture. For that reason the arrow does not look perpendicular to the contour lines, although in the true units it is. The section on the scale of the quantities shows that this stretching is not merely an accident of the drawing.

The length of the step: the learning rate

How large should the step downhill be? This is the one critical decision the data cannot take by itself; it must be chosen by a human. It is called the learning rate (or learning rate).

If the rate is too small, the steps are tiny and cautious; the descent is correct, but it may take an eternity. If the rate is too large, the step becomes a huge leap: you jump over the bottom of the valley and land on the opposite slope, higher than you started. Carry on like that and you leap ever more chaotically from side to side, and the error explodes in a few seconds. The art of training neural networks is, to an enormous degree, the art of tuning this step size with mastery.

Why the scale of the quantities matters (normalisation)

Press the button “Normalise the scales” in the figure. That button changes the units of measure: instead of raw distances in tens of kilometres, we express every distance as a departure from the average of all the journeys. The final model and the best line stay absolutely unchanged; only the numbers written on the dials change.

Look, though, at what happens to the relief: in raw kilometres the valley was a long, narrow, distorted canyon. A small turn of the slope threw the error into the air, while the starting height barely moved anything. The descent keeps striking the steep walls, advancing in a slow, tortured zigzag. When we bring the data to the same scale, the canyon becomes an almost perfectly round bowl. The steps head straight for the bottom of the valley.

The number of steps needed drops tenfold or even a hundredfold. Here is a precious lesson: the same data and the same model may reach the solution either in an instant or after hours of torment, purely from the way the numerical scales are calibrated before training.

The trap of many valleys and mountain saddles

The smooth landscape with a single valley that we have explored so far exists because our model is a simple straight line. As soon as we build more expressive models, the relief turns rugged, full of hills, deep valleys and local hollows. A ball let roll may stop in the first pit it meets, never reaching the deepest valley.

This problem looks discouraging, but in practice spaces of thousands or millions of dimensions hold a pleasant surprise for us: genuinely isolated valley bottoms are surprisingly rare. Most flat regions are in fact “mountain saddles” (places that rise in one direction but fall in others). What is more, even if the algorithm stops in a secondary valley, in huge models the quality of the solution there is almost as good as in any other reasonable valley.

What the descent looks like at real scale

To understand how real artificial intelligence systems work, it is worth revealing three simplifications we have used in the demonstrations above:

First, the slopes are not measured by “feeling” dial by dial. If a model has a billion parameters, feeling would ask for two billion computations for a single step. In practice the slopes of all the parameters are computed at once, from a single backward pass through the model — the ingenious mechanism called backpropagation, which we shall discover in lesson 17.

Second, the landscape does not stand still. In real training on millions of texts or images, the cost is computed at each step on only a small parcel of examples picked at random. This is called stochastic descent (SGD). The landscape sways slightly at every step and the road is bumpier; but that noisy movement is a blessing: it helps the ball jump out of the small accidental pits and carry on downhill.

Finally, the bottom of the valley on the known data is not the ultimate target. The descent finds the ideal setting for the examples it has already seen. But how will the model fare on entirely new examples it has never met? That is the great challenge of overfitting, which we shall explore in the very next lesson.