25
$\begingroup$

I was reading about the Adam optimizer for Deep Learning and came across the following sentence in the new book Deep Learning by Begnio, Goodfellow and Courtville:

Adam includes bias corrections to the estimates of both the first-order moments (the momentum term) and the (uncentered) second-order moments to account for their initialization at the origin.

it seems that the main reason to include these bias correction terms is that somehow it removes the bias of the initialization of $m_t = 0$ and $v_t = 0$.

  • I am not 100% sure what that means but it seems to me that it probably means that the 1st and 2nd moment start at zero and somehow starting it off at zero slants the values closer to zero in an unfair (or useful) way for training?
  • Though I would love to know what that means a bit more precisely and how that damages the learning. In particular, what advantages does un-biasing the optimizer have in terms of optimization?
  • How does this help training deep learning models?
  • Also, what does it mean when it's unbiased? I am familiar what unbiased standard deviation means but it's not clear to me what it means in this context.
  • Is bias correction really a big deal or is that something overhyped in the Adam optimizer paper?

Just so people know I've tried really hard to understand the original paper but I've gotten very little out of reading and re-reading the original paper. I assume some of these question might be answered there but I can't seem to parse the answers.

$\endgroup$
5
  • 3
    $\begingroup$ Link:arxiv.org/pdf/1412.6980v8.pdf 1st and 2nd moment gradient estimates are updated via moving average, and started off with both estimat4es being zero, hence those initial values for which the true value is not zero, would bias the results, because the initial estimates of zero only gradually die out. What I don't understand is why the gradient at initial point is not used for the initial values of these things, and then the first parameter update. Then there would be no contamination by the initial zero values, which has to be undone.So there'd be no need for the bias correction. $\endgroup$ Aug 31, 2016 at 21:45
  • 1
    $\begingroup$ So it appears that rather than having special code for the initial iteration, the authors have decided to do a mathematically equivalent thing by introducing what would be a bias, and then undoing it. This adds unnecessary, though fast, calculations on all iterations. Bt doing this, they have maintained a purity of code that looks the same at all iterations. I would have just started with the first gradient evaluation instead, and have the gradient moment update formula only start on the 2nd iteration. $\endgroup$ Aug 31, 2016 at 21:48
  • $\begingroup$ @MarkL.Stone the authors emphasize so much the bias correction that it seemed to me that was what was novel or important in their paper. So they could have just not "corrected the bias" and have the same algorithm? If that is true I fail to see why adam is such an important optimizer or what the big deal is. I always thought it was the bias correction. $\endgroup$ Aug 31, 2016 at 22:18
  • 5
    $\begingroup$ They introduce a bias and then correct it out, for no good reason apparent to me. It's like multiplying by 2 (oh my, the result is biased), and then dividing by 2 to "correct" it. The whole thing with the bias introduction and removal seems like an unnecessary sideshow. Maybe the paper wasn't long enough without doing it, so they added this spiel to make it longer :) Adam may have its merits, but they would have been the same doing it the way I proposed. I'd love for the authors to come on here and explain it though. Maybe I'm missing some subtle point or misunderstanding something. $\endgroup$ Aug 31, 2016 at 22:42
  • $\begingroup$ @MarkL.Stone I too, initially thought that using the initial value might be reasonable, but after some number crunching in my late answer below, I'd have to argue against that. Feel free to critique or argue otherwise. :-) $\endgroup$ Apr 14, 2021 at 5:33

2 Answers 2

26
+50
$\begingroup$

The problem of NOT correcting the bias
According to the paper

In case of sparse gradients, for a reliable estimate of the second moment one needs to average over many gradients by chosing a small value of β2; however it is exactly this case of small β2 where a lack of initialisation bias correction would lead to initial steps that are much larger.

enter image description here

Normally in practice $\beta_2$ is set much closer to 1 than $\beta_1$ (as suggested by the author $\beta_2=0.999$, $\beta_1=0.9$), so the update coefficients $1-\beta_2=0.001$ is much smaller than $1-\beta_1=0.1$.

