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

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

TL;DR

This paper provides the first rigorous mathematical formalization of the dynamical cavity method, a classic but traditionally heuristic tool from statistical physics. By making this method rigorous, the authors provide a unified proof for the high-dimensional behavior (Dynamical Mean Field Theory) of a wide range of optimization algorithms, including Gradient Descent and Approximate Message Passing.

What Problem Does This Paper Address?

When we train machine learning models or solve high-dimensional statistical problems, we often use iterative "first-order" algorithms like Gradient Descent. In high dimensions (where the number of features $d$ and data points $N$ are both very large), tracking every single weight or coordinate is impossible.

Physicists developed Dynamical Mean Field Theory (DMFT) to solve this. DMFT provides a set of "effective" low-dimensional equations that describe how macroscopic quantities—like the training loss or the correlation with a hidden signal—evolve over time.

To derive these equations, physicists typically use the dynamical cavity method. The intuition is simple: "remove" one coordinate (creating a 'cavity'), see how the rest of the system behaves without it, and then re-insert the coordinate to see how the system "reacts." While intuitive and powerful, this method has remained non-rigorous for decades. Mathematicians have had to rely on much more cumbersome tools (like Fourier analysis or large deviations) to prove the same results, often losing the physical intuition along the way.

Methods

The authors bridge the gap between physics intuition and mathematical rigor through several key steps:

  1. General First Order Methods (GFOM): They define a broad algorithmic template that captures Gradient Descent, Power Iteration, and Approximate Message Passing (AMP) under one roof.
  2. Formalizing the "Reaction": The core of the cavity method is calculating how a system "reacts" to a single coordinate. The authors formalize this using Taylor expansions of the algorithm's state with respect to the "disorder" (the random entries of the data matrix $X$).
  3. Derivative Bounds: The "heavy lifting" of the paper is a technical theorem (Theorem 2.7) proving that the influence of any single data entry on the algorithm's state is very small ($O(1/\sqrt{N})$) unless there is an explicit, direct connection. This allows them to ignore higher-order terms in their expansions.
  4. Lindeberg Exchange: They use a Lindeberg-style argument to show that the "fields" (internal variables of the algorithm) behave like Gaussian processes in the limit, matching the predictions of DMFT.

Datasets

As a theoretical paper in mathematical physics/statistics, it does not use empirical datasets. Instead, it operates on a standard theoretical model:

  • Data Matrix ($X$): Assumed to have i.i.d. (independent and identically distributed) sub-Gaussian entries with variance $1/N$.
  • Labels ($y$): Generated via a Generalized Linear Model (GLM) where $y = g(X\theta; w)$.

Key Insights and Ideas

  • The "Aha!" Moment for Derivatives: The authors realized that the "non-rigorous" part of the cavity method—assuming certain variables are independent—can be replaced by proving that their derivatives are negligible. If the sensitivity of variable $A$ to variable $B$ vanishes as $N \to \infty$, they are "effectively" independent for the sake of the mean-field equations.
  • Unified View of AMP and GD: In the physics of "disordered systems," AMP is special because its "reaction term" (the Onsager term) is simpler. This paper shows that Gradient Descent is just a slightly more complex version of the same phenomenon where the first-order "reaction" term survives rather than vanishing.
  • Path-wise Convergence: The proof shows that the entire trajectory of the algorithm converges to the DMFT process, not just the final state.

Key Results

  • Rigorous Proof of DMFT: The paper successfully proves that for any GFOM, the empirical distribution of the algorithm's variables converges to the probability measures defined by the DMFT equations.
  • Validation of the Cavity Method: By providing a rigorous path, they validate the "physicist's shortcut," showing that the cavity intuition is fundamentally sound and can be made mathematically exact.
  • Moment Bounds: They establish that all moments of the derivatives of the algorithm's variables remain bounded, which is a crucial requirement for stability in high-dimensional analysis.

Limitations and Future Work

  • I.I.D. Assumptions: The proof relies on the data matrix $X$ having independent entries. Real-world data is often highly structured or correlated (e.g., images, text). Extending this "rigorous cavity" to structured matrices (the "Universality" problem) is a major open challenge.
  • Lipschitz Constraints: The current proof assumes the non-linearities in the algorithm (like the activation functions or loss gradients) are Lipschitz continuous. While this covers many cases, it doesn't strictly cover non-smooth cases like hard thresholding without further approximation.
  • Multi-layer Architectures: The current work focuses on "shallow" models (Generalized Linear Models). Applying the dynamical cavity method to deep neural networks remains a "holy grail" for this line of research.

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