ML Explorer · Level 2 · Learning from data
Gradient descent
Gradient descent finds the bottom of a loss by taking small steps downhill, again and again.
Overview
Lesson 6 found the best line with a formula. Most models have no such formula. They are trained by gradient descent instead: start somewhere, look at the slope of the loss, take a small step downhill, and repeat.
This lesson uses the same 25 points as Lesson 6, so you can check that walking downhill ends at the same line the formula gave.
The points are made up. See "About the data" at the end.
You'll learn
- how the slope of the loss tells the model which way to move and how far, and why the steps shrink near the bottom on their own
- what the learning rate does when it is too small or too big
- why a bowl-shaped loss is easy, and what can go wrong on a bumpy one
-
One number to learn
To see gradient descent clearly, we give the model just one number to learn: the slope of a line, called w. Every w has a loss, and together they make a curve.
We take Lesson 6's points and centre them: subtract the mean of x from every x, and the mean of y from every y. The cloud keeps its shape, but its centre moves to (0, 0).
Lesson 6 showed that the least-squares line passes through the point of means. After centring, that point is (0, 0), so the best line goes through it. Only its slope is left to find. The model is ŷ = w·x.
Each w gives one line, drawn on the right, and one loss: its mean squared error (MSE) from Lesson 4. Plot the loss for every w and you get the curve L(w). Move the slider to try different values of w.
The curve is a bowl with one lowest point. Lesson 4 said the squared loss is smooth, so the curve has a slope at every w.
Learning one number is a simplification for this lesson. Real models learn many numbers at once; Lesson 8 learns two.
The maths
Write the centred values as and . The loss is the MSE of the line :
Multiplying out the square and completing the square in gives a parabola:
Here is the population variance of x (divide by ), is Lesson 6's least-squares slope , and is the smallest loss.
For these points = , = and = , which is the MSE of Lesson 6's least-squares line.
-
The slope says which way is downhill
At the current w, the slope of the loss curve says which way is downhill. Move w the opposite way to the slope's sign.
The violet line touches the curve at the ball. Its slope is the slope of the loss at that w, written L′(w).
Left of the bottom, the slope is negative, so downhill is to the right. Right of the bottom, it is positive, so downhill is to the left. This is the rule from Lesson 5: the sign of the slope tells you which way is downhill.
The slope also says how steep the curve is. Far from the bottom it is steep. Near the bottom it is close to 0. Move the slider and watch both change.
The maths
Differentiating the parabola from step 1:
Its sign is the sign of : negative left of the bottom, positive right of it, and 0 only at .
A computer does not know in advance, so it works the slope out from the data instead. The same slope, written that way, is
-
Take a step downhill
The slope tells the model which way is downhill. It moves its weight a little in that direction, then checks the slope again.
Each step replaces w with w − η × slope. The learning rate η (the Greek letter eta) is a small positive number that sets the size of the steps.
Subtracting η × slope moves w against the slope's sign, which is downhill. The size of the move is η times how steep the curve is.
Here η = . Press "Take a step" a few times. The faded dots are earlier positions and the dashed arcs are the hops. "Start again" puts the ball back at w = .
Repeating this step until w stops moving is gradient descent.
The maths
Starting from a first guess , step gives
The step is . Because , it always has the opposite sign to the slope (or is 0 where the slope is 0).
-
The steps shrink by themselves
Keep stepping and the steps get shorter near the bottom, even though η never changes.
Each step is η times the slope. Near the bottom the slope is close to 0, so the step is close to 0 too. Nothing tells the model to slow down: the curve flattens, and the steps follow.
The chart on the right shows w after each step. It closes in on w*, the bottom of the bowl. "Run again" replays the run.
Left to run until its steps are smaller than 10⁻¹⁰, gradient descent takes steps and ends at w = . Lesson 6's formula gave the slope = . They agree to four decimal places.
So this is Lesson 6's line. Centring lets gradient descent find the same slope as least squares, and the intercept comes back from the means. On the original scale the line is ŷ = ȳ + w(x − x̄), so its intercept is ȳ − w·x̄ = . Lesson 6 gave = . This holds as long as η is in the stable range shown in step 5.
The maths
Write for how far w is from the bottom after steps (negative when it is to the left). Then , and subtracting from both sides of the update gives
Call the bracket . Every step multiplies by the same number , so after steps it is . The step itself is long, so it shrinks at the same rate.
With η = , = : each step keeps that fraction of the distance that was left.
In the original units,
With the intercept is , Lesson 6's formula.
-
Too small, too big
The learning rate decides whether the walk settles. Too small, and it crawls. Too big, and it overshoots the bottom; bigger still, and the overshoots grow.
The slider runs on a log scale, from η = to : moving it the same distance always multiplies η by the same amount. The left chart and the right chart both show up to the first steps. The slider has a stop at exactly each of the two boundaries below.
- Below η = : steady. w moves towards the bottom from one side. At the low end it is slow, and steps cover only part of the way. At exactly the first step lands right on the bottom.
- Between and : zig-zags but settles. Each step jumps past the bottom, but by less each time.
- At exactly : never settles. w jumps back and forth between two points at the same distance from the bottom, for ever.
- Above : diverges. Each jump lands further away than the last, and, given enough steps, w runs off the chart. The ball is held at the edge and the page says so.
The boundaries come from the data: the more spread out x is, the steeper the bowl and the smaller η must be. With other data they move.
The maths
From step 4, the distance to the bottom after steps is with . So:
- : , the distance shrinks and keeps its sign (steady).
- : , it shrinks and flips sign each step (zig-zags but settles).
- : , it keeps its size and flips sign (never settles).
- : , it grows and flips sign (diverges).
A curiosity: at exactly , and the first step lands on . That works only because this loss is an exact parabola whose curvature we know.
These exact boundaries hold for a loss that is a perfect parabola. For other smooth losses the picture is similar close to a minimum, but the boundaries are no longer exact.
-
One bottom, or many dips?
On a bowl-shaped loss like this one, walking downhill leads to the lowest point. On a bumpy loss it can stop in a dip that is not the lowest.
A curve shaped like a bowl, one that never bends downwards, is called convex. On a convex curve, any bottom you reach is the lowest point of all, the global minimum. This lesson's loss is convex, so with η in the stable range gradient descent closes in on w* from any starting w.
The small curve on the right is a different, made-up curve, not this lesson's loss. It has two dips. Started on the right, gradient descent walks downhill into the nearer dip and stops there, because the slope is 0 at its bottom. It never finds the lower dip on the left.
A dip that is lowest only in its own neighbourhood is called a local minimum. The losses of neural networks (deep learning) are usually not bowl-shaped, so there gradient descent can stop in a local dip rather than at the lowest point.
The maths
A curve with a second derivative is convex when that second derivative is never negative. Here everywhere, as long as x varies.
The inset curve is
so for , and it is not convex there.
Gradient descent starts at with η = 0.05 and stops at = , where = . The lowest point is at = , where = .
Quick check
Lesson complete
- Gradient descent repeats one move: w becomes w − η × slope. The slope's sign gives the direction, downhill.
- With η fixed, the steps shrink near the bottom because the slope does. On these centred points it finds the same slope as least squares, and so Lesson 6's line.
- Too small an η is slow. Too large, and w zig-zags; larger still, and it runs away. On a bowl it ends at the lowest point; on a bumpy loss it can stop in a local dip.
Common misconceptions
- "A bigger learning rate always learns faster." Only up to a point. Past it the steps overshoot, and further still they grow without end.
- "The model slows down on purpose near the bottom." Here η stays fixed. The steps shrink because the slope shrinks.
- "Gradient descent always finds the best answer." On a convex loss with a stable η it closes in on it. On a bumpy loss it can stop in a local dip.
Further reading
- Goodfellow, Bengio & Courville, Deep Learning, Section 4.3, "Gradient-Based Optimization", which introduces gradient descent and the learning rate, and the difference between local and global minima.
- Deisenroth, Faisal & Ong, Mathematics for Machine Learning, Section 7.1, "Optimization Using Gradient Descent", and Section 7.3, "Convex Optimization".
About the data. The 25 points are Lesson 6's made-up points. They come from a seeded random number generator, mulberry32 with seed 11. For each point in turn, x is drawn uniformly between 0 and 10, and then y = 4 + 1.5x plus 2 times a random draw from a normal distribution with mean 0 and SD 1. This lesson subtracts the mean of x from every x and the mean of y from every y before fitting. Every run starts at w = −0.5. Steps 3 and 4 use η = 0.03; the slider in step 5 runs from 0.001 to 2.5 divided by the population variance of x. The bumpy curve in step 6 is a made-up formula, not data. The stage shows values to two decimal places and learning rates to three significant figures; the calculations use unrounded values.
If this helped, you can .