Optimization Strategies and Meta-Algorithms

Sorting the strategies

Section 8.7 collects strategies that make deep networks easier to train. They do not all change the same thing. Some change the model, some change the optimizer, some change the starting point or the objective, and some change what is reported at the end. The book does not use these four groups. They are added here so that each strategy can be placed before the details arrive.

The sorting is a useful habit for the rest of the section. A method that changes the model can also change the optimization problem, as batch normalization does in Section 8.7.1. Keep the four groups in mind as the sections below add one strategy each.

Batch normalization

Think about a plain chain of layers with one unit each and no activation function, so that the output is and each layer multiplies by its weight . The output is a linear function of the input but a nonlinear function of the weights. A gradient step changes every weight at once, and the effects of those changes multiply. The book writes the new output as Equation 8.34:

Every factor changes at once, so the products create second-order and higher-order terms. In a deep network those terms can be very large or very small, which makes the learning rate hard to choose. Batch normalization reparametrizes the network so that the statistics of each unit stay under control. The demo below shows the chain first.

The book sets the learning rate so that a first-order prediction says the output falls by a fixed amount, here 0.1. The exact change differs from that prediction, because the second-order terms of Equation 8.34 enter the update. The gap is small for small steps and grows quickly as the step gets larger.

Batch normalization fixes the statistics of a layer. For a minibatch of activations with one row per example, the layer is replaced by the standardized version of Equation 8.35. The mean and the standard deviation are computed for each unit over the minibatch, with examples:

The small positive value is in the book, and it avoids a case where the gradient of the square root does not exist at zero. The gradient flows through the mean and the standard deviation as well, so the update cannot increase them directly. The book notes that it is common to replace the normalized activations with , where and are learned. This keeps the expressive power of the layer, because and can set any mean and standard deviation.

The readout shows the raw mean and standard deviation of the eight values, then the mean and standard deviation after the normalization and the rescaling. The rescaling is added here as a demo control, and the statistics it produces follow directly from Equation 8.35 and the text.

The book also says the statistics should use the minibatch during training and running averages at test time. Each unit is standardized on its own, so the layer does not need the whole training set in one pass.

Coordinate descent

Coordinate descent minimizes an objective with respect to one variable at a time, then the next, and cycles through all of them. If the variables separate into groups that play isolated roles, each block can be solved quickly. The book's example is sparse coding, where a weight matrix decodes a code that reconstructs the training data :

The objective is not convex in both and together. Each block is convex when the other is fixed, so the algorithm alternates between the two blocks and uses efficient convex solvers for each. The book also warns that coordinate descent is weak when one variable strongly controls the best value of another. The example below is the book's case.

The first term pulls the two variables together, and the second pulls both towards zero. For a small each coordinate step is small, because the first term does not allow one variable to move far from the other. The readout counts the sweeps by simulation. This count is added here and is not printed in the book.

Newton’s method solves this problem in one step, because the objective is a positive definite quadratic. The book uses this to contrast the two methods.

Polyak averaging

Polyak averaging averages several points on the trajectory of an optimizer. The average of the first points is the mean of the points visited so far. The book writes it inline, without a number, and it is shown here as a display:

On some convex problems, averaging has strong convergence guarantees. For neural networks the justification is heuristic, but the book reports that it performs well in practice. The basic idea is that an optimizer can leap across a valley without visiting points near its bottom, while the average of the points on both sides stays close to the bottom.

For non-convex problems the book prefers an exponentially decaying running average, because points from the distant past may be separated from the current point by large barriers. The running form is Equation 8.39:

The toy valley has curvature 20 across the valley. It is made for this page and is not taken from the book. Across the valley the raw iterate is multiplied by at each step, so with it swings from side to side with a factor of minus 0.8. The readout compares the running average with the raw iterate after the chosen number of steps.

The readout also gives the formula for the ratio, which is added here and is not printed in the book. It is valid only while is smaller than . Near that value the simulated average stops following the formula, and the readout reports the simulated number.

Supervised pretraining

Sometimes a complex model is too hard to train directly on a difficult task. The book describes pretraining: first train a simpler model on a simpler task, then make the model more complex. Greedy algorithms solve one component at a time, and a joint fine-tuning stage can then improve the full solution. Greedy supervised pretraining breaks a supervised problem into simpler supervised problems, and each stage adds one hidden layer.

The figure shows the stages in the book. Panel a trains a shallow network. Panel b redraws the same network. Panel c keeps the input-to-hidden weights, drops the output layer, and adds a second hidden layer trained with the same objective. Panel d views the result as a feed-forward network, and the book adds that all layers can then be fine-tuned together, either at the end or at each stage. The parameter counts in the stepper are for an example with four inputs, six hidden units and one output. They are added here and are not printed in the book.

The book explains the hypothesis behind greedy pretraining: it gives better guidance to the intermediate levels of a deep hierarchy. The hypothesis is that pretraining helps both optimization and generalization. The book also describes FitNets, where the student network learns from hints on a middle layer of a teacher.

Designing models to aid optimization

The book makes a strong point here: the best strategy is not always a better optimizer. Many advances came from changing the model family. Modern networks use linear transformations between layers and activation functions with a useful slope over most of their domain. A linear function increases in one direction, so the gradient points towards a better output even when the output is far from correct.

Skip connections are another design choice. They reduce the length of the shortest path from a lower layer’s parameters to the output, which mitigates vanishing gradients. The demo below counts that path. The gain per hop is a toy number, added here so that the path length is visible, and it is not taken from the book.

With one skip connection every layers, the shortest path has hops. The readout reports that count and compares the toy gain after the hops with the gain across all layers. The count is added here and is not printed in the book.

Auxiliary heads are a related idea. Extra copies of the output are attached to intermediate layers and trained on the same task, which gives the lower layers a larger gradient. The book says the auxiliary heads may be discarded once training is complete.

Continuation methods and curriculum learning

Many optimization challenges come from the global structure of the cost, so a better local direction is not enough. Continuation methods choose starting points so that local optimization spends its time in well-behaved regions. They build a series of objectives that become harder, and the solution of one is the starting point of the next. The easiest objective is blurred, and the book writes the blur as Equation 8.40:

Some non-convex functions become approximately convex when blurred, and the minimum of the blurred version can guide the search to the global minimum. The blur can fail in three ways. The number of stages can be too large, the function may never become convex, or the blurred minimum may track to a local minimum. The book's example of a function that never becomes convex is .

For the toy loss and the blur , the average over the Gaussian can be written in closed form. The toy loss is made for this page and is not printed in the book. This closed form is added here and is not printed in the book:

The blurred function is convex only when , which means . The readout shows that a single minimum appears earlier, near . The track button slides the blur from its current value to zero, one small step at a time, and follows the lowest minimum. The path is drawn below.

Curriculum learning is a continuation method in this view. Earlier objectives make simple examples count more, and the share of harder examples grows as training goes on. In its recurrent network experiment, the book reports that a stochastic curriculum, a random mix of easy and hard examples with a gradually growing share of hard ones, gave much better results. A deterministic curriculum gave no improvement over ordinary training.

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.7 (pages 317–329), 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.