Approximate Second-Order Methods

Slope and curvature from one point

Gradient descent looks only at the slope of the loss, the gradient . Picture a hiker in fog who can feel the slope under their boots. They know which way is downhill, but nothing about whether the ground is about to level out or curl up. A second-order method also feels how fast the slope changes, which is the curvature. With both pieces, the hiker can estimate where the bottom of the nearby valley lies.

The book writes the objective as an average of the loss over the training examples. The sum runs over examples, and is the loss on one of them:

Plain gradient descent uses one derivative of . The methods on this page also use the second derivative. The book notes that the methods extend readily to objectives with extra terms, such as the parameter regularization of Chapter 7, so the ideas below apply to the loss of any network.

To keep the pictures readable, the first demos use a toy loss of one number, which the book does not use. It is a bent curve with a bottom, a top and a small bump. The toy is made for this page and is not taken from the book:

Its slope is and its curvature, the second derivative, is . Where the curvature is negative, the curve bends downwards. Where it is positive, the curve bends upwards like a bowl.

The orange line uses only the slope. The violet parabola also uses the curvature, so it bends with the loss. Near the chosen point the parabola fits the loss better than the line does. Far from that point, the parabola is only a rough guide.

Newton’s method

The most widely used second-order method is Newton’s method. It replaces the loss near the current point with the parabola in Equation 8.26. The parabola uses the gradient and the Hessian , the table of second derivatives. The Hessian has one row and one column for each parameter, so it is a square matrix:

The book writes this expansion around . It has three parts: the value at , a term with the gradient, and a quadratic term with the Hessian. Where is positive definite, meaning the curvature is positive in every direction, the parabola has a unique bottom. Setting the slope of the parabola to zero gives the Newton update:

Read the update from right to left. The gradient tells the direction and steepness of the slope. Multiplying by rescales each direction by the inverse curvature. Flat directions get big steps and steep directions get small steps. For a locally quadratic function the update jumps straight to the bottom, as the book notes. The book also gives the iterated form, Algorithm 8.8:

Section 8.2.3 of the book notes that Newton’s method is appropriate only when the Hessian is positive definite. Deep networks have saddle points, where some curvature is negative. The demo below lets you test both cases.

On the bent toy loss the picture changes. Start the Newton step where the curvature is negative, for example near 0.2. The step goes to the top of the local parabola, which is a maximum of the parabola. The readout reports whether the loss went up or down.

The bent toy loss has two bottoms and one top between them. Newton steps move in one jump to a nearby bottom when the curvature there is positive.

Regularized Newton and the cost of the Hessian

When the Hessian has negative eigenvalues (curvature below zero in some direction), the Newton step can point the wrong way. The book’s remedy is to add a constant along the diagonal, which is added to the Hessian. The regularized update is Equation 8.28. The book writes the objective as f in this equation, and this page keeps the symbol for it:

The regularized Hessian stays positive definite when is large enough. The book adds that the method is used in approximations such as the Levenberg-Marquardt algorithm, and that alpha must be large enough to offset the negative eigenvalues. For large the update approaches a small gradient step. With strong negative curvature, may need to be so large that the regularized step is shorter than a gradient step with a well chosen learning rate. The demo below uses a saddle, where one direction curves up and one curves down.

This saddle, made for this page, has loss . Its Hessian is , so the first direction curves up and the second curves down. At the point , the gradient is . The arrows show only the direction of each step, and the readout gives the angle between the regularized step and steepest descent.

Each step divides by along each direction. In the second direction that factor is , which is zero at . At that value the regularized Hessian is singular, and the readout says so. The step can point up the slope for some values of and down the slope for others. Try a few values.

The cost of the full Hessian

The book gives the cost reason for approximating the Hessian. The Hessian has one entry for each pair of parameters, so for parameters it has entries. Inverting it costs time of order , and the Hessian changes at every update. The book notes that even small networks can have millions of parameters. The next demo shows the storage needed for the gradient and for the Hessian.

