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

Aukosh Jagannath, Varnan SarangianarXiv 2026 · arXiv

This paper, recently published by Aukosh Jagannath and Varnan Sarangian, provides a rigorous mathematical framework for understanding how modern, complex optimizers like ADAM and MUON behave in high-dimensional settings. By deriving "ballistic limits"—essentially the smooth trajectories that these noisy algorithms follow—the authors offer a new way to compare algorithms and explain well-known empirical phenomena.

TL;DR

The authors develop a unified framework to derive the high-dimensional scaling limits (ODEs) for adaptive, momentum-based optimizers like ADAM and MUON. Their work rigorously explains the "cross-over" phenomenon—where vanilla SGD starts faster but ADAM eventually wins—and provides a sharp characterization of the "Edge of Stability" using a new mathematical tool called the effective infinity Laplacian.

What Problem Does This Paper Address?

While Stochastic Gradient Descent (SGD) is the backbone of machine learning, our theoretical understanding of its more sophisticated cousins—like ADAM (Adaptive Moment Estimation) and MUON (Momentum Orthogonalized by Newton-Schulz)—is surprisingly sparse in high-dimensional regimes.

In high dimensions, the number of parameters ($d$) and the inverse step size ($1/\delta$) both tend toward infinity. In this regime, the "noise" from stochastic sampling doesn't just disappear; it creates specific "corrections" to the algorithm's trajectory. Furthermore, adaptive algorithms have "memory" (via exponential moving averages), which makes them non-Markovian. This means the next step depends on the entire history, not just the current state, making standard mathematical tools like the "martingale problem" approach difficult to apply directly.

Methods

The researchers bridge this gap using the Method of Averaging. They treat the algorithm as a "fast-slow" dynamical system:

  1. The Fast Scale: The momentum and moving averages change rapidly.
  2. The Slow Scale: The actual model parameters evolve more slowly.

By "averaging out" the fast momentum dynamics, they derive a closed-form Markovian process that describes the evolution of a few "summary statistics" (like the model's alignment with a hidden signal or its total norm).

Key technical innovations include:

  • Poisson Equations: Used to solve for "momentum correctors" that account for the temporal correlations inherent in adaptive methods.
  • Effective Infinity Laplacian: The authors introduce this as a high-dimensional analogue to the Hessian-based stability criteria used in full-batch gradient descent. It allows them to predict exactly where an algorithm will "hover" when it reaches the Edge of Stability.

Datasets (Learning Tasks)

The paper evaluates these theoretical limits on several high-dimensional synthetic models that capture the essence of modern ML challenges:

  • Spiked Tensor PCA: Recovering a hidden signal from a noisy, high-dimensional tensor.
  • Multi-class Logistic Regression: A convex classification task using Gaussian mixture data.
  • Gaussian XOR Problem: A non-convex task where a two-layer neural network must learn a non-linearly separable function.

Key Insights and Ideas

  • The Cross-over Phenomenon: The theory explains why we often see vanilla SGD performing better in the very early stages of training (better generalization) only to be overtaken by ADAM later. The authors provide the exact "crossing time" ($t_{crs}$) where this reversal occurs.
  • Memory as Autocovariance: The "memory" in ADAM and MUON manifests in the high-dimensional limit as an autocovariance term. Unlike simpler momentum (like Polyak momentum), these adaptive terms do not simply collapse into a multiple of the gradient noise; they fundamentally reshape the dynamics.
  • The Edge of Stability (EoS): In high dimensions, the risk doesn't just settle at a minimum. Instead, the fluctuations interact with the loss surface's curvature. The authors prove that the "effective infinity Laplacian" $\Gamma^{eff}$ converges to a specific threshold ($c_\delta/2$), providing a sharp signature of EoS behavior in stochastic settings.

Key Results

  • Quantitative Comparison: The authors derived explicit ODEs for ADAM, MUON, and SGD. For example, in Matrix PCA, they showed that ADAM has the smallest sensitivity to noise as the step-size constant ($c_\delta$) grows, explaining its robustness.
  • Phase Transitions: For Logistic Regression, the paper identifies "initial-descent thresholds." If the step size is above this threshold, the risk actually increases initially before potentially decreasing later—a behavior captured perfectly by their ODEs but missed by classical theory.
  • Validation: The theoretical ODEs (dashed lines in the paper's figures) show a near-perfect match with actual algorithmic runs (solid lines) on systems with 10,000 dimensions.

Limitations and Future Work

  • Ballistic vs. Diffusive: This paper focuses on "ballistic limits" (the average path/ODE). The authors mention a companion work (Part II) that will address "diffusive limits" (the fluctuations around that path/SDE).
  • Data Distribution: The results currently rely on "Gaussian Projective Models." While these are broad, extending the proofs to more complex, non-Gaussian data distributions remains an open challenge.
  • Coordinate Delocalization: The analysis of ADAM requires the parameters to be "delocalized" (not concentrated in just a few coordinates). While they prove this holds for their models, it is a technical constraint that might be violated in specific sparse-feature settings.

Summary updated

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.
BibTeX
@misc{jagannath2026high,
  author = {Aukosh Jagannath and Varnan Sarangian},
  title = {{High-dimensional limit theorems for adaptive variants of SGD I: Ballistic limits}},
  year = {2026},
  eprint = {2611.19059},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19059},
}
Figure