In the first step of training $m_1=0.1g_t$, $v_1=0.001g_t^2$, the $m_1/(\sqrt{v_1}+\epsilon)$ term in the parameter update can be very large if we use the biased estimation directly.

On the other hand when using the bias-corrected estimation, $\hat{m_1}=g_1$ and $\hat{v_1}=g_1^2$, the $\hat{m_t}/(\sqrt{\hat{v_t}}+\epsilon)$ term becomes less sensitive to $\beta_1$ and $\beta_2$.

How the bias is corrected
The algorithm uses moving average to estimate the first and second moments. The biased estimation would be, we start at an arbitrary guess $m_0$, and update the estimation gradually by $m_t=\beta m_{t-1}+(1-\beta)g_t$. So it's obvious in the first few steps our moving average is heavily biased towards the initial $m_0$.

To correct this, we can remove the effect of the initial guess (bias) out of the moving average. For example at time 1, $m_1=\beta m_0+(1-\beta)g_t$, we take out the $\beta m_0$ term from $m_1$ and divide it by $(1-\beta)$, which yields $\hat{m_1}=(m_1- \beta m_0)/(1-\beta)$. When $m_0=0$, $\hat{m_t}=m_t/(1-\beta^t)$. The full proof is given in Section 3 of the paper.


As Mark L. Stone has well commented

It's like multiplying by 2 (oh my, the result is biased), and then dividing by 2 to "correct" it.

Somehow this is not exactly equivalent to

the gradient at initial point is used for the initial values of these things, and then the first parameter update

(of course it can be turned into the same form by changing the update rule (see the update of the answer), and I believe this line mainly aims at showing the unnecessity of introducing the bias, but perhaps it's worth noticing the difference)

For example, the corrected first moment at time 2

$$\hat{m_2}=\frac{\beta(1-\beta)g_1+(1-\beta)g_2}{1-\beta^2}=\frac{\beta g_1+g_2}{\beta+1}$$

If using $g_1$ as the initial value with the same update rule, $$m_2=\beta g_1+(1-\beta)g_2$$ which will bias towards $g_1$ instead in the first few steps.

Is bias correction really a big deal
Since it only actually affects the first few steps of training, it seems not a very big issue, in many popular frameworks (e.g. keras, caffe) only the biased estimation is implemented.

From my experience the biased estimation sometimes leads to undesirable situations where the loss won't go down (I haven't thoroughly tested that so I'm not exactly sure whether this is due to the biased estimation or something else), and a trick that I use is using a larger $\epsilon$ to moderate the initial step sizes.

Update
If you unfold the recursive update rules, essentially $\hat{m}_t$ is a weighted average of the gradients,
$$\hat{m}_t=\frac{\beta^{t-1}g_1+\beta^{t-2}g_2+...+g_t}{\beta^{t-1}+\beta^{t-2}+...+1}$$ The denominator can be computed by the geometric sum formula, so it's equivalent to following update rule (which doesn't involve a bias term)

$m_1\leftarrow g_1$
while not converge do
$\qquad m_t\leftarrow \beta m_t + g_t$ (weighted sum)
$\qquad \hat{m}_t\leftarrow \dfrac{(1-\beta)m_t}{1-\beta^t}$ (weighted average)

Therefore it can be possibly done without introducing a bias term and correcting it. I think the paper put it in the bias-correction form for the convenience of comparing with other algorithms (e.g. RmsProp).

