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.