Skip to the lesson
ML Explorer Reju Sam John

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.

About 12 minutes · No maths needed; the maths is there if you want it

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
  1. 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 x~i=xi−xˉ\tilde{x}_i = x_i - \bar{x} and y~i=yi−yˉ\tilde{y}_i = y_i - \bar{y}. The loss is the MSE of the line y^=w x~\hat{y} = w\,\tilde{x}:

    L(w)=1n∑i=1n(y~i−w x~i)2L(w) = \frac{1}{n}\sum_{i=1}^{n} \left(\tilde{y}_i - w\,\tilde{x}_i\right)^2

    Multiplying out the square and completing the square in ww gives a parabola:

    L(w)=σx2 (w−w∗)2+L(w∗)σx2=1n∑i=1nx~i2w∗=∑ix~i y~i∑ix~i2=SxySxx\begin{aligned} L(w) &= \sigma_x^2\,(w - w^*)^2 + L(w^*) \\ \sigma_x^2 &= \frac{1}{n}\sum_{i=1}^{n} \tilde{x}_i^2 \\ w^* &= \frac{\sum_i \tilde{x}_i\,\tilde{y}_i}{\sum_i \tilde{x}_i^2} = \frac{S_{xy}}{S_{xx}} \end{aligned}

    Here σx2\sigma_x^2 is the population variance of x (divide by nn), w∗w^* is Lesson 6's least-squares slope b^\hat{b}, and L(w∗)L(w^*) is the smallest loss.

  2. 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:

    L′(w)=2 σx2 (w−w∗)L'(w) = 2\,\sigma_x^2\,(w - w^*)

    Its sign is the sign of w−w∗w - w^*: negative left of the bottom, positive right of it, and 0 only at w=w∗w = w^*.

    A computer does not know w∗w^* in advance, so it works the slope out from the data instead. The same slope, written that way, is

    L′(w)=−2n∑i=1nx~i(y~i−w x~i)L'(w) = -\frac{2}{n}\sum_{i=1}^{n} \tilde{x}_i\left(\tilde{y}_i - w\,\tilde{x}_i\right)
  3. 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.

    Repeating this step until w stops moving is gradient descent.

    The maths

    Starting from a first guess w0w_0, step kk gives

    wk+1=wk−η L′(wk)w_{k+1} = w_k - \eta\,L'(w_k)

    The step is −η L′(wk)-\eta\,L'(w_k). Because η>0\eta > 0, it always has the opposite sign to the slope (or is 0 where the slope is 0).

  4. 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.

    The maths

    Write dk=wk−w∗d_k = w_k - w^* for how far w is from the bottom after kk steps (negative when it is to the left). Then L′(wk)=2σx2 dkL'(w_k) = 2\sigma_x^2\,d_k, and subtracting w∗w^* from both sides of the update gives

    dk+1=dk−2η σx2 dk=(1−2η σx2) dk\begin{aligned} d_{k+1} &= d_k - 2\eta\,\sigma_x^2\,d_k \\ &= (1 - 2\eta\,\sigma_x^2)\,d_k \end{aligned}

    Call the bracket qq. Every step multiplies dkd_k by the same number qq, so after kk steps it is dk=qk d0d_k = q^k\,d_0. The step itself is 2η σx2 ∣dk∣2\eta\,\sigma_x^2\,|d_k| long, so it shrinks at the same rate.

    In the original units,

    y^=yˉ+w (x−xˉ)=(yˉ−w xˉ)+w x\begin{aligned} \hat{y} &= \bar{y} + w\,(x - \bar{x}) \\ &= (\bar{y} - w\,\bar{x}) + w\,x \end{aligned}

    With w=w∗=b^w = w^* = \hat{b} the intercept is yˉ−b^ xˉ=a^\bar{y} - \hat{b}\,\bar{x} = \hat{a}, Lesson 6's formula.

  5. 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 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 kk steps is qk(w0−w∗)q^k(w_0 - w^*) with q=1−2η σx2q = 1 - 2\eta\,\sigma_x^2. So:

    • 0<η<1/(2σx2)0 < \eta < 1/(2\sigma_x^2): 0<q<10 < q < 1, the distance shrinks and keeps its sign (steady).
    • 1/(2σx2)<η<1/σx21/(2\sigma_x^2) < \eta < 1/\sigma_x^2: −1<q<0-1 < q < 0, it shrinks and flips sign each step (zig-zags but settles).
    • η=1/σx2\eta = 1/\sigma_x^2: q=−1q = -1, it keeps its size and flips sign (never settles).
    • η>1/σx2\eta > 1/\sigma_x^2: q<−1q < -1, it grows and flips sign (diverges).

    A curiosity: at exactly η=1/(2σx2)\eta = 1/(2\sigma_x^2), q=0q = 0 and the first step lands on w∗w^*. 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.

  6. 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 L′′(w)=2σx2>0L''(w) = 2\sigma_x^2 > 0 everywhere, as long as x varies.

    The inset curve is

    h(u)=0.25 u4−u2+0.3 u+2h′′(u)=3u2−2\begin{aligned} h(u) &= 0.25\,u^4 - u^2 + 0.3\,u + 2 \\ h''(u) &= 3u^2 - 2 \end{aligned}

    so h′′(u)<0h''(u) < 0 for ∣u∣<2/3|u| < \sqrt{2/3}, and it is not convex there.

Quick check

What happens if the learning rate η is too large?

Bigger steps help only up to a point. Past it, w jumps past the bottom, and past a second point it never settles at all.

Right. In step 5, η above the first boundary makes w zig-zag past the bottom, and η above the second makes each jump bigger than the last.

Local dips come from the shape of the loss, not from η. This lesson's loss is a bowl with no local dips, yet a large η still fails.

The step is η times the slope, so η scales every step. The slope sets the direction and steepness; η sets how far to go.

With η fixed, why do the steps get shorter near the bottom?

In this lesson η never changes. Some training methods do lower η on a schedule, but the shrinking here happens without that.

Right. The step is η × slope. As the bowl flattens towards its bottom, the slope shrinks, and so does the step.

It is the other way round. The bowl is steepest far from the bottom and flat at the bottom itself.

Every step here uses all 25 points. The steps shrink because the slope does.

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.
Next lesson: Many features and the loss surface →

Further reading

  1. 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.
  2. 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 .