How Learning Differs from Pure Optimization

The goal and the number you can compute

Picture a driving instructor who wants a student to drive well on every road in the country. The instructor cannot test every road, so the test runs on the streets around the training car park. The car-park score is the number the instructor can compute. The country-wide skill is the thing that matters. Training a deep network has the same shape: the goal is hidden, and training minimizes a number that can be computed.

Two numbers do this work. The first is the performance measure , the quantity you care about, such as accuracy on new data. It is defined on data you have never seen, and it is often too hard to optimize directly. The second is the training cost , which is an average of the loss over the training examples. The loss measures how wrong one prediction is. A model is a function , which maps an input and the parameters to a prediction. Training changes to make the cost small, and hopes that the performance measure improves with it.

The book writes the two costs as expectations. The training cost averages over the empirical distribution , which puts equal weight on each training example:

The goal is the same average taken over the true data generating process , the process that produced the examples in the first place. The book calls this the risk:

In words, is the expected loss of the model with parameters on a fresh example from the world. is the same quantity measured on the examples you happen to hold. The two agree on average, and they differ by an amount that depends on how many examples you hold.

The gap between the two curves

In the demo below the world produces values from a Gaussian with mean 2 and standard deviation 1. The loss is the squared error for predicting the constant . The true risk is smallest at . The training cost is smallest at the average of the sample you drew, which is close to 2 but not equal to it. Drag the sample size and draw new samples.

Try this before you move on. Draw several samples at , then at . The training minimum jumps around at small sizes and settles near 2 at large sizes. The distance between the two minima shrinks as the sample grows. The book does not print this rate. The step that gives it is added here and is not printed in the book: the sample average of values with standard deviation 1 has standard deviation , so the gap is about that size. Check it against the readout over a few draws.

Empirical risk and overfitting

The simplest way to turn a learning problem into an optimization problem is to replace the true distribution by the training set. Minimizing the average loss over the training examples is called empirical risk minimization. The average runs over examples, and indexes them.

The book calls this quantity the empirical risk. Minimizing it is still an optimization problem, but it differs from the goal in one important way. A model with high capacity, meaning it can represent many functions, can fit the training examples exactly and still be wrong on new ones. Capacity is the number of different shapes the model can take. The model has memorized the training set rather than learned the pattern in it. This failure is overfitting.

The book gives a second reason. Many useful losses, such as the 0-1 loss that counts mistakes, have no useful derivative. Its derivative is either zero or does not exist everywhere, so gradient descent has nothing to follow. For both reasons, deep learning rarely minimizes the empirical risk directly. The next section explains what it does instead. The demo below shows overfitting on a small fitting problem: fit a polynomial of growing degree to fifteen noisy points, and compare the error on the training points with the error on fresh points.

The true curve is a sine wave, and each point adds Gaussian noise of standard deviation 0.2. The error is the mean squared difference between the fit and the noisy data values. The training error is measured on the fifteen points the fit saw. The test error is measured on two hundred fresh points from the same process. The error on the training points never rises as the degree grows, while the test error falls for a few degrees and then rises. That rise is overfitting in one picture.

Move the degree up slowly from 3, then past 9, and watch which curve turns back up. The lowest test error is the best degree for this problem. Choosing the degree on the test points would be cheating, which is why a separate validation set exists. Section 3 returns to this point.

Surrogate losses and early stopping

The loss you care about is often not the loss you can optimize. Take classification. The number that matters is the fraction of mistakes, which is the 0-1 loss. Minimizing its expectation exactly is typically intractable, even for a linear classifier. So training optimizes a surrogate loss, a smooth stand-in with better properties. The usual choice is the negative log-likelihood of the correct class. It makes the model estimate class probabilities, and if the model estimates them well, it can pick the classes that give the least classification error in expectation.

A surrogate can also keep learning after the real loss has stopped moving. The book notes that the test 0-1 loss often keeps falling after the training 0-1 loss reaches zero, when the log-likelihood surrogate is used. Pushing the classes further apart gives a more confident classifier. The demo below uses the margin , which is positive when the example is classified correctly. It compares the 0-1 loss with the logistic surrogate .

The 0-1 loss is a step: 1 for a mistake and 0 for a correct answer. Its slope is zero everywhere it is defined, so it gives no signal. The surrogate is smooth, and its slope is , which is never zero. A margin of 3 gives a 0-1 loss of 0 and a surrogate of about 0.049. The surrogate still falls as the margin grows, so the training signal survives even when the mistakes have stopped.

