Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method

Yatin Dandi, David Gamarnik, Francisco Pernice, Lenka Zdeborová

Abstract

Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses, it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics, and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods (GFOM), a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

Introduction

When training machine learning models or solving high-dimensional statistical inference problems, we typically rely on iterative first-order algorithms. In the high-dimensional limit—where the number of features $d$ and data points $N$ both tend toward infinity—tracking the evolution of every individual weight or coordinate becomes mathematically intractable.

To address this, researchers in statistical physics developed Dynamical Mean Field Theory (DMFT). DMFT simplifies the complex, high-dimensional system into a set of "effective" low-dimensional stochastic processes. These equations describe how macroscopic quantities, such as training loss or the correlation with a hidden signal, evolve over time. However, the primary heuristic used to derive these equations—the dynamical cavity method—has lacked mathematical rigor for decades, forcing mathematicians to rely on more cumbersome and less intuitive frameworks like large deviations or Fourier analysis.

The GFOM Framework

A central contribution of this work is the definition of General First Order Methods (GFOM). This algorithmic template provides a unified structure that captures several prominent optimization and inference algorithms, including:

  • Gradient Descent (GD): The workhorse of modern machine learning.
  • Approximate Message Passing (AMP): A class of algorithms known for optimal performance in high-dimensional linear estimation.
  • Power Iteration: A fundamental method for eigenvalue problems.

By proving results for GFOM, the authors provide a single, unified proof that covers the high-dimensional behavior of all these disparate methods simultaneously.

Formalizing the Dynamical Cavity Method

The intuition behind the cavity method is to "remove" one coordinate from the system (creating a "cavity"), analyze the behavior of the remaining $N-1$ coordinates, and then re-insert the missing coordinate to observe the system's "reaction."

The authors bridge the gap between this physical intuition and mathematical rigor through a few key technical innovations:

1. Taylor Expansions of the Algorithm State

The core of the formalization involves calculating how the algorithm reacts to a single coordinate. The authors replace the heuristic "removal" step with rigorous Taylor expansions of the algorithm's state with respect to the "disorder" (the random entries of the data matrix $X$).

2. Derivative Bounds (Theorem 2.7)

The "heavy lifting" of the proof is contained in Theorem 2.7. The authors prove that the influence of any single data entry on the algorithm's state is vanishingly small, specifically $O(1/\sqrt{N})$, unless there is an explicit, direct connection. This result ensures that higher-order terms in the Taylor expansion can be safely ignored in the limit, and that all moments of the derivatives remain bounded, ensuring stability.

3. Lindeberg Exchange

To prove that the internal variables (or "fields") of the algorithm behave like Gaussian processes in the limit, the authors employ a Lindeberg-style exchange argument. This shows that the empirical distribution of the algorithm's variables converges to the probability measures predicted by DMFT.

Key Insights

Independence through Negligible Sensitivity

The "Aha!" moment of the paper lies in how it handles independence. In the heuristic cavity method, physicists often assume certain variables are independent. The authors show that this assumption can be replaced by proving that the derivatives of these variables with respect to one another are negligible. If the sensitivity of variable $A$ to variable $B$ vanishes as $N \to \infty$, they are "effectively" independent for the purposes of mean-field equations.

A Unified View of AMP and GD

In the physics of disordered systems, AMP is often viewed as a special case because its "reaction term" (the Onsager term) is simpler. This paper demonstrates that Gradient Descent is essentially a more complex version of the same phenomenon, where the first-order reaction term survives rather than vanishing. This provides a clear, rigorous link between two of the most important algorithm classes in the field.

Conclusion and Future Work

This work successfully validates the "physicist's shortcut," proving that the cavity intuition is fundamentally sound and mathematically exact for GFOM. It establishes path-wise convergence, meaning the entire trajectory of the algorithm—not just the final state—is governed by the DMFT process.

However, several challenges remain:

  • Structured Data: The current proof assumes the data matrix $X$ has i.i.d. sub-Gaussian entries. Real-world data (like images or text) is highly correlated. Extending this rigorous cavity method to structured matrices remains a major open problem.
  • Non-Smoothness: The proof currently requires Lipschitz continuity for the algorithm's non-linearities. This excludes certain non-smooth functions like hard thresholding.
  • Deep Architectures: While this work covers shallow models (Generalized Linear Models), applying the dynamical cavity method to deep, multi-layer neural networks is the next major frontier in this research line.

Summary updated

Abstract

Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses by Sompolinsky and Zippelius (1982), it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.
BibTeX
@inproceedings{dandi2026rigorous,
  author = {Yatin Dandi and David Gamarnik and Francisco Pernice and Lenka Zdeborová},
  title = {{Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method}},
  booktitle = {Conference on Learning Theory},
  year = {2026},
}

Loading related content...

Figure