Basic Algorithms

Stochastic gradient descent

Gradient descent follows the gradient of the whole training set downhill. It can be made much faster by following the gradient of a randomly selected minibatch instead. The book calls the result stochastic gradient descent, or SGD, and it says SGD and its variants are probably the most used optimization algorithms for machine learning in general and deep learning in particular. Section 8.1 showed that a minibatch of examples drawn independently from the data generating distribution gives an unbiased estimate of the gradient.

The book's Algorithm 8.1 is the complete update. At each training iteration it does the following:

1. Requires a learning rate at iteration , and an initial parameter .
2. Samples a minibatch of examples, with their targets.
3. Computes the gradient estimate, the average of the per-example gradients over the minibatch.
4. Applies the update , and repeats until a stopping criterion is met.

The book's Algorithm 8.1 is written with for the estimate, and the update applies it directly. The step is one gradient estimate with learning rate . The estimate is the sample average, so its noise does not vanish as the parameters approach a minimum.

That last point is the reason the learning rate must change over time. The book explains that the random sampling of minibatches introduces noise that does not vanish even at a minimum. The true gradient of the total cost becomes zero at a minimum, so batch gradient descent can keep a fixed learning rate. SGD cannot do the same without something to damp its noise. The demo below shows the effect on a simple quadratic. The gradient of is , and the minibatch adds noise with standard deviation . The demo sets .

Run the demo at a fixed learning rate and watch the path. It moves toward zero, then keeps wandering around it. The width of the wandering depends on the learning rate and the batch size. The readout measures the spread over the last 200 steps. It also gives the spread predicted by a short calculation, which is added here and is not printed in the book: the stationary spread is .

Larger batches reduce the noise, but only in proportion to the square root of the batch size. The book notes that the per-step cost of SGD does not grow with the number of training examples, which is why it works for very large datasets.

Learning rate schedules

The book states a sufficient condition for SGD to converge. The learning rates must sum to infinity so that the parameters can travel any distance, and the sum of their squares must stay finite so that the noise is damped:

A common choice that is practical is to decay the learning rate linearly until iteration , and then leave it constant. The schedule has one more symbol in the book: the fraction is , which is a different quantity from the momentum parameter in Section 4. The book uses the same letter for both:

The book gives advice for the three parameters. It suggests that can be set to the number of iterations needed for a few hundred passes through the training set, and that should be roughly one percent of . The main question is how to set . If it is too large, the learning curve shows violent oscillations and the cost can rise. If it is too small, learning is slow and may get stuck at a high cost. The book recommends monitoring the first few iterations and choosing a rate higher than the best one after about 100 iterations, but not so high that it causes severe instability. The book also says this is more an art than a science.

The demo runs 1000 steps of SGD on the quadratic from the first section, with minibatches of ten. The constant-rate run keeps the initial rate, and the decay run follows Equation 8.14. The readout gives the spread over the last 200 steps for both. Lower the final rate and watch the decay run settle, while the constant run keeps its wandering width.

Convergence rates

To study how fast an algorithm converges, the book measures the excess error , which is how far the current cost is above the lowest possible cost. For a convex problem, the excess error of SGD is after iterations. For a strongly convex problem it is . The book says these bounds cannot be improved unless extra conditions are assumed.

Batch gradient descent has better convergence rates in theory. The book then gives two reasons why the rate does not decide the matter. The Cramér-Rao bound says generalization error cannot decrease faster than . Bottou and Bousquet argue that it may not be worthwhile to pursue an algorithm that converges faster than , because faster convergence can correspond to overfitting. The book also notes that SGD makes rapid initial progress, evaluating very few examples per step, which outweighs its slow asymptotic rate on large datasets.

The demo below uses a quadratic with noise of standard deviation 1 in the gradient. It applies the learning rate with a constant , and computes the exact variance of the parameter from its recursion, which is added here and is not printed in the book. The excess error is half that variance. For it settles to a rate of , the same law the book describes.

