RMSProp and AdaDelta

AdaGrad's per-parameter scaling is a good idea, but its sum $G_t$ never stops growing. Both methods in this lesson repair that by forgetting.

RMSProp

Replace the running sum of squared gradients by an exponentially decaying average:

with $\beta \approx 0.9$. Old gradients fade away, so $E_t$ tracks the recent size of the gradient instead of growing forever. The name comes from the denominator: $\sqrt{E_t}$ is a root mean square (RMS) of recent gradients.

Because the step is $\eta$ times "gradient divided by its typical size", each parameter moves by roughly $\eta$ per step whatever the scale of its gradient. A parameter with tiny gradients and one with huge gradients both take steps of about the same size.

How it behaves

On the sigmoid toy problem, RMSProp with $\eta = 0.1$ has the loss below $10^{-3}$ for good after roughly 100 to 160 steps (RMSProp keeps jittering close to the threshold, so the exact step changes with tiny numerical differences), against 183 for plain gradient descent at its best rate of 1.

There is a catch in that scale-free step. Near the minimum, the gradient becomes small, but $E_t$ shrinks along with it, so the step stays about $\eta$ in size. The parameters then bounce around the minimum instead of settling. On the narrow valley with $\eta = 0.05$:

• the loss never stays below $10^{-4}$: after several hundred steps it sits at $0.0034$,
• the parameters end up alternating around $(\pm 0.025, \pm 0.025)$, which is $\eta/2$ either side of the minimum.

The remedy is a schedule from the previous lesson. Decaying the rate as $\eta_k = 0.05/(1 + 0.01k)$ brings the loss to $7.7 \times 10^{-6}$ after 2000 steps, instead of stalling at $3.4 \times 10^{-3}$.

The learning rate still matters

The rate means something different here: it is approximately a distance per step. That makes it easier to choose when gradients vary widely in scale, but it still has to fit the problem. The table shows the steps needed on the sigmoid toy problem (blank means it never settled in 3000 steps, or diverged):

Plain gradient descent needs a large rate here because the gradients on this problem are small. RMSProp is happy with small rates but, with $\eta$ of 1 or more, takes steps larger than the whole problem and never settles. There is no rate that is best everywhere.

AdaDelta

RMSProp's update is unit-inconsistent: the parameter change should have the units of the parameter, but $\eta\,g/\sqrt{E}$ has the units of $\eta$. AdaDelta (Zeiler, 2012) fixes this by replacing $\eta$ with a running RMS of past updates, so no learning rate is needed:

and $\theta_{t+1} = \theta_t + \Delta\theta_t$. Here $\rho \approx 0.95$.

So the method needs no initial learning rate. The catch is how it starts. At step 1 the average of past updates is 0, so the numerator is $\sqrt\epsilon$, and with $\epsilon = 10^{-6}$ the first steps are tiny, about 0.0045 per parameter on the valley and about 0.0035 to 0.0039 on the toy problem, whatever the gradient. They grow as the running average of updates builds up. The result on these problems is a slow start:

The constant $\epsilon$ quietly plays the role of the learning rate at the start. A larger $\epsilon$ gives bigger initial steps.

Summary so far