On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ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 frac1Ksumk=1KEleft[||nabla f(xk)||1right]≤ O(frac√dCK1/4) for AdamW measured by ℓ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 ||nabla f(x)||2ll ||nabla f(x)||1≤ √d||nabla f(x)||2 for any high-dimensional vector x and Eleft[||nabla f(x)||1right]≥√frac2dπEleft[||nabla f(x)||2right] 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=varTheta(√d)||nabla f(x)||2. Both support that our convergence rate can be considered to be analogous to the optimal frac1Ksumk=1KEleft[||nabla f(xk)||2right]≤ O(fracCK1/4) convergence rate of SGD in the ideal case. We also extend our result to NAdamW, an AdamW variant that employs a double-momentum mechanism, and demonstrate that it maintains the same convergence rate.