Gradient-Based Optimization

Downhill along the slope

Picture walking down a hillside in thick fog. You cannot see the valley, but you can feel which way the ground falls. Take a step that way, feel again, and repeat. Gradient descent is this walk, carried out on a function of millions of inputs instead of two.

Start with one input . The derivative is the slope of the graph at . It converts a small change of the input into a change of the output:

Most learning problems are a search for the input that makes an objective function as small as possible. The book also calls it the cost, loss or error function, and uses these names interchangeably. Maximizing is the same task as minimizing .

Here is a small positive step, the same letter as in the predictions above. The sign of the slope gives the direction. For a small enough , a step against the sign lowers the function:

Drag in the chart to choose the start. The orange line is the tangent, the prediction for that uses only the slope. The probe marks the point on the curve. Near the starting point the tangent and the curve agree, and the further you probe the more they differ.

To the left of 0 the slope is negative and the steps move right. To the right of 0 the slope is positive and the steps move left. At the slope is zero, the steps shrink to nothing, and the descent stops at the minimum.

The two tabs are two rules. Stepping by the slope, , makes the steps shrink as the slope flattens. Stepping by the sign only moves a fixed distance each time, the form in which the book states the inequality. It cannot settle at 0 and keeps hopping across it.

Walking against the slope is a way to lower , and repeating the step is gradient descent, a method the book credits to Cauchy (1847). The next figure rebuilds the book’s Figure 4.1 for , whose derivative is .

Critical points

Where the slope is zero, the derivative tells you nothing about which way to go. These points are critical points, also called stationary points. The book distinguishes three kinds (Figure 4.2):

• A local minimum is lower than all of its neighbors, so no tiny step lowers .
• A local maximum is higher than all of its neighbors, so no tiny step raises .
• A saddle point has higher neighbors on some sides and lower neighbors on others.

On the first tab, the probe shows the slope on either side of each critical point. At a minimum the slope turns from negative to positive. At a maximum it turns from positive to negative. At the saddle the slope is positive on both sides, so the point is neither.

On the second tab, click the landscape to choose a start, then press Run descent. Each start slides into the valley nearest to it.

The lowest value of all is the global minimum. There can be several global minima, and there can be local minima that are not global. Deep learning functions have many local minima and saddle points, with flat regions between them. The book therefore settles for a value of that is very low, not necessarily minimal in any formal sense (Figure 4.3).

A shallower valley nearby is a local minimum that performs almost as well, which the book accepts as a halting point. The valley at 3.6 is much higher and should be avoided. This is a toy landscape made of smooth bumps, not the loss surface of a real network.

Gradients and steepest descent

Most loss functions take many inputs, : a vector of numbers goes in and one number comes out. Each input has its own slope.

The partial derivative measures how changes when only the input moves. The gradient stacks all partial derivatives into one vector .

The lines in the next chart are contour lines: every point on a line has the same value of , like height lines on a map. The two violet arrows are the partial derivatives. Together they form the orange gradient arrow. It crosses the contour lines at a right angle and points uphill.

On the saddle tab the gradient vanishes at the center, and on the two-valley tab at three places: two valleys and the ridge between them. Where the gradient vanishes you are at a critical point.

The directional derivative

The partial derivatives are slopes along the axes. To move in any direction, take a unit vector , with . The directional derivative is the slope of along . It is the derivative of with respect to the step , at . By the chain rule it equals

Turn the angle of the direction. The lower chart is the directional derivative for all angles. It is a cosine wave with height equal to the length of the gradient. The highest point is uphill and the lowest is exactly opposite, the steepest descent direction. The readout also checks the formula against a slope measured by a tiny real step.

To make fall as fast as possible, the book looks for the direction that makes this slope most negative:

The second line is the dot product of two vectors, written with lengths and the angle between them. Since , and the gradient length does not depend on , only remains. It is smallest, equal to −1, when . So the gradient points straight uphill and the negative gradient points straight downhill. Stepping along the negative gradient is steepest descent:

where is the learning rate, a positive number that sets the step length.

Choosing the step size

Equation 4.5 fixes the direction but not the distance. The book lists three ways to choose :

1. A small constant. A popular choice.
2. The step where the directional derivative vanishes. Move along the descent line until its slope is zero, which is the lowest point of that line.
3. Line search. Evaluate for several values of and keep the one that gives the smallest .

The lower chart shows for the first step: the value of along the descent line. A line search looks at exactly this curve.

Look at the path. With a constant step it zigzags across the stretched valley, and a larger makes this worse. The stability limit for a constant step on this bowl is . Above it the path overshoots across the valley at every move.

Line search and the zero-slope rule avoid this by choosing a step for each point. For a quadratic the zero-slope step has a closed form, which Section 7 derives. Gradient descent converges when every element of the gradient is zero, or nearly so. Sometimes you can skip the iteration altogether: solve for and jump to the critical point.

