Problems getting ADADELTA to converge

Question

I have followed the pseudocode in the ADADELTA paper (top right on page 3), and wrote the following Python code for solving the optimization problem L(x) = x^2:

>>> import math
>>> 
>>> Eg = Ex = 0
>>> p = 0.95
>>> e = 1e-6
>>> x = 1
>>> history = [x]
>>>
>>> for t in range(100):
...   g = 2*x
...   Eg = p*Eg + (1+p)*g*g
...   Dx = -math.sqrt(Ex+e)/math.sqrt(Eg+e)*g
...   Ex = p*Ex + (1-p)*Dx*Dx
...   x = x + Dx
...   history.append(x)
...
>>> print(history)
[1, 0.9992838851718654, 0.998764712958258, 0.9983330059505671, 0.9979531670003327, 0.9976084468473033, 0.997289409971406, 0.996990129861279
7, 0.9967066004793412, 0.9964359664599116, 0.9961761091943561, 0.9959254064337589, 0.9956825840862665, 0.9954466203957414, 0.99521668152795
22, 0.994992076841149, 0.9947722269598268, 0.9945566404428509, 0.9943448963795858, 0.9941366311727671, 0.9939315283404335, 0.99372931053536
84, 0.9935297332202913, 0.9933325795977276, 0.9931376565033874, 0.9929447910484566, 0.9927538278504536, 0.9925646267313296, 0.9923770607899
557, 0.9921910147771753, 0.9920063837173206, 0.991823071731977, 0.9916409910308515, 0.9914600610415929, 0.9912802076558476, 0.9911013625730
931, 0.9909234627271605, 0.990746449783029, 0.9905702696936243, 0.9903948723080783, 0.9902202110243085, 0.9900462424799209, 0.9898729262763
75, 0.9897002247321224, 0.9895281026610697, 0.9893565271732506, 0.9891854674950317, 0.989014894806555, 0.9888447820944316, 0.98867510401796
52, 0.9885058367874141, 0.9883369580529869, 0.9881684468034365, 0.9880002832732533, 0.9878324488575824, 0.9876649260340926, 0.9874976982911
152, 0.9873307500614499, 0.9871640666613011, 0.9869976342338704, 0.9868314396971792, 0.9866654706957432, 0.9864997155557601, 0.986334163243
507, 0.9861688033266723, 0.9860036259383794, 0.9858386217436783, 0.9856737819083067, 0.9855090980695381, 0.9853445623089551, 0.985180167126
9962, 0.9850159054191441, 0.9848517704536291, 0.9846877558505386, 0.9845238555622267, 0.9843600638549337, 0.984196375291527, 0.984032784715
2862, 0.983869287234659, 0.9837058782089235, 0.9835425532346933, 0.9833793081332108, 0.983216138938377, 0.9830530418854679, 0.9828900134004
96, 0.9827270500901729, 0.9825641487324376, 0.9824013062675131, 0.9822385197894608, 0.9820757865381995, 0.9819131038919638, 0.9817504693601
732, 0.9815878805766881, 0.9814253352934307, 0.9812628313743479, 0.9811003667896978, 0.9809379396106398, 0.9807755480041119, 0.980613190227
9784, 0.9804508646264328, 0.9802885696256415]

Here, Eg, Ex, e, p, g and Dx are $E[g^2]$, $E[\Delta x^2]$, $\rho$, $\epsilon$, $g$ (or $\nabla L(x)$) and $\Delta x$, respectivelly, and history is the record of all values that x has obtained.

For the hyperparameters $\rho$ and $\epsilon$, I use the same values that they use in the paper, and I initialize $x$ to 1.

As can be seen when printing history, the convergence is extremely slow for such a simple optimization problem, and after 100 iterations the method has barely got 2 % closer to the optimum (x = 0). It feels like I must have misunderstood some crucial part of the paper.

For example, the paper claims that the update step Δx will have the same unit as x, if x has some hypothetical unit. While this is probably a desireable property, it is as far as I'm concerned not true, since the premise that $RMS[\Delta x]$ has the same unit as $x$ is incorrect to begin with, since $RMS[\Delta x]_0 = \sqrt{E[\Delta x]_0 + \epsilon} = \sqrt{0 + \epsilon}$ which is a unitless constant, so all $\Delta x$ become unitless rather than having the same unit as $x$. (Correct me if I'm wrong.)

Have I made some error when implementing the algorithm, or why is the convergence so slow? Is it supposed to be this slow?

Edit

