Section 1
Large data, expensive steps
How to use this pageClick any colored symbol and it explains itself. Predict first, then read on. Move each slider and watch the challenge boxes light up.
parameters and data gradients and spreads minibatch estimates the cost, the main object learning rate and minibatch size
Nearly all of deep learning is trained with stochastic gradient descent, or SGD. As in gradient descent, move the parameters a small step against the slope of the cost, and repeat. The toy model here is a line with a slope and an intercept , so = (, ).
Predict first. A pollster wants an estimate about twice as precise as one from a poll of 1,000 voters. How many voters should be sampled?
Think of a poll. A pollster does not phone all ten million voters. A random sample gives an answer that is a little off, and it arrives in a day. SGD treats the training set as the population and a small random minibatch of examples as the poll.
The race below is fair. Both methods fit the same line to the same toy examples, with the same budget, a fixed number of example gradients. Full gradient descent spends all on every step, while SGD spends only per step.
Predict first. Both methods get a budget of 20,000 example gradients, with = 16 and = 0.1. Which one ends nearer the best cost?
Same budget of work, very different numbers of steps
full gradient descentSGD with minibatch size
Look at the two curves that the demo draws. At the default budget, full gradient descent makes only 10 steps, so its line is a short orange stub. SGD makes more than a thousand steps, each one rough, and its violet curve falls quickly at the start. Near the end the violet curve stops falling and hovers. That hovering is the noise floor, and Section 4 explains it. A bigger minibatch lowers the floor, but for the same budget it buys fewer steps.
Challenge +8 XPBreak SGD. With the budget at 20,000, find a minibatch size and a learning rate where SGD ends with a larger cost gap than full gradient descent does.
The race can also fail. A tiny minibatch with a large learning rate makes each step a wild guess, and the violet curve climbs away from the minimum. Try it with the challenge above. Then move the budget and see that the answer depends on how many steps the budget buys and how far each step goes.
Section 2
The cost as a sum over examples
Each training example casts a vote on which way the line should move. The votes add up, so the cost is an average of a per-example loss , which measures how badly the parameters handle one example:
Click any coloured symbol to see what it means.
The middle form is an expectation , an average over examples each drawn with probability . Each example pairs an input with a target , so is the target of the -th example.
Predict first. A loss is large when the model gives the true answer a small probability. The model gives the true answer probability 0.9 for one example and 0.1 for another. Which pair of losses is correct?
The book defines the per-example loss in the text under Equation 5.96 as the negative log-likelihood of the target:
Click any coloured symbol to see what it means.
That is the negative logarithm of the probability that the model gives to the true answer. A confident wrong answer costs a lot.
Going deeper: the loss of a linear model with Gaussian noise
This derivation is added here and is not printed in the book. Take a linear prediction + with Gaussian noise of variance one, so that is a normal density around that prediction. The negative logarithm of a normal density with variance one is half the squared distance from its mean, plus a constant, so the loss on one example is
Click any coloured symbol to see what it means.
The constant does not depend on the parameters, so it does not change any gradient. What remains is half the squared error of the prediction.
Twelve points are fitted by a line. Drag its two ends until the votes balance. Each bar is one point's vote, and the dashed line is their average.
Per-example gradients and their average
data pointthe line, drag its endsresidual and gradient of one exampleaverage of the bars
Predict first. At the starting line the average of the slope bars is negative. If you raise a little, what happens to the cost ?
Each bar is the residual of one point, the line's prediction minus the target, times a number that belongs to the point. For the slope the number is the input, for the intercept it is 1. A point above the line gives a negative bar in the slope tab, which says the cost falls if the slope grows. When both averages are zero, no small move of the line lowers the cost, so the line is the best one for these twelve points.
Challenge +8 XPDrag the line, or use the sliders, until both averages of the bars lie between −0.1 and 0.1. Each average is the slope of the cost in one parameter.
The readout checks the averages against a numerical slope of the cost, found by nudging the parameter. The two numbers agree, which checks Equation 5.97 on this example.
Because the gradient of a sum is the sum of the gradients, the gradient of the cost is the average of the per-example gradients. This is the quantity gradient descent needs:
Click any coloured symbol to see what it means.
An exact gradient visits all examples, so one step's work is proportional to , which the book writes as . With billions of examples, one exact step is prohibitively slow.
Section 3
Minibatch estimates
Draw one minibatch and compute its gradient, then draw another. Each press gives a different number for the same slope.
The gradient in Equation 5.97 is an average over examples, and an average can be estimated from a small sample. On each step SGD draws a minibatch of examples, uniformly from the training set. The book keeps small, for example from 1 to a few hundred, as grows.
How noisy is a minibatch gradient?
per-example gradients (all )minibatch estimates true gradient
The top strip shows the gradient for the slope of each training example. The values are widely spread, so one example is a poor guide. The violet value is the average of the highlighted minibatch, the estimate . The histogram repeats the experiment 1000 times, and its center sits on the true gradient for any batch size. That center is what the next paragraphs call unbiased.
Challenge +8 XPSet the minibatch so that the spread of the estimates is at most one tenth of the spread of one example. Read both numbers in the readout.
The estimate is the same expression as Equation 5.97, with the average taken over the minibatch only:
Click any coloured symbol to see what it means.
Two properties of explain why this works. Both are derived below and are not printed in the book.
Going deeper: the estimate is unbiased
Each example in the minibatch is drawn uniformly, so the expected value of one per-example gradient is the average over the whole training set, which is . The expected value of a sum is the sum of the expected values, so the expectation of the average of such terms is the same number:
Click any coloured symbol to see what it means.
On average the estimate points exactly where the full gradient points. A single estimate can be wrong in either direction, but it is not wrong in a consistent direction.
The second property concerns the spread. Let be the spread of one per-example gradient. An average of independent draws has a spread that is smaller by the factor :
Click any coloured symbol to see what it means.
Going deeper: why the spread falls with the square root
This derivation is added here and is not printed in the book. The variance of a sum of independent draws is the sum of their variances. Each draw has variance , so the average of draws has variance , and its spread is the square root of that. The argument assumes draws with replacement, which is what the demo does. Without replacement the spread is smaller by a factor close to 1 whenever the minibatch is small compared with the training set.
Predict first. You double the minibatch from 16 to 32. The spread of the estimates of the slope becomes:
Two consequences follow. A hundred examples give an estimate about ten times less noisy than one example. And does not appear next to anywhere: the quality of the estimate depends on the minibatch, not on the size of the data it was drawn from.
Now slide the parameter to its best value, where the true gradient is zero. The estimates still scatter around zero, and their width is far from zero. The noise does not vanish when the parameters become good. This is the root of the behavior in the next section.
Section 4
The update and a constant learning rate
SGD follows the estimated gradient downhill, just as gradient descent follows the true one:
Click any coloured symbol to see what it means.
The book states that is the learning rate, a positive number that sets how far each step goes. A bigger moves faster and risks overshooting, and a smaller one is safer and slower. In this section the rate stays constant. Try it in the demo: set to 0.55 and watch both methods, then bring it back under 0.5.
Noisy descent into a valley
SGDfull gradient descent, same ratepredicted floor
The contour lines show the cost for the line, in the plane of its slope and intercept. The valley is long and narrow, because the two parameters trade off against each other. Full gradient descent (orange) follows a smooth path. SGD (violet) is jagged, reaches the valley floor, and then jitters there. Keep the rate at 0.12 and watch the violet curve settle above the golden floor line.
Challenge +8 XPWith the decay box unticked, set the learning rate to 0.2 or more and bring the average cost gap over the last 100 steps below 0.004. At a rate of 0.2, a minibatch of 128 or more lowers the floor enough.
With a constant rate there are two phases. Far from the minimum the true gradient is large compared with the noise, and the steps make steady progress. Near the minimum the true gradient shrinks towards zero, but the minibatch gradient does not. The parameters then wander in a small cloud around the minimum. This wandering is the noise floor. The name is ours, and the book does not use it.
Predict first. SGD with a constant learning rate has reached the valley. From there its cost:
The formula says three things. The floor doubles when doubles, and halves when the minibatch size doubles. And the floor is the same at every step once the run has settled, so a constant rate never reaches the exact minimum. The stability limit is 2 divided by the largest curvature of this valley, which is about 3.8, so full gradient descent diverges above a rate of about 0.53.
Going deeper: where the noise floor comes from
This derivation is added here and is not printed in the book. Near the best parameters , the cost is approximately a bowl, with curvature matrix , and the minibatch gradient is times the distance from the best point plus noise of covariance . Let be the covariance of the parameters once they have settled. One step of SGD gives a steady state where the decay of cancels the new noise, which leads to
Click any coloured symbol to see what it means.
Take the trace of both sides. The left side becomes two times the trace of , and the trace of is twice the average excess cost. So the average gap above the best cost is
Click any coloured symbol to see what it means.
The formula is a first-order estimate, valid for a small learning rate. The golden line in the demo uses the next order in each curvature direction, which is a factor larger when the rate is not small.
Challenge +8 XPBreak it. With the decay box unticked, set the learning rate above 0.53 and watch full gradient descent diverge.
Read the readout as an estimate. With a minibatch of 16 or more and a rate of 0.12 or more, the measured floor was between 0.73 and 1.58 times the prediction. With a minibatch of 4, rates of 0.12 and 0.3 gave 1.4 to 1.7 times, and a rate of 0.45 was unstable. With a minibatch of 1 and a rate of 0.3 or more, the formula does not apply. A rate of 0.05 with a minibatch of 64 or 256 has not settled after 400 steps, and was up to six times the prediction.
Section 5
Cost that does not grow with the data
Predict what happens to the work of training as the data grows. Then count it.
For a fixed model size, one SGD update reads examples, so its cost depends on and not on the training set size . The book notes that the number of updates needed usually grows with , and then argues that the growth stops. So the asymptotic cost of SGD training is as a function of .
Going deeper: why the growth stops
The book argues that, as becomes very large, the model reaches its best possible test error before SGD has sampled every example. Past that point more data does not lengthen training, which is why the asymptotic cost is constant in . The argument is the book’s, and the toy below only illustrates it.
Predict first. In the toy below, the training set grows from 1,000 to 1,000,000 examples, and the minibatch is held fixed. The number of updates needed for a fixed accuracy:
How many updates does SGD need?
updates neededupdates in one pass over the data,
Challenge +8 XPWith a minibatch of 64 or less and a learning rate near 0.08, make SGD reach the target for the largest training set, 1,000,000 examples, in fewer than 300 updates.
Each point is one full SGD run to a fixed accuracy on new data, for a training set of the size shown. The smallest sets are unreliable, and hollow markers show runs that never reached the target. For the larger sets, with the default settings, the number of updates is almost the same for every size, while the examples read in one pass keep rising. This toy has two parameters, so it illustrates the book's argument without proving it for deep networks.
Predict first. Kernel methods store a table with one entry for each pair of training examples. If the training set doubles from 1,000 to 2,000 examples, how much larger does the table become?
Many kernel methods build a table of similarities between every pair of training examples. The book writes it as , with entries , the kernel that scores how similar two inputs are. The table is not numbered in the book:
Click any coloured symbol to see what it means.
A table with rows and columns has entries, so building it costs . On a log scale the full step rises with the data, the kernel matrix rises twice as fast, and the SGD step stays flat.
Counting work as the data grows
full gradient step, SGD step, kernel matrix,
Going deeper: a historical note on gradient descent
Gradient descent was long regarded as slow or unreliable, and applying it to non-convex problems, costs with many valleys and hills, was seen as unprincipled. Today the models of Part II are known to train well with it. The method is not guaranteed to reach even a local minimum in reasonable time, but it often finds a very low value of the cost quickly enough to be useful. SGD is also the main way to train large linear models on very large datasets. In academia, deep learning first drew interest from 2006, because it generalized better than competing methods on medium-sized datasets of tens of thousands of examples. Industry followed because it offered a scalable way to train nonlinear models on huge datasets. Chapter 8 describes SGD and many enhancements to it.
What to take away
- The cost is an average of per-example losses, so its gradient is their average (5.96, 5.97). One exact step costs .
- A minibatch of examples gives an unbiased estimate (5.98), whose spread shrinks like .
- SGD steps against (5.99). With a constant it hovers at a noise floor proportional to and inversely proportional to .
- One update does not depend on the training set size, unlike a kernel table of entries.
Final quizCheck 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 5.9 (pages 151–153), 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.