Skip to content
wannacode

Gradient descent

In short: Gradient descent finds the weights of a model step by step: it works out which way the error grows and moves the weights a little the other way, as far as the learning rate says.

Problem

The best line, without guessing

The colleagues in the linear regression lesson picked a line by eye. Now the warehouse wants the program to find the best one by itself. There is an exact formula only for the line, and the next models (neural networks) have none. We need a way that always works.

The task is smaller for now: the warehouse is known (6 hours), and we only look for how many hours each 100 km add, w. The distance is in hundreds of km so that the numbers are small:

// distance in hundreds of km (0.3 is 30 km) and hours to delivery
double[] dist = [0.3, 0.5, 0.8, 1.0, 1.3, 1.6, 2.0, 2.4, 2.7, 3.0];
double[] hours = [10, 11, 17, 17, 23, 24, 31, 33, 40, 44];
const double B = 6; // the warehouse: 6 hours, it is known
const double Nudge = 0.0001;

The loss is the same MSE as in linear regression, now only a function of w:

// the MSE of the line hours = w · distance + 6
double Loss(double w)
{
    double sum = 0;
    for (var i = 0; i < dist.Length; i++)
    {
        var error = w * dist[i] + B - hours[i];
        sum += error * error;
    }
    return sum / dist.Length;
}

We could try w = 0, 1, 2, … up to 100 and take the smallest loss. With one w that works. With 10 weights that is 100¹⁰ tries, and a neural network has millions of weights.

The idea

Nudge and see

Instead of trying everything, stand at one w and ask: if I move a little to the right, does the loss drop or grow?

var before = Loss(0);
var after = Loss(0.01);
Console.WriteLine($"w = 0: loss {before:F2}");
Console.WriteLine($"w = 0.01: loss {after:F2}");
Console.WriteLine($"slope: {(after - before) / 0.01:F2}");
Output
w = 0: loss 485.00
w = 0.01: loss 484.21
slope: -78.97

Nudging by 0.01 lowered the loss by 0.79. Divided by the nudge, that is the slope: −78.97, how much the loss changes per unit of w. The minus means "right is downhill".

With a smaller nudge (0.0001) the slope is more exact. Here it is at four places:

// the slope: nudge w and see how much the loss changes
double Slope(double w) =>
    (Loss(w + Nudge) - Loss(w)) / Nudge;
foreach (double w in new double[] { 0, 6, 12, 18 })
{
    Console.WriteLine($"w = {w}: loss {Loss(w):F2}, slope {Slope(w):F2}");
}
Output
w = 0: loss 485.00, slope -79.00
w = 6: loss 127.21, slope -40.26
w = 12: loss 1.83, slope -1.53
w = 18: loss 108.87, slope 37.21

The slope says two things. The sign is the direction: minus means w must grow, plus that it must shrink (at w = 18 we have already passed the bottom). The size is how far we are: −79 is far from the bottom, −1.53 is almost at the bottom.

The idea

A step against the slope

The rule is one line: w -= rate · slope. Against the slope, because the slope points uphill. With a negative slope this increases w, with a positive one it decreases it. The steeper, the bigger the step.

One pass (compute the slope, take a step) is an epoch. We repeat:

double w = 0;
var rate = 0.1;
for (var epoch = 1; epoch <= 10; epoch++)
{
    w -= rate * Slope(w);
    Console.WriteLine($"epoch {epoch}: w = {w:F2}, loss {Loss(w):F2}");
}
Output
epoch 1: w = 7.90, loss 62.36
epoch 2: w = 10.70, loss 9.28
epoch 3: w = 11.69, loss 2.61
epoch 4: w = 12.04, loss 1.77
epoch 5: w = 12.17, loss 1.67
epoch 6: w = 12.21, loss 1.65
epoch 7: w = 12.23, loss 1.65
epoch 8: w = 12.23, loss 1.65
epoch 9: w = 12.24, loss 1.65
epoch 10: w = 12.24, loss 1.65

The first step is big (from 0 to 7.90) because the curve is steep. Near the bottom the slope gets smaller, and so do the steps: from epoch 7 on, w hardly moves. The loss of 1.65 is smaller than the 1.83 of the line the colleagues picked by eye.

This is gradient descent: step by step down the slope of the loss until you reach the bottom. "Gradient" is the slope when there is more than one parameter.

See it

The ball on the curve

double Slope(double w) =>
    (Loss(w + Nudge) - Loss(w)) / Nudge;


double w = 0;
var rate = 0.1;
for (var epoch = 1; epoch <= 10; epoch++)
{
    w -= rate * Slope(w);
}
Step by step, in words
  1. Below: the loss for every w; the ball starts at w = 0. Above: the line with this w.
  2. Nudge w a little: the loss drops. The slope is -79.00: downhill is to the right.
  3. One step: w -= 0.1 · (-79.00), so w becomes 7.90. Against the slope, so downhill.
  4. Each pass is an epoch. The slope gets smaller near the bottom, and so do the steps. After 10: w = 12.24.
  5. Rate 0.01: the grey ball crawls. After 10 epochs it is only at w = 5.96.
  6. Rate 0.35: the red ball jumps over the bottom, every time higher. The loss grows: it diverges.
  7. With 0.1 the ball sits at the bottom: w = 12.24, loss 1.65. Nobody guessed w: it was found.

