Understanding the mathematics of AdaGrad and AdaDelta

Question

I have been building some models for a project, but I can't wrap my head around the math of Adagrad and Adadelta algorithms.

I do understand how vanilla gradient descent works and I have written code for making it work successfully.

I will be grateful if anyone explain these two things to me or provide some resource to understand them.

Answer 1

With regard to resources:

• In my opinion, ADADELTA: An Adaptive Learning Rate Method (the original ADADELTA paper) explains (in sections 1-3) both ADAGRAD and ADADELTA in a quite accessible manner.
• I found Adaptive Subgradient Methods for Online Learning and Stochastic Optimization to be less accessible, but it is the original ADAGRAD paper, so it is probably worth a shot.
• An overview of gradient descent optimization algorithms (a blog post by Sebastian Ruder) also helped me understand both ADAGRAD and ADADELTA.
  
  

---

Here are some central quotes from ADADELTA: An Adaptive Learning Rate Method, along with some examples and short explanations:

ADAGRAD

The update rule for ADAGRAD is as follows: $$\begin{matrix}\Delta x_{t}=-\frac{\eta}{\sqrt{\sum_{\tau=1}^{t}g_{\tau}^{2}}}g_{t} & & & (5)\end{matrix}$$ Here the denominator computes the $l2$ norm of all previous gradients on a per-dimension basis and η is a global learning rate shared by all dimensions.
While there is the hand tuned global learning rate, each dimension has its own dynamic rate.

I.e. if the gradients in the first three steps are $g_{1}=\left(\begin{gathered}a_{1}\\ b_{1}\\ c_{1} \end{gathered} \right)\,,\,g_{2}=\left(\begin{gathered}a_{2}\\ b_{2}\\ c_{2} \end{gathered} \right)\,,\,g_{3}=\left(\begin{gathered}a_{3}\\ b_{3}\\ c_{3} \end{gathered} \right)$, then: $$\begin{gathered}\Delta x_{3}=-\frac{\eta}{\sqrt{\sum_{\tau=1}^{3}g_{\tau}^{2}}}g_{3}=-\frac{\eta}{\sqrt{\left(\begin{gathered}a_{1}^{2}+a_{2}^{2}+a_{3}^{2}\\ b_{1}^{2}+b_{2}^{2}+b_{3}^{2}\\ c_{1}^{2}+c_{2}^{2}+c_{3}^{2} \end{gathered} \right)}}\left(\begin{gathered}a_{3}\\ b_{3}\\ c_{3} \end{gathered} \right)\\ \downarrow\\ \Delta x_{3}=-\left(\begin{gathered}\frac{\eta}{\sqrt{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}}a_{3}\\ \frac{\eta}{\sqrt{b_{1}^{2}+b_{2}^{2}+b_{3}^{2}}}b_{3}\\ \frac{\eta}{\sqrt{c_{1}^{2}+c_{2}^{2}+c_{3}^{2}}}c_{3} \end{gathered} \right) \end{gathered} $$ Here it is easier to see that each dimension has its own dynamic learning rate, as promised.

Problems of ADAGRAD that ADADELTA tries to counter

The idea presented in this paper was derived from ADAGRAD in order to improve upon the two main drawbacks of the method: 1) the continual decay of learning rates throughout training, and 2) the need for a manually selected global learning rate.

The second drawback is quite self-explanatory.

Here is an example for when the first drawback is an issue:
Consider a case in which the absolute value of each component of $g_2$ is much larger than the absolute value of the respective component of the gradient in any other step.
For any $t>2$, it holds that every component of $\sqrt{\sum_{\tau=1}^{t}g_{\tau}^{2}}$ is bigger than the absolute value of the respective component of $g_2$. But the absolute value of every component of $g_2$ is much bigger than the absolute value of the respective component of $g_t$, and so $\Delta x_t$ is very small.
Moreover, as the algorithm progresses, it gets closer to a minimum, so the gradient gets smaller, and so $\Delta x_t$ becomes smaller and smaller.
Thus, it might be that the algorithm virtually comes to a standstill before reaching a minimum.

ADADELTA

Instead of considering all of the gradients that were calculated, ADADELTA considers only the last $w$ gradients.

Since storing $w$ previous squared gradients is inefficient, our methods implements this accumulation as an exponentially decaying average of the squared gradients. Assume at time $t$ this running average is $E\left[g^{2}\right]_{t}$ then we compute: $$\begin{matrix}E\left[g^{2}\right]_{t}=\rho E\left[g^{2}\right]_{t-1}+\left(1-\rho\right)g_{t}^{2} & & & (8)\end{matrix}$$ where $\rho$ is a decay constant [...]. Since we require the square root of this quantity in the parameter updates, this effectively becomes the $\text{RMS}$ of previous squared gradients up to time $t$: $$\begin{matrix}\text{RMS}\left[g\right]_{t}=\sqrt{E\left[g^{2}\right]_{t}+\epsilon} & & & (9)\end{matrix}$$ where a constant $\epsilon$ is added to better condition the denominator

