Optimization Papers

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

Jagannath and Sarangian

High-dimensional effective dynamics for Adam, Muon and related optimisers, obtained by averaging out their memory, allow exact comparisons with plain stochastic gradient descent.

Filed under Optimization, Probability

Adaptive optimisers such as Adam and Muon are not Markovian, because of their exponential moving averages and preconditioning. The authors show that in high dimension this memory can be handled by the method of averaging, giving effective dynamics that are a Markov process, for tasks including tensor PCA, Gaussian projective models, teacher-student networks and a multi-layer network trained on XOR.

The limits allow precise comparisons between algorithms. One finding is a crossover: online stochastic gradient descent generalises better than Adam early in training until the learning curves cross and Adam takes over. The authors also prove a version of the Edge of Stability phenomenon, characterised sharply by an analogue of the infinity Laplacian.