Convergence proof of ADAM optimizer

Question

I've read ADAM paper (https://arxiv.org/abs/1412.6980) and found out a suspicious part.

In Lemma 10.3 of Appendix, \begin{align*} \sqrt{\|g_{1:T,i}\|_2^2 - g_{T,i}^2} & \le \|g_{1:T,i}\|_2 - \frac{g_{T,i}^2}{2\|g_{1:T,i}\|_2}\\ & \le \|g_{1:T,i}\|_2 - \frac{g_{T,i}^2}{2\sqrt{TG_\infty^2}} \end{align*}

They set the bound of 2-norm, $\|g_{1:T,i}\|_2$ of gradient using $G_\infty$, not $G_2$.

Infinity norm is less than or equal to 2-norm, so I think the proof might be wrong.

Can someone tell me what went wrong? Thanks.

Answer 1

The paper is correct, since $$\|x\|_2 = \sqrt{\sum x_i^2} \le \sqrt{\sum \max_i x_i^2 } = \sqrt{ T \|x\|_\infty^2 },$$ and for scalars $0 < y_1 \le y_2$, $$\frac{-1}{y_1} \le \frac{-1}{y_2}$$

hence $$- \frac{g_{T,i}^2}{2 \| g_{1:T,i}\|_2} \le - \frac{g_{T,i}^2}{2 \sqrt{T\|g_{1:T,i}\|_\infty^2}} \le - \frac{g_{T,i}^2}{2 \sqrt{T G^2_\infty}} $$

The important distinction is that we are comparing the 2-norm to the square root of $T$ times the infinity norm squared, rather than the 2-norm directly with the infinity norm.