Below is the loss for every w, and the ball is the current w. Above is the line with this w over the orders: when the ball reaches the bottom, the line goes through the points. The grey and the red ball are the same rule with another rate.

The idea

The learning rate

The number the slope is multiplied by is the learning rate. It decides how long the step is. Three rates, 20 epochs each (w after the first three and after the twentieth):

foreach (var rate in new[] { 0.01, 0.1, 0.35 })
{
    double w = 0;
    var seen = new List<string>();
    for (var epoch = 1; epoch <= 20; epoch++)
    {
        w -= rate * Slope(w);
        if (epoch <= 3 || epoch == 20) seen.Add($"{w:F2}");
    }
    Console.WriteLine($"rate {rate:F2}: w = {string.Join(", ", seen)}, loss {Loss(w):F2}");
}
Output
rate 0.01: w = 0.79, 1.53, 2.22, 9.02, loss 35.14
rate 0.10: w = 7.90, 10.70, 11.69, 12.24, loss 1.65
rate 0.35: w = 27.65, -7.18, 36.69, -1224.61, loss 4938139.70
  • 0.01 is too small. The direction is right, but after 20 epochs w is only 9.02. It reaches the bottom, but after hundreds of epochs.
  • 0.1 is right. Three steps and w is close, then it settles at 12.24.
  • 0.35 is too big. The first step overshoots the bottom to 27.65. There the slope is even bigger, the next step is even longer and w flies to −7.18, then to 36.69. The loss becomes millions: descent diverges.

A good rate is not computed, it is tried. It is common to start with 0.1 or 0.01 and watch the loss by epoch: if it grows or jumps, the rate is too big; if it barely drops, it is too small.

The idea

w and b together

Until now b was known. Now we look for it too: each parameter has its own slope (you nudge only that one), and each takes its own step in the same epoch.

// the MSE of the line hours = w · distance + b
double Loss(double w, double b)
{
    double sum = 0;
    for (var i = 0; i < dist.Length; i++)
    {
        var error = w * dist[i] + b - hours[i];
        sum += error * error;
    }
    return sum / dist.Length;
}
double w = 0, b = 0, rate = 0.1;
for (var epoch = 1; epoch <= 1000; epoch++)
{
    var slopeW = (Loss(w + Nudge, b) - Loss(w, b)) / Nudge;
    var slopeB = (Loss(w, b + Nudge) - Loss(w, b)) / Nudge;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 1 || epoch == 10 || epoch == 100 || epoch == 1000)
        Console.WriteLine($"epoch {epoch}: w = {w:F2}, b = {b:F2}, loss {Loss(w, b):F2}");
}
Output
epoch 1: w = 9.77, b = 5.00, loss 29.77
epoch 10: w = 12.21, b = 6.03, loss 1.66
epoch 100: w = 12.41, b = 5.65, loss 1.62
epoch 1000: w = 12.41, b = 5.64, loss 1.62

After 1000 epochs w = 12.41 hours per 100 km and b = 5.64 hours. The formula for the best line from linear regression gives 0.1241 hours per km and 5.64 hours: the same line. Descent does not know the formula; it just goes downhill.

The idea

The scale of the features

Why was the distance in hundreds of km? Here are the same orders in km:

// the same orders, but the distance is in km
double[] km = [30, 50, 80, 100, 130, 160, 200, 240, 270, 300];
double[] hours = [10, 11, 17, 17, 23, 24, 31, 33, 40, 44];
const double Nudge = 0.0001;

With a rate of 0.1, descent diverges from the first epoch:

double w = 0, b = 0, rate = 0.1;
for (var epoch = 1; epoch <= 3; epoch++)
{
    var slopeW = (Loss(w + Nudge, b) - Loss(w, b)) / Nudge;
    var slopeB = (Loss(w, b + Nudge) - Loss(w, b)) / Nudge;
    w -= rate * slopeW;
    b -= rate * slopeB;
    Console.WriteLine($"rate 0.1, epoch {epoch}: w = {w:F0}");
}
Output
rate 0.1, epoch 1: w = 977
rate 0.1, epoch 2: w = -6304921
rate 0.1, epoch 3: w = 40699231079

The slope for w grows with the size of the feature: every w is multiplied by 300 instead of 3, and at w = 0 the slope is almost −10,000. So we lower the rate until it stops diverging:

double w = 0, b = 0, rate = 0.00002;
for (var epoch = 1; epoch <= 1000; epoch++)
{
    var slopeW = (Loss(w + Nudge, b) - Loss(w, b)) / Nudge;
    var slopeB = (Loss(w, b + Nudge) - Loss(w, b)) / Nudge;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 10 || epoch == 100 || epoch == 1000)
        Console.WriteLine($"epoch {epoch}: w = {w:F4}, b = {b:F4}, loss {Loss(w, b):F2}");
}
Output
epoch 10: w = 0.1513, b = 0.0013, loss 9.44
epoch 100: w = 0.1513, b = 0.0063, loss 9.42
epoch 1000: w = 0.1510, b = 0.0563, loss 9.28