Hill climbing

Gradient descent needs continuous inputs. Its idea, a small move that is approximately the best small move, also works on discrete inputs. Climbing an objective of discrete parameters is called hill climbing. The landscape below has 40 cells with random heights from a fixed seed.

Each move goes to the better neighbor, and the climber stops when neither neighbor is better. The climber ends on the nearest peak, not necessarily on the tallest one. This is the discrete counterpart of the local minima in Section 2.

The Jacobian and the second derivative

The book now goes beyond the gradient, which applies to one output. A function can take a vector and return a vector, , as a neural network layer does. All of its first derivatives fit into one table, the Jacobian matrix .

Row belongs to output , and column to input . Row of is the gradient of output . Near a point the Jacobian is the best straight-line picture of the function: a small change of the input changes the output by about .

Drag the point in the left square. The table lists the Jacobian at that point, row by row. With a small circle the true image and the predicted ellipse agree. With a large one they separate, because the Jacobian describes only the neighborhood of the point.

The second derivative

The derivative of a derivative is a second derivative. In one dimension it is . It says how the slope changes as the input moves, and that decides whether a gradient step does as well as the gradient alone predicts. Call it the curvature.

Take a quadratic, which many functions resemble near a point, with gradient 1, and step a distance downhill:

• Zero curvature: the graph is a straight line and the value drops by exactly .
• Negative curvature: the graph bends down and the value drops by more than .
• Positive curvature: the graph bends up and the value drops by less than . A step that is too long can even raise it.

The dashed line is the prediction from the slope alone, read off the tangent. For negative curvature the true curve lies below it, for zero curvature it coincides with it, and for positive curvature it lies above it. The lower chart shows itself. Its slope is .

The second derivative test in one dimension

The second derivative also classifies a critical point. At a point where : if the slope rises through the point, so it points uphill on both sides and is a local minimum. If , it is a local maximum. If the test says nothing, since the point may be a saddle or part of a flat region.

Turn the tabs to see five functions with a critical point at 0. The test gives an answer only for the first two.

The last three tabs all have and , so the test is silent. Yet has a minimum at 0, a maximum and a saddle. A single second derivative cannot tell them apart.

The Hessian matrix

With several inputs there are many second derivatives, one for each pair of inputs. The square table of all of them is the Hessian matrix:

The Hessian is the Jacobian of the gradient. Where the second partial derivatives are continuous, the order of differentiation does not matter:

So , and the Hessian is symmetric. Functions met in deep learning are usually smooth enough that their second derivatives are continuous, so their Hessians are symmetric.

The demo checks Equation 4.7 on a function with a cross term.

The function is . The table gives the Hessian at the point you drag, from analytic formulas. The readout computes both mixed derivatives by finite differences, in both orders, and they agree.

Curvature in every direction

A unit vector is a direction. The second derivative of along it is . Because the Hessian is real and symmetric, it has real eigenvalues and perpendicular eigenvectors. If is an eigenvector, the answer is its eigenvalue. Any other direction gives a weighted average of the eigenvalues, with more weight on the eigenvectors that lie closer to . So the largest eigenvalue is the largest curvature in any direction, and the smallest is the smallest.

The eigenvectors here are the coordinate axes. The curve shows for every angle. It touches at 0° and at 90°, and every angle in between gives a blend. With one positive and one negative eigenvalue, the curvature changes sign as you turn.

The multidimensional second derivative test uses the eigenvalues of at a critical point, where :

• All eigenvalues positive, so is positive definite: the curvature is positive in every direction, and the point is a local minimum.
• All eigenvalues negative, a negative definite Hessian: a local maximum.

Two more cases. Non-zero eigenvalues of one sign with at least one zero eigenvalue make the test inconclusive, because the one dimensional test fails along the zero direction. Eigenvalues of both signs make a saddle point: a local maximum along one cross section and a local minimum along another. Unlike in one dimension, this is positive evidence of a saddle, and no zero eigenvalue is needed.

The book’s Figure 4.5 shows the saddle . In the demo below, the function is , which has the same shape as the book’s figure when the eigenvalues are 2 and −2.

The lower chart shows the two cross sections, the curve along and the curve along . One curves up and the other curves down, so the origin is a saddle. Set one eigenvalue to 0 and that cross section goes flat, and the test becomes inconclusive, as the readout notes.

The optimal step from the Taylor expansion

Near the current point the book uses a second-order Taylor series: it replaces by the quadratic with the same value, slope and curvature at .

Here is the gradient and the Hessian, both at . Take a steepest descent step with learning rate , so the new point is . Substituting it into (4.8) gives

