Try this first

You are standing somewhere on a hillside in thick fog. You cannot see anything. You want to reach the lowest point of the valley.

You can feel the ground under your feet. That is all. Write down the procedure you would follow, in three steps or fewer, before reading on.

The procedure

Almost everyone writes some version of this. Feel which way the ground slopes down. Take a step that way. Do it again.

That is gradient descent. There is nothing else to it. The rest of this section is spent on three questions the procedure leaves open:

  • How do you find which way is down, when you cannot see?
  • How big should the step be?
  • When do you stop?

Notice what the procedure does not need. It never asks for a map. It only ever uses the ground within one step of where you are standing. That matters more than it sounds like it should. In lesson 3050 you drew the whole map and it cost 172,800 evaluations of the loss for two parameters. Feeling the ground costs a handful, and the cost does not explode when the landscape gets bigger.

Walking downhill without any calculus

You can already write this. Try both directions and go whichever way is lower.

function step(f, x, size) {
  const here  = f(x);
  const left  = f(x - size);
  const right = f(x + size);
  if (left < here && left <= right) return x - size;
  if (right < here) return x + size;
  return x;
}

const bowl = x => (x - 3) * (x - 3) + 1;

let x = 9;
for (let i = 0; i < 40; i++) {
  x = step(bowl, x, 0.25);
  log(i, x.toFixed(3), bowl(x).toFixed(3));
}

Three evaluations per step: where you are, one to the left, one to the right. If the left is lower and no worse than the right, move left. If the right is lower, move right. If neither improves, you are at the bottom, so stay.

Run it. The value slides from 9 down to 3 and then stops moving. It found the minimum of the bowl without knowing anything about the bowl.

0 3 6 9 0 25 50 x f(x) f(x − h) f(x) f(x + h) you are standing here left is lower, so step left fog: never measured
The walker never sees the bowl. It sees three numbers, and the lowest one decides the next step. That is why the cost does not grow when the landscape does.

Why we do not stop here

This works and it is honest. It also gets expensive in a way that is easy to miss. One parameter needs two probes per step. Two parameters need four. A model with a million parameters needs two million probes to take one step, and then it has to take thousands of steps.

So we want the slope directly, at the cost of a single look, rather than by trial. That is what the next two lessons are for.

What to watch

The step size is fixed at 0.25, so the walker cannot land closer than that to the true minimum. It arrives near 3 and then oscillates or halts, depending on where it started. A fixed step gives you a fixed floor on your accuracy, and lesson 8 of this section is about getting around that.

Exercises

  1. Start at x = 9 with a step of 2. Does it still find the bottom? Explain what you see in terms of the width of the bowl.
  2. Change bowl to x => Math.abs(x - 3) + 1. Does the walker still work? This is the V from lesson 3047.
  3. Count the calls to f for a run of 40 steps. Then work out the count for two parameters, and for a hundred.
  4. Add a stopping rule: halt when a step does not move x. How many steps did it actually need?
PreviousNext