2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ In terms of checking the code, you might want to utilize the Code Review or Computer Science forums. In terms of the conceptual aspects, you've come to the right place. Welcome to AI! $\endgroup$ – DukeZhou Aug 23 '17 at 23:57
1
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In terms of unit analysis, I'm still not sure I follow your reasoning. For example, according to the expression you have written, $\epsilon$ would need to have the same unit as $E\left[ \Delta x^2 \right]$ since those two terms are summed together; it would also need to have the same unit as $E\left[ g^2 \right]_{t}$, for the same reason. So $E\left[ \Delta x^2 \right]$ and $E\left[ g^2 \right]_{t}$ would actually need to have the same unit, and the fraction would need to be unitless. So $\Delta x_t$ would need to have the same unit as $g_t$. $\endgroup$ – HelloGoodbye Jan 9 at 22:42
  • $\begingroup$ However, the unit added to E[Δx^2] and the constant added to E[g^2] don't have to be the same, and they don't have to be unitless. See the edit I made to my question. $\endgroup$ – HelloGoodbye Jan 9 at 23:38
  • $\begingroup$ @HelloGoodbye The paper describes right before Equation (10) that $\epsilon$ is only added to "better condition the denominator", which I'm pretty sure is a fancy way of saying "we want to avoid accidentally dividing by $0$". Otherwise $\epsilon$ doesn't really have any "meaning". Indeed, you should treat the $\epsilon$ being added to the two different square roots as being different constants, they have different units and could in theory have different values. In practice, using the same value makes sense since it should just be a tiny number to avoid division by $0$ in both cases. $\endgroup$ – Dennis Soemers Jan 10 at 8:16
  • $\begingroup$ Well, I see now that the paper actually writes that the same constant is added to the numerator RMS as well. But I guess that in any practical analysis, they should be treated as different constants. $\endgroup$ – HelloGoodbye Jan 10 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.