Now it does not diverge, but b hardly moves: after 1000 epochs it is 0.06 instead of 5.64, and w sits at 0.151 instead of 0.124. For b the step is too small. One rate does not suit both. The fix is scale: the features are brought to a similar range before training (here dividing by 100; often you subtract the mean and divide by the spread). Without that no rate does the job.

Try it

Predict the output

w is 2, the slope there is −20, and the rate is 0.1. What will one step print?

double w = 2;
double slope = -20;
var rate = 0.1;
w -= rate * slope;
Console.WriteLine($"{w:F1}");
Answer

Try it

Fill in

Which operation takes the step against the slope?

for (var epoch = 1; epoch <= 10; epoch++)
{
    w  rate * Slope(w);
}

Try it

Find the bug

A colleague writes descent, but the loss by epoch grows faster and faster. Which line has the bug?

Pick the line with the bug.

The idea

When descent hurts

  • The wrong rate. Too big diverges, too small crawls. If the loss by epoch grows or jumps, lower the rate first.
  • Features on different scales. km and the number of parcels in one line: the slopes differ hundreds of times and no rate fits. Scale the features before training.
  • Not just one valley. The loss of a line is one smooth bowl with one bottom. For neural networks the curve has many valleys and plateaus: descent reaches some bottom, not necessarily the lowest, and the result depends on the starting w.
  • When to stop. Here the epochs are fixed. In practice you stop when the loss stops dropping, and whether the model is good for new orders is measured separately (evaluating the model).
  • The cost. Every epoch goes through all the data. With millions of examples and millions of weights, training runs for hours on special servers; that infrastructure (training machines, running the model in production) is taught in the DevOps course ZeroToOps.
More precisely, if you are curious

The slope by formula. Nudging is an approximation. For the MSE the slope has an exact formula (the derivative): 2 · the mean of error · distance. Here are both ways side by side:

// the slope by formula: 2 · the mean of error · distance
double SlopeByFormula(double w)
{
    double sum = 0;
    for (var i = 0; i < dist.Length; i++)
    {
        var error = w * dist[i] + B - hours[i];
        sum += error * dist[i];
    }
    return 2 * sum / dist.Length;
}
foreach (double w in new double[] { 0, 12 })
{
    Console.WriteLine($"at w = {w}: by numbers {Slope(w):F2}, by formula {SlopeByFormula(w):F2}");
}
Output
at w = 0: by numbers -79.00, by formula -79.00
at w = 12: by numbers -1.53, by formula -1.53

They agree to the second digit. The formula is faster (one pass instead of two per parameter), which is why libraries compute derivatives automatically from the model's code. That is backpropagation, from the lesson on training a network.

The gradient. With many parameters, their slopes together are the gradient (a vector). The step is the same for each: parameter -= rate · its slope.

Parts of the data. With millions of examples one epoch is slow. So the slope is computed on a small random part (a mini-batch) and there are many more steps. This is stochastic gradient descent (SGD). Its improved versions (Adam, for example) also keep a "momentum" of the previous steps.

Exercise

The courier, learned by itself

Solve the task in your editor.

In the linear regression lesson the colleagues compared three lines for the courier's price. Now let the program find the best one by itself:

// parcels: weight in kg and the courier price in €
double[] kg = [0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0, 6.0];
double[] eur = [4.10, 4.60, 5.00, 5.60, 6.40, 7.50, 8.30, 9.40];
const double Nudge = 0.0001;

Write the loss function (MSE) for price = w · kg + b, then 1000 epochs of gradient descent for w and b together, from w = 0 and b = 0, with a rate of 0.05 and a nudge of 0.0001. Print w, b and the loss with 4 digits each.

Output
w = 0.9538, b = 3.6204, MSE 0.0038

More tasks

  • The rate. Run it with a rate of 0.1. What happens? Find the biggest rate at which the loss still drops.
  • Stopping. Instead of 1000 epochs, stop when both slopes are smaller than 0.001 in absolute value. After how many epochs?
  • Comparison. How much smaller is the loss than the colleagues' best line (A, MSE 0.0144)?

Test

Check yourself

1. The slope of the loss at the current w is −40. Which way should w move?
2. With a rate of 0.35, w jumps to 27.65, −7.18, 36.69, and the loss grows. What do you do?
3. With a rate of 0.01, w is 5.96 after 10 epochs, and the bottom is around 12. Is the rate wrong?
4. Why does descent diverge with the distance in km (30 to 300) at a rate that works with hundreds of km (0.3 to 3)?
5. Descent for the delivery line reaches w = 12.41 and b = 5.64. The formula from linear regression gives 0.1241 h/km and 5.64 h. Why use descent at all?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·