($\text{RMS}$ stands for Root Mean Square.)

Similarly: $$E\left[\Delta x^{2}\right]_{t-1}=\rho E\left[\Delta x^{2}\right]_{t-2}+\left(1-\rho\right)\Delta x_{t-1}^{2}$$ $$\text{RMS}\left[\Delta x\right]_{t-1}=\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\epsilon}$$ And finally:

[...] approximate $\Delta x_{t}$ by compute the exponentially decaying $\text{RMS}$ over a window of size $w$ of previous $\Delta x$ to give the ADADELTA method: $$\begin{matrix}\Delta x_{t}=-\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}g_{t} & & & (14)\end{matrix}$$ where the same constant $\epsilon$ is added to the numerator $\text{RMS}$ as well. This constant serves the purpose both to start off the first iteration where $\Delta x_{0}=0$ and to ensure progress continues to be made even if previous updates become small.
[...]
The numerator acts as an acceleration term, accumulating previous gradients over a window of time [...]

I.e. if the gradient in step $r$ is $g_{r}=\left(\begin{gathered}a_{r}\\ b_{r}\\ c_{r} \end{gathered} \right)$ and $\Delta x_{r}=\left(\begin{gathered}i_{r}\\ j_{r}\\ k_{r} \end{gathered} \right)$, then: $$\begin{gathered}\Delta x_{t}=-\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}g_{t}=-\frac{\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\epsilon}}{\sqrt{E\left[g^{2}\right]_{t}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho E\left[\Delta x^{2}\right]_{t-2}+\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho E\left[g^{2}\right]_{t-1}+\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho\left(\rho E\left[\Delta x^{2}\right]_{t-3}+\left(1-\rho\right)\Delta x_{t-2}^{2}\right)+\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho\left(\rho E\left[g^{2}\right]_{t-2}+\left(1-\rho\right)g_{t-1}^{2}\right)+\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho^{2}E\left[\Delta x^{2}\right]_{t-3}+p^{1}\left(1-\rho\right)\Delta x_{t-2}^{2}+p^{0}\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho^{2}E\left[g^{2}\right]_{t-2}+p^{1}\left(1-\rho\right)g_{t-1}^{2}+p^{0}\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho^{t-1}E\left[\Delta x^{2}\right]_{0}+\overset{t-1}{\underset{r=1}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\Delta x_{r}^{2}+\epsilon}}{\sqrt{\rho^{t-1}E\left[g^{2}\right]_{1}+\overset{t}{\underset{r=2}{\sum}}\rho^{t-r}\left(1-\rho\right)g_{r}^{2}+\epsilon}}g_{t} \end{gathered} $$

$\rho$ is a decay constant, so we choose it such that $\rho\in\left(0,1\right)$ (typically $\rho\ge0.9$).
Therefore, multiplying by a high power of $\rho$ results in a very small number.
Let $w$ be the lowest exponent such that we deem the product of multiplying sane values by $\rho^w$ negligible.
Now, we can approximate $\Delta x_{t}$ by dropping negligible terms: $$\begin{gathered}\Delta x_{t}\approx-\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\Delta x_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)g_{r}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\left(\begin{gathered}i_{r}^{2}\\ j_{r}^{2}\\ k_{r}^{2} \end{gathered} \right)+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)\left(\begin{gathered}a_{r}^{2}\\ b_{r}^{2}\\ c_{r}^{2} \end{gathered} \right)+\epsilon}}\left(\begin{gathered}a_{t}\\ b_{t}\\ c_{t} \end{gathered} \right)\\ \downarrow\\ \Delta x_{t}\approx-\left(\begin{gathered}\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)i_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)a_{r}^{2}+\epsilon}}a_{t}\\ \\ \frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)j_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)b_{r}^{2}+\epsilon}}b_{t}\\ \\ \frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)k_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)c_{r}^{2}+\epsilon}}c_{t} \end{gathered} \right) \end{gathered} $$

Answer 2

From quora you'll find a more complete guide, but main ideas are that AdaGrad tries to taggle these problems in gradient learning rate selection in machine learning:

1 Manual selection of the learning rate η.

2 The gradient vector gt is scaled uniformly by a scalar learning rate η.

3 The learning rate η remains constant throughout the learning process.

It resolves concerns 2 and 3 simply by dividing each current gradient component by an L2 norm of past observed gradients for that particular component.

It has in itself the following issues:

1 Continually decaying learning rate η.

2 Manual selection of the learning rate η.

AdaDelta resolves AdaGrad concern 1 by summing the gradients only within a certain window W.

Concern 2 solution relates to mismatch in gradient units and thus

the actual accumulation process is implemented using a concept from momentum.

The last calculation needs understanding on momentum theory and it was shortly explained there in article.

My idea was to give the main causes behind what was intended, maybe that makes reading easier.