There are three terms: the value now, the improvement expected from the slope, and a correction for the curvature. The middle term always helps. The last term is positive when the curvature along is positive, and then a large step can climb uphill.

The approximation then keeps falling as grows, and no finite step is optimal. When the curvature term is positive, the step that makes the approximation smallest is the optimal step size:

In the worst case the gradient points along the eigenvector of with the largest eigenvalue . Then the optimal step is , and in general . In practice the series is not accurate for large steps, so a heuristic choice is needed.

On the first tab the Taylor prediction is exact, because the function is a quadratic. Turn the start angle so that the gradient lies along the axis of strongest curvature, and the optimal step lands exactly on . For other angles it is larger.

On the second tab the function has a small fourth power term, so the prediction is good near 0 and drifts as grows. On the third tab the gradient lies along a direction of negative curvature, the prediction keeps falling, and there is no finite optimal step.

Conditioning and Newton’s method

The condition number of the Hessian is the ratio of its largest to its smallest eigenvalue, in absolute value (Section 4.2 of the book defines the general form). It says how much the curvature differs between directions. When it is large, gradient descent performs poorly. In one direction the slope grows quickly and in another slowly, and gradient descent does not know this.

The step is also hard to choose: it must be small enough not to overshoot along the steep direction, which leaves little progress along the flat one. The Hessian has eigenvector with the large eigenvalue and with the small one, as in the book.

Descent is stable while the step is below . The share slider sets the step as a fraction of this limit. Near the limit the path crosses the canyon at every step. A smaller step stops the zigzag but slows the walk along the floor. The lower chart counts the steps needed to shrink the loss by a factor of with the best constant step, , for each condition number. This best step is a standard result and is added here.

The trouble with gradient descent is that it ignores the Hessian. The simplest cure uses it. Newton’s method starts from the second-order Taylor expansion around the current point:

Setting the gradient of this quadratic to zero gives its critical point:

The inverse Hessian rescales the gradient by the curvature. The steps are long where the curvature is small and short where it is large, which is the cure for the canyon.

If is a positive definite quadratic, one application of (4.12) jumps to the minimum. If is only locally a positive definite quadratic, repeat the update: approximate, jump, approximate again. That reaches a critical point much faster than gradient descent does near a minimum.

Its update finds a critical point of its model, and that point may be the saddle. The book says Newton’s method is appropriate only when the nearby critical point is a minimum, a point where every eigenvalue of the Hessian is positive (Section 8.2.3).

Methods that use only the gradient, such as gradient descent, are first-order algorithms. Methods that also use the Hessian, such as Newton’s method, are second-order algorithms. The price of Newton’s method is that it needs the Hessian, with entries, and a linear system solved with it.

On the quadratic tab Newton reaches the minimum in one step from any start, and gradient descent needs many. On the non-quadratic bowl Newton needs a few steps, still far fewer than gradient descent. On the saddle tab Newton jumps to the nearest critical point of its model, the saddle, while gradient descent slides into one of the minima.

Lipschitz continuity and convexity

The algorithms in this section work for a wide range of functions but guarantee little, because the functions of deep learning are complicated. Two restrictions buy some guarantees. A function is Lipschitz continuous with Lipschitz constant if its rate of change is bounded by :

This states the assumption behind gradient descent, that a small change of the input causes a small change of the output. Geometrically, the graph through any point stays inside a double cone with slopes .

Drag the point along the curve. If is a valid constant, the curve never leaves the cone, wherever the point is. The readout estimates the smallest valid from samples. The parabola has steeper slopes further out, so its constant depends on the window. The function has a corner and still qualifies: Lipschitz continuity does not need a derivative everywhere. The square root has an infinite slope at 0, so no finite constant works there.

Convex functions

The most successful area of specialized optimization is convex optimization. It gives more guarantees by restricting to convex functions, those whose Hessian is positive semidefinite everywhere. These have no saddle points, and every local minimum is a global minimum. Geometrically, a chord between two points of the graph never lies below the graph.

On the convex tabs the chord lies on or above the curve, and descent from every start ends at one value. On the two non-convex tabs some chords dip below the curve, and different starts end in different valleys. Convex optimization is only a subroutine in some deep learning algorithms, and its direct importance in deep learning is much smaller.

What to take away

• Gradient descent steps against the gradient, the steepest descent direction.
• Critical points are minima, maxima or saddle points; a low enough value is usually good enough.
• The step is a constant, a line search or the zero-slope step. Too large a step climbs uphill.
• The Hessian gives curvature along any direction; a large condition number makes descent zigzag.
• The optimal step is at least 1 over the largest eigenvalue. Newton’s update uses the Hessian but can be drawn to saddles.
• Lipschitz continuity bounds the rate of change; convexity removes saddle points and spurious minima.

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 4.3 (pages 82–92), 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.