Gradient Descent

The four hand steps are what a paper asks for. At w = 10 the slope is 14, so the step is 0.2 * 14 = 2.8 and w becomes 7.2. The loss falls from 51 to 19.64. Each step the slope is smaller, so the step is smaller, and the descent slows as it approaches the bottom without being told to.

That automatic slowing is the property worth naming. Nothing schedules it: the slope IS the distance from the minimum here, so the step shrinks in proportion. By step 30 w is 3.000002 and the slope is 0.000003.

The learning rate, in both directions

Read the last table, because every row is a different failure or success.

0.001 is too small. After 30 steps w has moved from 10 to 9.59. It is going the right way and will take thousands of steps.

0.2 arrives, to six decimal places, in 30 steps.

1.0 oscillates forever. From w = 10 the slope is 14 and the step is 14, landing at -4. From -4 the slope is -14 and the step takes it back to 10. It never diverges and it never converges; it jumps between the two points forever, and the table shows it exactly back at 10 after 30 steps.

1.05 diverges. Each step overshoots by slightly more than it came, so w grows without bound: 125.1 after 30 steps, and the loss is 14,921.

There is a threshold and for this loss it is exactly 1.0. Below it the method converges; at it the method cycles; above it the method diverges. For a general quadratic loss the threshold is 2 divided by the curvature, and the practical consequence is the one to remember: a loss that is sharply curved in some direction forces a small rate on every direction, which is why real optimisation uses the refinements below.

The three variants, which is what a paper asks for

The loss in machine learning is a sum over the training examples, and the variants differ in how many examples are used per step.

The reason mini-batch wins is worth one sentence: a noisy estimate of the gradient computed a hundred times is worth far more than an exact one computed once, because the errors partly cancel while the hundred steps make real progress.

One epoch means one complete pass through the training data. It is the unit training is usually reported in, and it is not the same as a step.

Why it does not always find the best answer

Three honest limits, and a paper can ask for any.

Local minima. On a loss with several valleys, gradient descent settles in whichever one it started above. The loss in this chapter is convex, a single valley, so the starting point does not matter; a neural network's loss is not, and the starting point does matter.

Saddle points and plateaus. Places where the gradient is nearly zero but the point is not a minimum. In many dimensions these are far more common than local minima, and they stall progress without stopping it.

It needs the loss to be differentiable. A loss with a jump in it has no gradient at the jump. This is why classification is usually trained on a smooth surrogate such as cross-entropy rather than directly on the number of mistakes, which is a step function and has zero gradient almost everywhere.

The standard refinements, named

None is on MU's label and all four appear in any library, so one line each.

• Momentum: add a fraction of the previous step to this one, so the parameter keeps moving in a consistent direction and crosses flat regions faster.
• AdaGrad, RMSProp: give each parameter its own rate, scaled down for parameters whose gradients have been large, so one sharply curved direction no longer forces a small rate on all of them.
• Adam: momentum and a per-parameter rate together. It is the usual default.
• A learning rate schedule: start large and reduce the rate over time, so early steps are fast and later ones settle.

Where it appears in the rest of this book

The cross-chapter list, because this is the one method that recurs.

And the one place it is not used: the straight line of What Machine Learning Is has a closed-form solution, so nothing is iterated. Gradient descent is what you use when there is no formula, and most models in this module have none.

Distinctions

What it does not mean

The gradient does not point at the minimum. It points in the direction of steepest increase at the current point, and the step is the opposite direction. On a long narrow valley that is nearly across the valley rather than along it.

A zero gradient does not mean a minimum. It may be a maximum, a saddle point or a plateau.

A smaller learning rate is not safer in every sense. It cannot diverge, and it may never arrive.

Gradient descent does not need the loss to be the error. It minimises whatever differentiable function it is given, which is how the penalty of Regularization is included: add it to the loss and its gradient joins the step.

Stochastic gradient descent is not an approximation to be apologised for. Its noise helps it escape shallow minima, and many small noisy steps beat one exact one.

It is not always necessary. A closed-form solution, where one exists, is exact and faster.

Quick revision

• Update rule: w <- w - rate * gradient. Subtracting the slope moves downhill whichever way the slope points.
• The gradient is the vector of partial derivatives, one per parameter.
• Four hand steps from w = 10 at rate 0.2: slope 14 gives 7.2, then 5.52, 4.512, 3.9072, with the loss falling 51, 19.64, 8.35, 4.29, 2.82. The steps shrink by themselves because the slope shrinks.
• Learning rate: 0.001 crawls, 0.2 arrives, 1.0 oscillates between 10 and -4 forever, 1.05 diverges to 125.1. The threshold here is exactly 1.0, and in general 2 / curvature.
• Variants: batch (all examples, exact, slow), stochastic (one, noisy, fast), mini-batch (a group, and what is actually used). One epoch is one pass over the data.
• Limits: local minima on a non-convex loss, saddle points and plateaus, and the loss must be differentiable, which is why classification uses a smooth surrogate.
• Refinements: momentum, AdaGrad and RMSProp, Adam, learning rate schedules.
• Used to fit the perceptron, a neural network by backpropagation, the hinge loss, maximum likelihood where no closed form exists, and the Q-learning update. Not used where a closed form exists.

Test yourself

1. State the update rule and explain why subtracting the gradient moves downhill. w <- w - rate * gradient. The gradient is the slope, which points uphill: positive slope means the low ground is to the left and negative slope means it is to the right. Subtracting therefore moves left when the slope is positive and right when it is negative, which is downhill in both cases.

2. Work the first two steps for f(w) = (w - 3)2 + 2 from w = 10 with a rate of 0.2.** The slope is 2(w - 3). At w = 10 it is 14, so the step is 2.8 and w becomes 7.2, where the loss is 19.64. At 7.2 the slope is 8.4, so the step is 1.68 and w becomes 5.52, where the loss is 8.3504.

3. Why do the steps get smaller without anything scheduling them? Because the step is the rate times the slope, and the slope shrinks as the minimum is approached. For this loss the slope is exactly twice the distance from the minimum, so the step shrinks in proportion to how far there is still to go.

4. Describe what happens at learning rates of 0.001, 1.0 and 1.05 on this loss. At 0.001 it converges correctly but far too slowly, reaching only 9.59 after thirty steps. At exactly 1.0 it jumps from 10 to minus 4 and back forever, neither converging nor diverging. At 1.05 each step overshoots by more than it came, so the parameter grows without bound, reaching 125.1 after thirty steps.

5. Distinguish batch, stochastic and mini-batch gradient descent, and say which is used. Batch uses every training example for each step, giving the exact gradient at high cost. Stochastic uses one example, giving a very noisy direction very cheaply. Mini-batch uses a small group, giving a reasonable direction at moderate cost, and it is what is used in practice, because many approximate steps make more progress than one exact one.

6. Give three reasons gradient descent may fail to find the best answer. On a non-convex loss it settles in whichever valley it started above, so the starting point decides the result. It stalls at saddle points and plateaus where the gradient is nearly zero but the point is not a minimum. And it requires a differentiable loss, so a loss such as the count of mistakes, which is a step function, cannot be used directly.

7. Why is the straight line of the first chapter not fitted by gradient descent? Because least squares for a linear model has a closed-form solution, which gives the exact answer in one calculation. Gradient descent is for losses with no formula, which is the case for almost every other model in this module.