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.

• Good explanation in quora.com/…
– mico
Feb 10, 2018 at 17:37

With regard to resources:

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

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.

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.

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}$$

• I had a question here. I understand that the idea of AdaGrad is to make the update speed of a parameter is inversely proportional to the update history of that parameter. My question is about how to implement this. Why are we summing the squares of update history and getting its square root? I understand that we need to get rid of negative sign. So, why not directlry summing the absolute values? Jul 7, 2020 at 10:02
• @OsamaEl-Ghonimy Thanks a lot for making me recall how these beautiful algorithms work! Now, if I understood your question correctly, then it isn't clear to you why the denominator in AdaGrad is the L2 norm (aka euclidean norm). Why not use the L1 norm (aka absolute-value norm) instead? I think this question is not specific to AdaGrad. In general, how does one chooses which norm to use? Jul 8, 2020 at 10:58
• @OsamaEl-Ghonimy quora.com/When-would-you-chose-L1-norm-over-L2-norm/answer/… discusses this issue. I don't know why L2 norm was chosen in AdaGrad, but the aforementioned link and similar discussions would probably give you a better understanding of the advantages and disadvantages of each norm. I don't know the pro/cons of each, but my current best guess is that the creators of AdaGrad just chose the norm that gave them the best performance :) Jul 8, 2020 at 10:59
• Thank you for your reply. This is exactly my question. Yes, I found this quora link when searching about my question. But, I could not find the reason of AdaGrad specifically. Jul 9, 2020 at 20:45

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 η.

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.