The bars assume 32-bit numbers, four bytes each. This accounting is added here and is not printed in the book. It shows why Newton’s method stays out of reach for large networks, and why the methods in Sections 4 and 5 store less.

Conjugate gradients

Steepest descent with a line search zigzags on an elongated bowl. Each line search stops where the slope is zero along its direction. The next step then starts along the new slope and undoes part of the progress just made. The book’s Figure 8.6 shows this on a tilted ellipse. The demo below rebuilds that picture and adds the conjugate gradient path.

The toy is with written as a rotation of a diagonal matrix. This toy is made for this page and is not printed in the book. The ratio sets how long the ellipse is. Like the book, the figure uses an exact line search, which is the step size that gives the lowest loss along the chosen direction. For this quadratic the exact step is:

This line search formula is added here and is not printed in the book. Its numerator is the slope along the direction and its denominator is the curvature along the direction.

The conjugate gradient method changes the direction. Instead of the raw negative gradient, it uses a direction that adds back part of the previous direction:

The coefficient controls how much of is kept. Two directions are conjugate when they do not undo each other along the curvature, which means:

Computing exact conjugate directions needs the eigenvectors of , which is the cost the method wants to avoid. The book gives two formulas for that avoid this. Fletcher-Reeves uses the ratio of the squared gradient norms:

Polak-Ribière is the second choice in the book:

On a quadratic surface, the book states that the conjugate directions keep the gradient along the previous directions from growing again. In a space of dimensions, conjugate gradients therefore needs at most line searches. Algorithm 8.9 applies the same steps to a minibatch loss and writes the direction as , with the update . The book adds that for non-quadratic losses the method is restarted from time to time, that a few steps of stochastic gradient descent often help at the start, and that minibatch versions have been used successfully to train neural networks.

Two readings from the demo are worth checking. The formulas for give the same value here, because consecutive gradients are perpendicular. That identity is added here and is not printed in the book. Also, the path of conjugate gradients reaches the bottom in two steps on this two-dimensional ellipse, while steepest descent is still far away when the ellipse is long.

BFGS and its low-memory form

Quasi-Newton methods aim for the benefits of Newton’s update without computing the inverse Hessian. The Newton update is Equation 8.32:

BFGS, named after Broyden, Fletcher, Goldfarb and Shanno, keeps an approximation of the inverse Hessian . The approximation is refined by low-rank updates, which are small corrections that change the matrix in only a few directions. The direction is , which is the approximate Newton direction. A line search then picks the step size, and the update is Equation 8.33:

The book refers to the textbooks for the exact formula that refines . That update is not printed here. What matters for the learner is the shape of the result: the direction is times the gradient, and tries to be the inverse curvature.

Storing costs memory of order for parameters. The book introduces L-BFGS, which starts each update from the identity matrix instead of keeping the old approximation. It remembers only a few recent vectors, and each remembered step costs memory of order . The memory demo below compares the three costs.

The bowl is , and the point is . The blend is a toy stand-in for BFGS. It is not the BFGS update, and it is not printed in the book. It shows the idea that a better approximation of the inverse Hessian turns the direction from the gradient towards the Newton direction.

The L-BFGS count assumes two vectors of length for each remembered step. This assumption is added here and is not printed in the book. With that assumption, L-BFGS costs far less than the full approximation once is large. The price is that the direction uses only recent information.

• Curvature helps. A second derivative tells the step how far the slope will keep going. Newton’s update in Equation 8.27 uses it through the inverse Hessian, and a locally quadratic loss reaches its bottom in one step.
• Negative curvature misleads Newton. The step goes to a stationary point of the local parabola, which can be a top. Equation 8.28 adds a constant to the diagonal, and the step tends to a gradient step for large regularization.
• The Hessian is expensive. It has entries for parameters, and inverting it costs of order .
• Conjugate gradients avoids zigzags. Its directions in Equation 8.29 keep the progress made along earlier directions, and on a quadratic it needs at most line searches.
• BFGS and L-BFGS approximate the inverse Hessian. BFGS keeps in Equation 8.33, which costs memory of order . L-BFGS keeps only a few recent vectors, each of order .

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