Adaptive momentum methods reveal new training dynamics in high dimensions

High-dimensional limit theorems for adaptive variants of SGD I: Ballistic limits

Machine Learning

Summary

Training AI models often involves updating their settings using methods like stochastic gradient descent (SGD), sometimes with added tricks like momentum or adaptive step sizes to speed things up. The authors explain how these advanced training methods behave when models are very large, turning their complex, history-dependent steps into simpler processes that can be understood mathematically. They show this understanding applies to popular algorithms like ADAM and its variants across various learning problems. This work helps explain why some methods perform better early on, why sometimes the training process is on the 'edge of stability,' and offers a way to compare algorithms precisely.

What this means in practice

Authors

Aukosh Jagannath, Varnan Sarangian

Abstract

We develop the high-dimensional effective dynamics for adaptive, momentum-based variants of Stochastic Gradient Descent (SGD). These effective dynamics are given by a Markov process. They key observation is that the non-Markovianity in the algorithm due to the exponential moving average and preconditioning can be treated using the method of averaging. Our approach applies to a broad class of algorithms including to Adaptive momentum estimation (ADAM), Momentum orthogonalized by Newton-Schultz (MUON), and its variants. It also applies to a broad class of learning tasks, such at tensor PCA, Gaussian projective models, teacher-student networks, and a multi-layer neural network trained on the XOR problem using a hybrid of MUON and ADAM as commonly done in practice. We demonstrate how to this technique can give precise, quantitative comparisons between algorithms. In particular, we find interesting phenomena, such as the cross-over phenomenon where online SGD has better generalization than ADAM early in training until the learning curves cross and ADAM dominates. Furthermore, we prove a version of the Edge of Stability phenomenon. In particular, we introduce an analogue of the infinity Laplacian that sharply characterizes the Edge of Stability.