Where training halts

Training does not run until the gradient vanishes. The book describes the usual rule: the algorithm halts when a convergence criterion based on early stopping is met. That criterion is measured on held-out validation data with the true loss, such as the 0-1 loss, and it halts when overfitting starts. The surrogate may still have a large derivative when it stops. The demo below plots a training curve and a validation curve. The two curves are made-up shapes for illustration, and their derivatives are computed exactly from their formulas. In this toy the training slope is already small near the stopping point, so the demo shows where the validation curve turns up. It does not show a large surrogate derivative.

Minibatch estimates of the gradient

The cost is a sum over the training set. Many properties of it are sums too. The book gives the maximum likelihood estimate as the maximiser of a sum of log probabilities, one term per example, and the same sum appears as an expectation under :

The most used property is the gradient of that expectation, which is an average of per-example gradients:

Computing that average exactly means evaluating the model on every example in the dataset, which is expensive. The fix is to sample a few examples and average over them. The sample average is an estimate of the gradient, and it changes from one sample to the next. How good is it? If one example's gradient has standard deviation , the average of independent ones has standard deviation . This is the standard error of the mean. The book writes the sample count as n in its Equation 5.46. Quadrupling the sample halves the error. That gives the book's remark that the returns are less than linear.

Take two estimates, one from 100 examples and one from 10,000. The second costs 100 times as much, and its error is only 10 times smaller. Most optimization algorithms converge much faster in total computation, not in number of updates, when they are allowed quick, approximate gradients than when they compute the exact gradient slowly. Redundancy in the data adds a further argument. If all examples were identical copies, one sample would give the exact gradient at a fraction of the cost. Real datasets are rarely that redundant, but many examples often make similar contributions.

Three names describe how many examples a method uses per update. Batch (or deterministic) methods use the whole training set. Stochastic methods use a minibatch or a single example. Online learning is the case where examples arrive from a stream and each one is seen once. On this page, batch size always means the size of a minibatch, not the full set.

Each dot is one minibatch gradient. Its height is random and only spaces the dots out. The true gradient is 1, and each example contributes noise with standard deviation 2. If each example's noise is Gaussian, the average of such examples is Gaussian, centered on 1 with spread , so the dots are drawn from that distribution. Drawing the average directly gives the same distribution of dots as summing separate examples, and it costs far less to draw. For other noise shapes the average is only approximately Gaussian when is large.

Minibatch size and shuffling

A minibatch is an unbiased estimate of the true gradient when its examples are drawn independently from the data generating distribution. Successive minibatches should also be independent of each other. The book gives the exact-gradient version of this claim for discrete data. The true gradient of the generalization error is a sum over all possible examples weighted by :

A minibatch of fresh samples gives the unbiased estimate of this gradient, written with the average over the batch:

That estimate follows the gradient of the generalization error only while no example is reused. Most implementations shuffle the dataset once and make several passes over it. On the first pass each minibatch is fresh. On later passes the estimate reuses examples, so it is no longer a fair sample of the data generating distribution. The book adds that with very large datasets, a single pass or an incomplete pass may be enough, because overfitting is then no longer the main concern.

Shuffling matters because the order of the training data can carry structure. Imagine a dataset of blood tests stored patient by patient. Taking consecutive blocks gives minibatches that come mostly from one patient. Each one points at that patient, not at the population. The demo below shows the same eight patients in recorded order and in shuffled order.

In recorded order, each batch of six examples belongs to one patient, so its estimate jumps between the patients' values. In shuffled order, every batch is a mix, and its estimate stays near the full gradient. Both orders give the same average over a full pass, because each example is used once and the batches are the same size. The difference is the path. A biased path can carry the parameters somewhere a fair sample would not.

Minibatch size as a checklist

The book lists the forces that set the batch size. Use these as a checklist, not as a rule:

• Accuracy. Larger batches estimate the gradient better, but with less than linear returns.
• Hardware. Multicore machines are underused by very small batches, so there is a practical minimum. Memory grows with the batch, and on GPUs powers of two from 32 to 256 often run faster.
• Regularization. Small batches add noise that can help generalization. The book notes that generalization error is often best at a batch size of 1, which then needs a small learning rate to stay stable.
• Algorithm. Methods that use only the gradient handle batches of about 100. Second-order methods that use the Hessian need far larger batches, around 10,000, because multiplying by the inverse Hessian amplifies errors in the gradient estimate when the Hessian is poorly conditioned.

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.1 (pages 275–281), 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.