Challenges in Neural Network Optimization

Why optimization is hard

Optimization in general is hard. Machine learning has often avoided that difficulty by designing the objective and the constraints so that the problem is convex. A convex problem has one useful property: any local minimum is a global minimum, so finding any point with zero gradient is enough. Neural networks do not have this property. The book states that the general non-convex case must be faced, and it lists the main obstacles that appear in practice.

The demo below uses a one-dimensional cost with a wiggle of size . At the cost is a smooth bowl, and gradient descent from anywhere reaches the bottom. Add a wiggle and the bowl gets bumps, which can trap descent. The step is the book's basic update, with step size , and the lowest point of the cost is found on a fine grid. This page uses the wiggle to show the effect. It is a stand-in function written for this page, and the book does not print it.

Move the wiggle up slowly from 0 and watch where the path ends. Up to a wiggle of about 0.03 the path still ends close to the lowest point. By 0.1 it has stopped in a dip, and the gap grows with the wiggle. The readout gives the gap between the stopping cost and the lowest cost on the grid. A gap near zero means the path found the lowest point.

The book groups the difficulties into several kinds. The list is ill-conditioning, local minima, saddle points and other flat regions, cliffs, long-term dependencies, inexact gradients, and poor correspondence between local and global structure. Sections 2 to 7 take them in turn, with cliffs and long-term dependencies sharing Section 5. The book's Figures 8.1 to 8.4 are discussed where they apply.

The demo does not match any network. In the book, the difficulties come from the shape of the cost around the parameters, and the list tells you where to look when training stalls.

Ill-conditioning

Ill-conditioning is the most prominent difficulty even for convex functions. It is a property of the Hessian , the matrix of second derivatives of the cost. When the curvature differs strongly between two directions, one step size cannot suit both. The book says ill-conditioning is generally believed to be present in neural network training, and that it can make SGD appear stuck, because even very small steps increase the cost.

The book writes the second-order Taylor expansion of the cost after one step of size in the direction of the negative gradient . The change in cost is given by Equation 8.10:

The first term is positive and grows with the curvature along the gradient. The second term is negative and is the decrease the gradient promises. Ill-conditioning is a problem when the first term exceeds the second. The book suggests monitoring the squared gradient norm and the term during training. In many cases the gradient norm does not shrink, but the curvature term grows by more than an order of magnitude, and the learning rate must then shrink. Figure 8.1 in the book shows a gradient norm that increases during successful training of a convolutional network. That figure uses logged training data, which this page does not reproduce. Section 7 shows the same message, that the gradient norm need not shrink during successful training, in a model the book describes.

The demo below uses a two-parameter quadratic with curvatures 1 and in the two directions, so the Hessian is . Here is the ratio of the two curvatures. The symbol and the ratio are chosen for this page, and the book does not print them. The start is (1, 1), the gradient there is , and the chart plots the cost after one step against the step size. The horizontal line is the starting cost.

The exact change in cost for this quadratic is the same as the expansion in Equation 8.10, so the two numbers in the readout agree. This agreement is a property of a quadratic and is added here, not printed in the book. In a neural network the expansion is only an approximation. Set to 100 and raise the step size past about 0.02. The cost rises after one step, which is the stuck behavior the book describes.

Local minima and symmetries

Many local minima in a neural network are harmless. The book explains that neural networks, and any model with several equivalent latent variables, are not identifiable. A model is identifiable if a large enough training set rules out all but one setting of its parameters. Two hidden units can be swapped, with their incoming and outgoing weights, to give a different parameter vector and the same function. The book calls this weight space symmetry. With layers of units each, the book counts the arrangements as .

The book adds that in any rectified linear or maxout network, the incoming weights and biases of a unit can be scaled by while its outgoing weights are scaled by . Without a term such as weight decay, every local minimum of such a network then lies on a hyperbola of equivalent minima. All these minima have the same cost, so the book says they are not a problematic form of non-convexity.

Local minima of high cost are a different matter. The book notes that small networks, even without hidden units, can have local minima with higher cost than the global minimum. Whether such minima are common in networks of practical size is an open question. The book says that for many years practitioners believed local minima were a common problem, and that this does not appear to be the case today. Experts now suspect that most local minima of large networks have a low cost, so that a low but not minimal cost is often enough.

