Why is Adam trapped in bad/suspicious local optima after the first few updates?
The authors describe their belief in Section 3:

Due to the lack of samples in the early stage, the adaptive learning rate has an undesirably large variance, which leads to suspicious/bad local optima.

Diving further, in section 3.2:

Adam uses the exponential moving average to calculate the adaptive learning rate.  For gradients $\{g_1,\dots,g_t\}$, their exponential moving average has a larger variance than their simple average.  Also, in the early stage ($t$ is small), the difference of the exponential weights of $\{g_1,\dots,g_t\}$ is relatively small (up to $1−β^{t−1}_2$).

It seems like the root issue is that exponential moving average, while great with many data samples, have too large of a variance with few data samples. It is this variance that sometimes allow the gradient descend in a bad optima.