Try first

Everything in this section has worked. That is because the landscape has been a single bowl every time.

Here is one that is not.

const wiggly = x => 0.1 * x * x + Math.sin(x * 3) * 2;

Plot it from -8 to 8. Then predict: if you run gradient descent from x = -6 and again from x = 5, do you get the same answer?

Local minima

function descend1d(f, x, lr = 0.05, steps = 2000) {
  for (let i = 0; i < steps; i++) x -= lr * slopeAt(f, x);
  return x;
}

for (const start of [-6, -3, 0, 2, 5, 7]) {
  const end = descend1d(wiggly, start);
  log("from", start, " to", end.toFixed(3), " value", wiggly(end).toFixed(3));
}

Six starting points, several different answers. Each run settled into whichever dip it happened to be standing over, and none of them had any way to know a better dip existed a little further along.

This is the central limitation. Gradient descent only ever looks at the ground under its feet, which is what made it cheap. It finds a local minimum: a point with nothing lower nearby. Whether that is the lowest point overall is a question it never asks.

Linear regression is safe from this. Squared error on a linear model always gives a single bowl, which is why sections 3 and 4 went smoothly. Neural networks are not safe from it at all.

Flat ground

const plateau = x => Math.tanh(x) * Math.tanh(x);
log(descend1d(plateau, 6, 0.05, 5000).toFixed(4));
log(slopeAt(plateau, 6).toExponential(3));

Start at 6 and the slope is about 5e-5. Multiply that by the learning rate and each step moves you a few millionths. Five thousand of them take it from 6 to 5.99. The walker is on ground that slopes down, and it is stuck anyway, because the rule moves you in proportion to the steepness and the steepness has run out.

There is no error and the loss barely moves. It looks exactly like being finished. This is the vanishing gradient problem, it is the main reason deep networks were hard to train for many years, and lesson 3101 is about the fix.

-8 -4 0 4 8 0 4 8 x f(x) six starts, six different answers the best dip 0 4 8 0 1 x tanh(x)² downhill, but stuck slope 4.9e-05 5000 steps move it from 6.00 to 5.99
Gradient descent only reads the ground under its feet. That is what made it cheap, and it is also why it cannot tell a local dip from the best one, or a slow hill from a finish line.

Saddle points

With two or more parameters, a third possibility appears: ground that falls away in one direction and rises in another, like a horse’s saddle. Right at the center the gradient is zero in every direction, so the update rule stops.

In high dimensions these outnumber local minima by a wide margin. For a point to be a local minimum, every one of a million directions must go up. For a saddle, one direction going up is enough. Modern thinking is that large networks are mostly slowed by saddles and plateaus rather than trapped in bad minima.

What people actually do

None of these are solved. They are managed.

  • Start in several places and keep the best result. Crude and effective.
  • Add noise. Using a small random sample of the data for each step, rather than all of it, makes the steps jitter enough to leave shallow dips. That is stochastic gradient descent, in lesson 3099.
  • Add momentum. Carry some velocity from previous steps so the walker rolls through small dips and across flat ground instead of stopping in them.
  • Choose activation functions with useful slopes, which is what lesson 3101 is about.

Worth being clear about where this leaves you. Nobody can prove a trained network found the best possible parameters, and it almost certainly did not. In practice a good local minimum is usually good enough, and the whole field runs on that observation holding up.

What to watch

When training stalls, the loss curve looks the same whether you are in a minimum, on a plateau, or at a saddle. Print the size of the gradient too. A large gradient with a stuck loss means the learning rate is wrong. A gradient near zero means the landscape has flattened out, and no learning rate will help.

Exercises

  1. Run descend1d on wiggly from a hundred random starts. How many distinct answers, and which is best?
  2. Add momentum: keep v = 0.9 * v - lr * slope and update with x += v. Does it escape any of the dips?
  3. On plateau, find the starting point beyond which the walker no longer makes progress in 5000 steps.
  4. Sketch a two parameter function with a saddle at the origin. You need one squared term positive and one negative.
PreviousNext