A possible bug in a highly cited paper (Adam gradient descent)?

Question

My question comes from the paper Adam: A Method for Stochastic Optimization published on ICLR, which has been cited over $80,000$ times up to now. Specifically, in page 13, I think there is a 'bug' in the proof of Lemma 10.4 (see the following snapshot of my annotated version of that page):

I believe that the inequality stated after "Similarly, we can upper bound the rest of the terms in the summation" is wrong, I think the authors missed an important term in the summation that can not be handled easily. I am not sure whether such bug can be remedied to be honest...

---

Sometimes I feel super mad at some mathematical derivations or statements in these "machine-learning" paper, as I think some steps are really not that trivial and given the fact that the paper is not even that long, so why don't the authors present the full details to HELP the readers? Thank you very much for your kind help!

---

Edit: There is another question on The mathematics behind Adam Optimizer posted on MSE $4$ years ago, and I am also thinking the bound on $\Delta_t$ stated in their paper is wrong (see the bottom of page 2 of their original paper), as I tried very hard to derive it but did not succeed, how on earth the authors are allowed to skip the details of such non-trivial bounds?

---

Edit: It seems that their Lemma 10.4 is absolutely wrong, as pointed out for instance in Conjecture 4.2 of this paper. I feel ashamed of this area, as it would be a "miracle" for such paper (with obvious flaw) to get published on any mathematical journal!

Answer 1

I believe there is a typo in the paper and the $t$ you circled is supposed to be a $j$. Not that this fixes the problem. My attempted derivation agrees with you:

From $$\frac{\widehat m_{t,i}^2}{\sqrt{t\widehat v}_{t,i}} \le \frac{t}{\sqrt{t(1-\beta_2)}} \sum_{k=1}^t \gamma^{t-k} \lVert g_{k,i}\rVert_2,$$ we sum over $1 \le t \le T$, obtaining $$\begin{align*}\sum_{t=1}^T\frac{\widehat m_{t,i}^2}{\sqrt{t\widehat v}_{t,i}} &\le \sum_{t=1}^T \sum_{k=1}^t\frac{t}{\sqrt{t(1-\beta_2)}} \gamma^{t-k} \lVert g_{k,i}\rVert_2 \\ &= \sum_{k=1}^T\sum_{t=k}^T \frac{t}{\sqrt{t(1-\beta_2)}} \gamma^{t-k} \lVert g_{k,i}\rVert_2 \\ &= \sum_{k=1}^T \lVert g_{k,i}\rVert_2\sum_{t=k}^T \frac t{\sqrt{t(1-\beta_2)}} \gamma^{t-k} \\ &= \sum_{k=1}^T \lVert g_{k,i}\rVert_2\sum_{j=0}^{T-k} \frac {k+j}{\sqrt{(k+j)(1-\beta_2)}} \gamma^j \\ &= \sum_{t=1}^T \lVert g_{t,i}\rVert_2\sum_{j=0}^{T-t} \frac {t+j}{\sqrt{(t+j)(1-\beta_2)}} \gamma^j \\ &= \sum_{t=1}^T \frac{\lVert g_{t,i}\rVert_2}{\sqrt{t(1-\beta_2)}}\sum_{j=0}^{T-t} \frac {(t+j)\sqrt{t}}{\sqrt{t+j}} \gamma^j \\ &\le \sum_{t=1}^T \frac{\lVert g_{t,i}\rVert_2}{\sqrt{t(1-\beta_2)}}\sum_{j=0}^{T-t} (t+j) \gamma^j. \end{align*}$$ To obtain the claimed inequality, we appear to need $j$ to be an upper bound for $\dfrac {(t+j)\sqrt{t}}{\sqrt{t+j}} = \sqrt{t(t+j)}$, but it isn't unless $j$ is large enough relative to $t$.