SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
This work addresses the theoretical understanding and acceleration of adaptive gradient methods for machine learning optimization, with incremental contributions to existing frameworks.
The paper provides a unified convergence analysis for SGD with AdaGrad-type preconditioning, recovering state-of-the-art results for methods like AdaGrad and establishing theoretical guarantees for DASGO, and shows that these methods can be accelerated beyond known rates using Nesterov momentum, offering insights into Adam's efficiency.
In this paper, we revisit stochastic gradient descent (SGD) with AdaGrad-type preconditioning. Our contributions are twofold. First, we develop a unified convergence analysis of SGD with adaptive preconditioning under anisotropic or matrix smoothness and noise assumptions. This allows us to recover state-of-the-art convergence results for several popular adaptive gradient methods, including AdaGrad-Norm, AdaGrad, and ASGO/One-sided Shampoo. In addition, we establish the fundamental connection between two recently proposed algorithms, Scion and DASGO, and provide the first theoretical guarantees for the latter. Second, we show that the convergence of methods like AdaGrad and DASGO can be provably accelerated beyond the best-known rates using Nesterov momentum. Consequently, we obtain the first theoretical justification that AdaGrad-type algorithms can simultaneously benefit from both diagonal preconditioning and momentum, which may provide an ultimate explanation for the practical efficiency of Adam.