The mathematics behind Adam Optimizer

Question

I have read the paper "ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION".

The PDF link is below: https://arxiv.org/pdf/1412.6980.pdf

The section 2.1 gives the explanation and the intuition in ADAM, but the statements does not make sense for me.

At first, it claims that $| \Delta_t | \le \alpha \cdot (1-\beta_1) / \sqrt{1-\beta_2}$, if $(1-\beta_1)>\sqrt{1-\beta_2}$

In the suggested value of $\beta_1=0.9$, $\beta_2=0.999$, it is in the case.

Latter it claims that $| \Delta_t | \le \alpha$, in common scenarios, but I think that if $\beta_1$, $\beta_2$ is fixed, if would never be in this so called "common scenarios".

Did I miss something? I am really confused.

Answer 1

Reading the paper as it is, I'm fairly sure their upper bounds here are incorrect. For instance, consider the counter example $g_1 = 2$, $g_2 = 1$, $\beta_1 = \beta_2 = 0.5$, $\alpha = 1$, $\epsilon \rightarrow 0$.

Then $m_1 = 1$, $v_1 = 1$, $m_2 = 0.5 \cdot 1 + 0.5 \cdot 1 = 1$ and $v_2 = 0.5 \cdot 1 + 0.5 \cdot 1 = 1$

Therefore, $\widehat{m}_2 = 1/(1 - 1/4) = 4/3$ and $\widehat{v}_2 = 1/(1 - 1/4) = 4/3$ and $|\Delta_2| = 1\cdot (4/3)/\sqrt{4/3} = \sqrt{4/3}$, which is more than both suggested upper bounds.

It's possible that this is a typo in favor of $\alpha \cdot \sqrt{1 - \beta_2}/(1 - \beta_1)$, which seems to have a lot more going for it.

Answer 2

My understanding is that those two expressions are two possible upper bounds (applicable depending the situation).

According to the paper (https://arxiv.org/pdf/1412.6980.pdf)

The first case only happens in the most severe case of sparsity: when a gradient has been zero at all timesteps except at the current timestep.

In that situation the upper bound will be:

$| \Delta_t | \le \alpha \cdot (1-\beta_1) / \sqrt{1-\beta_2} $

Otherwise the upper bound will be:

$|\Delta_t | \le \alpha$