The demo uses a stand-in cost with a global minimum at zero and local minima at about ±2.02 and ±4.04, and further local minima at about ±6.05. It is written for this page, and the book does not print it. Gradient descent with step 0.05 runs for 400 steps from the chosen start. Starts near zero reach the global minimum, and starts further out stop in a local minimum with a higher cost. The readout gives the stopping cost, which the challenge checks.

Saddle points and flat regions

For many high-dimensional non-convex functions, saddle points are far more common than local minima. At a saddle point the gradient is zero, and the Hessian has both positive and negative eigenvalues. Along directions with positive eigenvalues the cost rises, and along directions with negative eigenvalues it falls. The book describes a saddle as a local minimum along one cross-section and a local maximum along another. Maxima are also zero-gradient points, and like minima they are exponentially rare in high dimension. Wide flat regions, where the gradient and the Hessian are both zero, pose major problems for every numerical method, because they give no direction at all.

The book gives an intuition from random functions. The sign of each eigenvalue behaves like a coin toss. A local minimum needs all eigenvalues to be positive. Its odds in that picture are , which is exponentially small. This derivation is added here and is not printed in the book. The book states the conclusion: in high dimension, saddle points are more common than minima, and low-cost critical points are more likely to be minima than high-cost ones.

The book reports that Dauphin et al. (2014) showed experimentally that real neural networks have very many high-cost saddle points. It also reports a visualization of a training trajectory, Figure 8.2, in which the cost near a prominent saddle point is flat and the gradient descent trajectory escapes it quickly. The book adds that continuous-time gradient descent can be shown to be repelled from such a saddle, but that the situation may be different for more realistic uses of gradient descent. Figure 8.2 is a projection of a real trained network and is not rebuilt here.

Newton's method behaves differently. Gradient descent moves downhill and is not designed to seek a critical point. Newton's method solves for a point where the gradient is zero, so without modification it can jump to a saddle point. The demo below uses the saddle . Its gradient in is , so gradient descent grows the offset in by a factor of 1.2 per step with step size . The chart shows the offset in on a log scale.

Gradient descent takes longer to leave a saddle when the starting offset is small, but it leaves. Newton's method, with the exact Hessian of this quadratic, reaches the saddle point at the origin in one step. The readout states both results. The one-step result for Newton's method is added here and is not printed in the book.

Cliffs and exploding gradients

Deep networks often have steep regions resembling cliffs. The book attributes them to the multiplication of several large weights. On the face of a steep cliff, one gradient step can move the parameters far, often off the cliff altogether. The book's Figure 8.3 shows such a cliff in a deep network. The cliff below is made for this page and has the same shape, but its numbers are not taken from the book.

The gradient gives the best direction within an infinitesimal region, not the best step size. Gradient clipping limits the step length, so that it stays small enough to remain in the region where the gradient describes the cost. The demo compares a plain step with a clipped one. The cost has a sharp rise near . The default start, at 0.5, sits on the gentle slope before the rise, not on its face.

The book also explains where the same effect appears in recurrent networks. Repeated multiplication by a matrix at each time step makes the gradient depend on the powers of its eigenvalues. Suppose that has an eigendecomposition. The book gives Equation 8.11:

Every eigenvalue that is not near an absolute value of 1 will explode if it is greater than 1 in magnitude, or vanish if it is less than 1. The book calls this the vanishing and exploding gradient problem. Vanishing gradients make it hard to know which direction to move, and exploding gradients make learning unstable. The book says this repeated multiplication is similar to the power method for the largest eigenvalue, so that the principal eigenvector dominates in the end.

Feedforward networks use a different matrix at each layer, so they can largely avoid this problem. Recurrent networks use the same matrix at every time step. The demo shows one eigenvalue. Its power sets the size of the component along that eigenvector, and the book's Equation 8.11 says this is what the whole matrix does direction by direction.

Inexact gradients

