Intuition behind learning rate scheduling in AdaDelta

Question

To get rid of the problems in AdaGrad, the learning rate is changed from $\frac{\eta}{\sqrt{G_{t, ii}+\epsilon}}$ to include only gradients in a small window size $w$. But as the function approaches the optimal value, won't the denominator become small in the case of AdaDelta because the gradients become small?

Isn't this opposite to the intuition of decreasing the learning rate as the function approaches the optimal value which is followed in other learning rate scheduling techniques?

Answer 1

According to the original paper - ADADELTA: An Adaptive Learning Rate Method (and sticking to the notation in the paper), the update rule is: $$x_{t+1}=x_{t}+\Delta x_{t}$$while $f(x)$ is the function we try to minimize, $x_k$ is its parameter at the $k$-th iteration, and $\Delta x_{t}$ is given by: $$\Delta x_{t}=-\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}g_{t}$$ while:

• The operations on vectors are entrywise (as in ADAGRAD).
• $\text{RMS}\left[\Delta x\right]_{t-1}=\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\varepsilon}$ is an exponentially decaying root mean square of $\Delta x_{t-1},...,\Delta x_{t-w}$. (And $\varepsilon$ is an hyperparameter.)
  Note that the algorithm (see image below) doesn't have any $w$ explicitly in it - it is implicitly determined by the decay constant hyperparameter $\rho$, as $w$ is the lowest natural number such that multiplying a sane value by $\rho^w$ results in a negligible value.)
• $g_{t}$ is the gradient at $x_t$ (it is an approximation, as this is an SGD algorithm, but I would refer to it as "gradient", as everyone does)
• $\text{RMS}\left[g\right]_{t}=\sqrt{E\left[g^{2}\right]_{t}+\varepsilon}$ is an exponentially decaying root mean square of $g_{t},...,g_{t-w+1}$.
  
  

Finally, let's talk about your question.

Section 4.3 in the paper explains that when the algorithm approaches the optimal value, both the gradients and the $\Delta x$ values become smaller and smaller.
Consequently, $E\left[g^{2}\right]_{t}$ and $E\left[\Delta x^{2}\right]_{t-1}$ both become much smaller than $\varepsilon$, and so $$\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}=\frac{\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\varepsilon}}{\sqrt{E\left[g^{2}\right]_{t}+\varepsilon}}$$ approaches $1$, i.e. the learning rate approaches $1$.

This is not as bad as the learning rate getting uncontrollably larger, but the authors of the paper admit that $1$ might be a relatively high learning rate. Thus, they conclude that adding an annealing schedule to ADADELTA might be a good idea.


For your convenience, here is an image of the algorithm from the paper: