On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by ${\ell }_1$ Norm

As the default optimizer for training large language models, AdamW has achieved remarkable success in deep learning. However, its convergence behavior is not theoretically well-understood.

This paper establishes the convergence rate $\frac{1}{K}{\sum }_{k=1}^{K}E||\nabla f(x^k)|{|}_1\le$ for AdamW measured by ${\ell }_1$ norm, where K represents the iteration number, d denotes the model dimension, and C matches the constant in the optimal convergence rate of SGD.

Theoretically, we have $E||\nabla f(x)|{|}_1\ge$ when each element of $\nabla f(x)$ is generated from Gaussian distribution $\mathcal{N}(0,1)$. Empirically, our experimental results on real-world deep learning tasks reveal $||\nabla f(x)|{|}_1=\Theta (\sqrt{d})||\nabla f(x)|{|}_2$. Both support that our convergence rate can be considered to be analogous to the optimal convergence rate of SGD.