Most optimization algorithms assume an exact gradient or Hessian. In practice both are estimates. Nearly every deep learning algorithm uses a minibatch to estimate the gradient, which is the sampling noise of Section 4 in the previous module. Other objectives are intractable, so their gradients are also intractable and can only be approximated. The book gives contrastive divergence as an example, which approximates the gradient of the intractable log-likelihood of a Boltzmann machine.

Algorithms can be designed to allow for imperfect gradients, or a surrogate loss can be chosen that is easier to approximate than the true loss. The demo below uses a quadratic cost with curvature and a constant bias added to the gradient. The gradient estimate is , and the noise has the size set by the slider. Gradient descent uses step .

The noise makes the path wander, but the bias moves its center. Without noise, the settling point of this quadratic is where the biased gradient is zero, which is . This derivation is added here and is not printed in the book. The true minimum is at zero, so the bias moves the answer away from the goal even when the noise is removed. The book's point is the same: an estimate that is wrong on average leads to a wrong answer, even when the optimizer itself is correct.

The readout gives the noise-free settling point and the average of the noisy path over its last fifty steps. With small noise the average should be close to .

Poor correspondence and theoretical limits

The difficulties so far describe the cost at one point. A step can be hard to compute if the cost is poorly conditioned at the current point, if the point lies on a cliff, or if it is a saddle point that hides progress. Even when all of these are handled, training can still perform poorly if the most improving local direction does not point toward distant regions of much lower cost.

Figure 8.4 in the book shows this. Its cost has no minima or saddle points, only asymptotes toward low values, and the main cause of difficulty is starting on the wrong side of a mountain that cannot be traversed. The demo below is a stand-in with the same absence of minima and saddle points, but a different shape. Its cost is one sigmoid step with asymptotes at 1 on the left and 0 on the right, and it has no mountain. On the flat left tail the slope is so small that each step barely moves, so 300 steps may not reach the low region. The function is written for this page and is not printed in the book.

The book notes that the learning trajectory can spend much of its time tracing a wide arc around a mountain. In higher dimensions, learning algorithms can often go around such mountains, but the detour may be long. Much of the research into optimization difficulties asks whether training reaches a global minimum, a local minimum, or a saddle point. The book adds that in practice neural networks often do not reach a critical point of any kind, since the gradient does not shrink, as Figure 8.1 showed.

The book also says that critical points do not always exist. The negative log-likelihood of a softmax classifier can get arbitrarily close to zero without reaching it, and a Gaussian model can have a negative log-likelihood that tends to negative infinity as the learner raises the precision without bound. Here the optimizer keeps moving, and the cost only approaches a limit.

The book gives a practical conclusion: all of these difficulties might be avoided if a region of space connected reasonably directly to a solution can be reached by local descent from a good starting point. That view suggests research into choosing starting points, not only into better local moves.

Gradient norm that does not shrink

Figure 8.1 is a logged run of a real network, so it is not rebuilt here. The same message appears in a model that the book describes in this section. The model is a Gaussian with precision , where is the log precision and the only parameter. For one training target with residual , the negative log-likelihood is, up to a constant,

Its derivative with respect to is

When the residual is not zero, the gradient vanishes at the best precision . When the residual is zero, the gradient stays at one half for ever and the cost falls without limit. This is the case the book describes, where the learning algorithm keeps increasing the precision.

Read the two charts together. While the residual is not zero, the gradient magnitude stays near one half for many steps while the cost keeps falling, and it reaches zero only at the best precision. This page's demo is a stand-in built from the Gaussian model. It does not reproduce the network in Figure 8.1.

Good-enough solutions

The book states that several theoretical results limit what any optimization algorithm can do for neural networks. It also says those results usually have little bearing on the use of neural networks in practice. In training, the goal is not the exact minimum. The goal is to reduce the value enough to give a good generalization error. The demo below uses the same stand-in cost as Section 3. For each start on a grid, it reports whether gradient descent stops at a cost at or below a chosen threshold.

At a threshold of 0.2, only starts that reach the global minimum or the valley near ±2.02 count. At 0.7 the valleys near ±4.04 also count. The fraction rises with the threshold, which is the book's point: a point with low but not minimal cost is often good enough.

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.2 (pages 282–293), 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.