$\endgroup$
11
  • 1
    $\begingroup$ Do you agree with my 2nd comment on the question? To me, that's the bottom line. The thing about the multiplying and dividing by 2 was just supposed to be an "easier to understand" analogy, not the math used in the matter at hand. if there were other papers, which i haven't looked at, which introduced a bias by the same mechanism, which in the case of ADAM seems entirely avoidable, but didn't correct it, then that's just totally STUPID (unless somehow the bias helped the performance of the algorithm). $\endgroup$ Sep 13, 2016 at 15:55
  • $\begingroup$ @MarkL.Stone yes! actually i upvoted it, sorry about my English. and i think the algorithm that didn't correct the bias is the rmsprop, but unlike adam rmsprop works fine with the bias. $\endgroup$
    – dontloo
    Sep 13, 2016 at 16:48
  • $\begingroup$ @dontloo does your answer address Mark L. Stone's comment on why the bias correction seems superfluous? (That I think is quite important, maybe even more than paraphrasing what the original paper says). $\endgroup$ Sep 20, 2016 at 1:20
  • $\begingroup$ @CharlieParker you mean why the bias correction is superfluous or why the author makes it look superfluous? $\endgroup$
    – dontloo
    Sep 20, 2016 at 2:09
  • $\begingroup$ @dontloo I don't think the authors make it superfluous. I thought they did indeed need it (given their specific conditions). However, I thought that it wasn't necessary given Mark's suggestion. I guess my question in the comments section right now is if they really needed the correction term. $\endgroup$ Sep 20, 2016 at 16:19
2
$\begingroup$

An example, with some number crunching, might be intuitive and also help debunk the idea of using the initial gradient instead of $0$.

Consider the 1D problem $f(x)=x$, where $f'(x)=1$. $\beta_1=0.9$ and $\beta_2=0.999$ as usual.

The first few values of $m_t$ and $v_t$ (rounded to 4 places) are given below.

\begin{array}{c|c|c|c} t&m_t&v_t&m_t/\sqrt{v_t}\\\hline 0&0&0&\mathrm{N/A}\\ 1&0.1000&0.001000&3.162\\ 2&0.1900&0.001999&4.250\\ 3&0.2710&0.002997&4.950\\ 4&0.3439&0.003994&5.442 \end{array}

At $t=12$, we reach a high of $m_t/\sqrt{v_t}=6.568$, and from there it descends to $1$, the "correct" value of $m_t/\sqrt{v_t}$. In other words, with these parameters we may reach step sizes roughly $6.5$ times larger than what they should be, which may be undesirable.


We can also see that initially $m_t$ and $v_t$ are very close to $0$. As dontloo shows, $m_t$ and $v_t$ are always going to start out close to the initially used value.

As Mark L. Stone comments,

What I don't understand is why the gradient at initial point is not used for the initial values of these things, and then the first parameter update. Then there would be no contamination by the initial zero values, which has to be undone. So there'd be no need for the bias correction.

Consider, however, the context in which momentum estimates are often used: stochastic/mini-batch gradient descent. It should be expected that the initial (stochastic) gradient is not an accurate estimate of the true gradient. If we truly want an accurate estimate of the gradient, then we need to have nearly equal contributions from the first few gradients.

Note then the expanded expressions for their choice of $m_t$, using $m_0=0$.

\begin{align} m_1&=0.1g_1\\ m_2&=0.1g_2+0.09g_1\\ m_3&=0.1g_3+0.09g_2+0.081g_1\\ m_4&=0.1g_4+0.09g_3+0.081g_2+0.0729g_1 \end{align}

It is apparent that $m_t$ shares nearly the same amount of the previous several $g_t$.

Now consider setting $m_1=g_1$.

\begin{align} m_1&=g_1\\ m_2&=0.1g_2+0.9g_1\\ m_3&=0.1g_3+0.09g_2+0.81g_1\\ m_4&=0.1g_4+0.09g_3+0.081g_2+0.729g_1 \end{align}

As expected, $g_1$ now has a ten-fold influence on $m_t$.

One could make the argument that the influence of $g_1$ in $m_t$ is rapidly diminishing, and hence largely irrelevant.

But what about $v_t$? Based on our previous example, we should expect a thousand-fold influence. Let's compare $v_t$ and $\bar v_t$, where $v_0=0$ and $\bar v_1=g_1^2$. Doing the math, here's the $\%$ influence of $g_1$ on the $v$'s for several $t$.

