Algorithms with Adaptive Learning Rates

The problem: one learning rate for every parameter

Plain SGD moves every parameter by the same rule, times its gradient. Think of a mixing desk with one master fader for every channel. The bass needs a gentle touch and the cymbals a light one, and a single fader cannot suit both. Adaptive methods give each channel its own fader, and move each fader according to how that channel has behaved so far.

The book makes the same point. The cost is often far more sensitive to some directions in parameter space than to others. If those directions roughly follow the coordinate axes, each parameter can have a rate of its own. Momentum helps, but it adds a hyperparameter of its own.

The first heuristic, the delta-bar-delta rule (Jacobs, 1988), watches the sign of each partial derivative. If the sign stays the same, that parameter's rate grows. If the sign flips, the rate shrinks. The book notes that this kind of rule can only be applied to full batch optimization.

Build the picture with a bowl. Its loss has one curvature per parameter, so a steep parameter has a large and a flat one a small :

Use the one shared learning rate and watch what it does to the steep and flat directions.

Plain gradient descent has one knob. Make the learning rate too large and the steep direction overshoots and grows. Make it small enough to be safe there and the flat direction barely moves. A method that gives each direction its own rate avoids that trade-off. The next four sections build three such methods, in the order the book gives them.

AdaGrad: a rate that shrinks with history

AdaGrad (Duchi et al., 2011) gives each parameter a rate that scales inversely with the square root of the sum of its past squared gradients. The book calls it Algorithm 8.4. The accumulator holds that sum for every parameter, so it has the same shape as :

Read the two lines in order. The first adds the square of the new gradient to the sum, with the product taken element by element. The second moves each parameter by divided by rooted, with a tiny to avoid division by zero. The gradient is the same minibatch average as in Section 1.

• A parameter with large gradients accumulates a large , so its rate shrinks quickly.
• A parameter with small gradients keeps a small , so its rate shrinks only a little.
• The net effect is more progress along the gently sloped directions.

AdaGrad has good theoretical properties in convex problems. The book reports, however, that in deep networks the sum runs over the whole history from the first step, so the rate can fall too far too early. This derivation is added here and is not printed in the book: if one parameter has the same gradient at every step, then after steps equals times , and its rate is . The rate falls like , and it never rises again.

The steep coordinate receives the large gradients, so its effective rate falls first. The readout gives both rates at the chosen step, and the dashed line shows the constant rate that plain gradient descent would keep. The curve falls steadily as the sum grows, which is the premature decrease the book describes.

RMSProp: forgetting the distant past

RMSProp (Hinton, 2012) changes one thing in AdaGrad. The running sum becomes an exponentially weighted average, so old squared gradients fade. The new hyperparameter sets the decay rate. Algorithm 8.5 writes it out:

A squared gradient from steps ago keeps the weight . The weights add up to one, so the average is a true average. Its memory is about steps: remembers roughly 10 steps and roughly 100. This derivation is added here and is not printed in the book.

The book describes the purpose of the change. AdaGrad, once it reaches a convex bowl after a rough part of the landscape, has a rate already made too small by that rough part. RMSProp forgets the rough part and recovers. It is widely used in practice. The next demo builds exactly that situation: a rough patch of large gradients, followed by a gentle slope.

The gradient is 10 during the rough patch and 1 afterwards, for one parameter. This is a toy input built for the demo, not a training run. Notice how a large keeps the rough patch in memory, and a small one lets RMSProp recover quickly.

Adam: momentum, a second moment and bias correction

Adam (Kingma and Ba, 2014), Algorithm 8.7, is perhaps best seen, the book says, as a variant on the combination of RMSProp and momentum, with a few important distinctions. The first distinction is that momentum enters as an exponentially weighted estimate of the first moment of the gradient, which is the average of the gradient itself. The most straightforward way to add momentum to RMSProp applies it to the rescaled gradients, and the book notes that this combination has no clear theoretical motivation. The second distinction is the second moment , the average of the squared gradient. Adam keeps it as RMSProp does, and corrects both estimates for their start at zero. RMSProp has the second moment but lacks the correction. The equations are:

The book suggests the defaults , , and . Adam is fairly robust to these choices, though the learning rate sometimes needs changing. The corrections divide by and , which are small at the first steps.

The gradient here is held at 2 for every step, so the true values are and . The raw averages start far below these values and creep up. The corrected estimates are equal to the truth from the first step. Try a small and see that the first moment reacts quickly, while a large makes the raw second moment take several hundred steps to reach half of its true value.

The demo explains why Adam is robust. Its first step has size about whatever the gradient, because the corrected ratio is about . RMSProp has no such correction. At step one its average is , so the step is times the learning rate for a large gradient. That factor is 3.16 at .

Nesterov look-ahead and choosing an algorithm

Algorithm 8.6 combines RMSProp with Nesterov momentum. The gradient is taken at a look-ahead point , which lies one momentum step ahead of along the current velocity :

The accumulator and the decay work as in RMSProp, and is the momentum coefficient. The accumulation line is the RMSProp line of Section 3, now applied to the look-ahead gradient, so the only change from Algorithm 8.5 is where the gradient is evaluated. The demo below moves a single parameter along a parabola so that you can see the look-ahead point and the gradient taken there.

The readout gives each number of the step so that you can check the line by line arithmetic. The look-ahead point is where the momentum is already heading, so the gradient there corrects the velocity earlier than the gradient at would.

Choosing an algorithm

The book reports that there is no consensus on the best optimizer. Schaul et al. (2014) compared many algorithms across many tasks, and the adaptive family, represented by RMSProp and AdaDelta, performed fairly robustly. The book lists the most popular algorithms in use as SGD, SGD with momentum, RMSProp, RMSProp with momentum, AdaDelta and Adam. It says the choice seems to depend largely on the user’s familiarity with the algorithm, for ease of hyperparameter tuning. The sweep below shows how robust each method is to the learning rate on one toy bowl. The bowl is a single case, not a benchmark.

• Adaptive methods give each parameter its own rate. The problem is a loss that is steep in some directions and flat in others, and a single learning rate has to compromise.
• AdaGrad divides by the square root of the whole sum of squared gradients. Its rate shrinks steadily, which can stop progress early.
• RMSProp replaces the sum with an average that forgets. Its memory is about steps, and its first step is times the learning rate for large gradients.
• Adam adds momentum to the gradient, keeps a second moment, and corrects both for their start at zero. Its first step is about the learning rate whatever the gradient.
• Algorithm 8.6 takes the gradient at the look-ahead point , which is one momentum step ahead.
• No algorithm wins everywhere. The book finds the adaptive family robust, and treats the choice as a question of familiarity and tuning.

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.5 (pages 306–310), 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.