After changing Eg = p*Eg + (1+p)*g*g to Eg = p*Eg + (1-p)*g*g (i.e. correcting the error spotted by Dennis), convergence is now significantly better. It still doesn't get very close to 0 after the first 100 iterations; x only goes down to 0.597. However, after 400 iterations or so, the convergence really starts to kick in and in the following 100 iterations, x goes down from its current value at 0.0156 to 2.07e-8, and then to 3.24e-57 after yet another 100 iterations!

I plotted $x$, $E[\Delta x^2]$ and $E[g^2]$ in logarithmic scale against the number of iterations, and this is what I found:

I'm not really sure what this means in terms of performance "in the wild," since this only is a toy problem, free from stochasticity in the optimization and with only one parameter.

About the unit analysis, I guess $\epsilon$ shouldn't be unitless as I wrote that it was, as otherwise, it cannot be added to $E[g^2]$ (which has the same unit as $g^2$). Also, I guess that in practice, $\epsilon$ must be treated as two different constants that may have different units when added to $E[\Delta x^2]$ and when added to $E[g^2]$; otherwise, $x$ will end up having the same unit as $g$.

Verdict

A funny thing is that even though $\epsilon$ should only be a tiny number that shouldn't affect the process significantly unless you divide by something really small, the process turns out to be highly sensitive to its value. This is because $\epsilon$ essentially is the only thing that really makes $E\left[ \Delta x^2 \right]$ grow. Higher $\epsilon$-values will make $E\left[ \Delta x^2 \right]$ grow faster and will make the optimization process go significantly faster. In my opinion, this seems to indicate a major design flaw in the algorithm.

Answer 1

The error in the code is simply having a $+$ rather than a $-$ sign. Line 4 of the algorithm says:

$$E\left[ g^2 \right]_t = \rho E\left[ g^2 \right]_{t - 1} + (1 - \rho) g_t^2,$$

but your code implements (note the $+$ inside the brackets at the end):

$$E\left[ g^2 \right]_t = \rho E\left[ g^2 \right]_{t - 1} + (1 + \rho) g_t^2.$$

A correct implementation, with only that minor change, would be:

import math

Eg = Ex = 0
p = 0.95
e = 1e-6
x = 1
history = [x]

for t in range(100):
    g = 2*x
    Eg = p*Eg + (1-p)*g*g
    Dx = -(math.sqrt(Ex + e) / math.sqrt(Eg + e)) * g
    Ex = p*Ex + (1-p)*Dx*Dx
    x = x + Dx
    history.append(x)

print(history)

On my end, that code leads to a value of approximately $0.597$. It looks like, with these hyperparameters, you'll need more like 400 or 500 iterations to get really close to $0$, but it steadily gets there.

---

For example, the paper claims that the update step Δx will have the same unit as x, if x has some hypothetical unit. While this is probably a desireable property, it is as far as I'm concerned not true, since the premise that RMS[Δx] has the same unit as x is incorrect to begin with, since RMS[Δx]_0 = sqrt(E[Δx]_0 + ϵ) = sqrt(0 + ϵ) which is a unitless constant, so all Δx become unitless rather than having the same unit as x. (Correct me if I'm wrong.)

Suppose that we use the symbol $u$ for this hypothetical unit that $x$ has. Line 5 of the algorithm says:

\begin{aligned} \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. \end{aligned}

We can get rid of the $\epsilon$ terms, their addition does not change the unit of whatever they are added to:

$$- \frac{\sqrt{E\left[ \Delta x^2 \right]_{t-1}}}{\sqrt{E\left[ g^2 \right]_{t}}} g_t.$$

As you stated correctly, for the very first iteration, we have $E\left[ \Delta x^2 \right]_{t-1} = 0$. Technically in the very first iteration it could have any unit we like (or no unit at all), based on whatever unit we choose to assign to the $0$ constant it is initially set to. Let's just say we assign it the unit $u^2$ (by saying that that is the unit of the $0^2$ constant we initialize it to). This is convenient because it allows us to immediately figure out the unit in all cases rather than just the $t = 0$ case, this is the unit that it has to have if we also still want things to work out for $t > 0$.

The gradient $g_t$ has a unit $\frac{1}{u}$, which means that $E[g^2]_t$ has a unit $\frac{1}{u^2}$, and $\sqrt{E[g^2]_t}$ then again has the unit $\frac{1}{u}$. If we replace all the quantities by their units, we then get:

$$\frac{u}{\frac{1}{u}} \times \frac{1}{u} = u.$$