\begin{array}{c|c|c} t&\%\text{ of $g_1$ in $v_t$}&\%\text{ of $g_1$ in $\bar v_t$}\\\hline 1&100\%&100\%\\ 10&9.96\%&99.1\%\\ 100&0.951\%&90.5\%\\ 200&0.452\%&81.9\%\\ 300&0.286\%&74.1\%\\ 400&0.203\%&67.1\%\\ 500&0.154\%&60.7\%\\ 600&0.122\%&54.9\%\\ 1000&0.0582\%&36.8\%\\ 2000&0.0156\%&13.5\% \end{array}

In my humble opinion, this is atrociously bad. Would I rather risk an initially inaccurate estimate of the gradient persisting in my momentum so significantly just to avoid a division by $1-\beta_2^t$? Absolutely not.


For the not-so-mathematically inclined, how does their bias correction solve all of these issues? Let's go through it, one-by-one.

At $t=12$, we reach a high of $m_t/\sqrt{v_t}=6.568$, and from there it descends to $1$, the "correct" value of $m_t/\sqrt{v_t}$. In other words, with these parameters we may reach step sizes roughly $6.5$ times larger than what they should be, which may be undesirable.

The bias correction solves this issue by rescaling $m_t$ and $v_t$ to have roughly the same magnitude as $g_t$ and $g_t^2$. How exactly? It divides the total sum by the sum of the weights of each $g_t$.

\begin{align} \hat m_1&=\frac{0.1g_1}{0.1}\\~\\ \hat m_2&=\frac{0.1g_2+0.09g_1}{0.1+0.09}\\~\\ \hat m_3&=\frac{0.1g_3+0.09g_2+0.081g_1}{0.1+0.09+0.081}\\~\\ \hat m_4&=\frac{0.1g_4+0.09g_3+0.081g_2+0.0729g_1}{0.1+0.09+0.081+0.0729} \end{align}

It turns out this denominator can more simply be written as $1-\beta_1^t$.

It can also be seen from the last table that by initializing $v_0=0$, we get a much more accurate momentum than initializing $v_1=g_1^2$. Indeed using $v_1=g_1^2$ actually introduces another, perhaps concerning, problem.

Furthermore, we observe that using the "initial gradient" approach is subject significantly more to the choice of $\beta$. Although $\beta=0.9$ is not so bad, when $\beta=0.999$, it can cause the initial value to persist much longer.


What should you understand from all this, intuitively? My take is that by initializing momentum to the first provided value, you become biased towards the initial value rather than biased towards $0$. In contrast, biased towards $0$ is remarkably simple, and much more intuitive, to fix.


An alternative, equivalent, formula for computing $\hat m_t$, is actually presented by dontloo, but it has some semantic drawbacks. For large $t$, we can see that $1-\beta^t\approx1$, leaving us with $m_t\approx\hat m_t$, whilst with theirs they obtain $m_t\approx\hat m_t/(1-\beta_1)$. This causes $m_t$ to be influenced by the choice of $\beta_1$ as well as lose its meaning as the momentum approximation of $g_t$. Since it's influenced by $\beta_1$, it can no longer be directly compared to $g_t$.

Though one could argue you shouldn't worry about the existence of $m_t$ and instead focus on $\hat m_t$, which is the same in both formulations, I would argue that letting $m_t$ be an approximation of $g_t$ is much more of an intuitive buildup than the latter.


For some intuition on the momentum formulas, note also the similarity between the following:

$$m_t=m_{t-1}+(1-\beta_1)(g_t-m_{t-1})$$ $$a_t=a_{t-1}+\frac1t(g_t-a_{t-1})$$

As it turns out, $a_t$ is the accumulating formula for the actual average of $g_t$. $m_t$ is then an approximation of this, where the newest gradient weighs in slightly more than the previous.

$\endgroup$

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.