Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method
This work addresses the need for rigorous mathematical foundations in analyzing algorithms for researchers in machine learning and high-dimensional statistics, though it is incremental as it formalizes an existing method rather than introducing a new one.
The authors formalized the dynamical cavity method, a previously non-rigorous tool from physics, and used it to provide a new proof of the Dynamical Mean Field Theory equations for General First Order Methods, which include algorithms like Gradient Descent and Approximate Message Passing.
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.