The book's bounds are about the rate in , not the constant. The constant in the demo changes how big the excess error is at a given step, but not the shape. The book's advice is about practice: on large datasets, the rapid early progress of SGD, from evaluating very few examples per step, outweighs its slower asymptotic rate.

Momentum

SGD can be slow. The method of momentum, due to Polyak (1964), is designed to speed up learning in the face of high curvature, small but consistent gradients, or noisy gradients. It accumulates an exponentially decaying average of past gradients and keeps moving in their direction. The book calls the quantity that does this the velocity , the direction and speed at which the parameters move. The parameter in [0, 1) decides how quickly the contributions of previous gradients decay. The book gives the update rule as Equations 8.15 and 8.16:

The velocity accumulates the gradient, and the parameters move by the velocity. The larger is relative to , the more previous gradients affect the current direction. The book's Algorithm 8.2 is the same update written out, with the minibatch gradient computed first, then the velocity, then the parameters.

Figure 8.5 in the book shows the effect on a quadratic with a poorly conditioned Hessian, a long narrow valley with steep sides. Gradient descent zigzags across the valley. Momentum traverses it lengthwise. The demo below uses a stand-in quadratic of its own, with curvatures 0.2 and 2, and both paths start from the same point. At the slider settings gradient descent cannot zigzag, because a step of at most 0.45 is too small to overshoot the steep direction, so the stand-in does not reproduce Figure 8.5. At the default settings momentum oscillates across the steep direction instead.

The readout gives the distance from the minimum after 60 steps for both methods. The two methods differ only in the velocity term, so the comparison isolates momentum. With a large the path can overshoot and oscillate, so momentum is not always closer. The challenge asks for a setting where momentum ends closer.

Terminal velocity and the physical picture

The size of the step with momentum is no longer the learning rate times the gradient. It depends on how large and how aligned a sequence of gradients is. The book says the step is largest when many successive gradients point the same way. If the momentum algorithm always sees the gradient , it accelerates in the direction of minus until it reaches a terminal velocity where each step has size

The book says it is helpful to think of the momentum parameter in terms of . For the maximum speed is ten times the speed of gradient descent. The book's formula has no learning rate in it. A learning rate of one recovers it, which is a reading added here and is not printed in the book. The demo below keeps the learning rate in the formula. The terminal speed is then , which is added here and is not printed in the book.

The book describes momentum as a physical system. The position of a particle is , and the net force accelerates it. The book introduces the velocity and writes Newton's equations as a first-order system:

The momentum algorithm solves these equations by simulation, with Euler's method, which takes small finite steps in the direction of each gradient. One force is proportional to the negative gradient of the cost, which pushes the particle downhill. A second force is needed. Without it the particle would oscillate forever on a frictionless surface. The book adds a force proportional to minus the velocity, which is viscous drag, as if the particle moves through syrup.

Nesterov momentum

Sutskever et al. (2013) introduced a variant of momentum inspired by Nesterov's accelerated gradient method. The only change is where the gradient is evaluated. Standard momentum evaluates it at the current parameters. Nesterov momentum first applies the current velocity, then evaluates the gradient at that interim point. The book gives the update as Equations 8.21 and 8.22:

The book interprets Nesterov momentum as adding a correction factor to standard momentum. Algorithm 8.3 writes it as an interim update , a gradient at that interim point, a velocity update, and a parameter update.

The book states the convergence results. In the convex batch case, Nesterov momentum improves the excess error from after steps to , as shown by Nesterov (1983). In the stochastic gradient case it does not improve the rate of convergence. The demo below compares the two methods on a one-dimensional quadratic, which is a stand-in written for this page, and counts the steps each one needs to bring the parameter within 0.01 of zero.

The readout gives the step at which each method first reaches a distance below 0.01, if it does within 3000 steps. The outcome depends on the settings. For some values the Nesterov path reaches zero sooner, and for others the standard path does. The book gives the theory for the convex batch case, not this stand-in, so the comparison here is only an illustration.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 8.3 (pages 294–300), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.