Rigorous effective dynamics for first-order algorithms through the dynamical cavity method

The cavity method is a powerful, non-rigorous technique at the heart of the theory of spin glasses. Its application to dynamics, called the dynamical cavity method, has been one of the main tools in the physicist's toolkit for describing the asymptotics of algorithms in disordered systems. One of the strengths of the method is its transparency: the cavity derivation is naturally reflected in the final equations describing the asymptotic effective dynamics. By contrast, previous rigorous methods to obtain the same equations have been based on the Gaussian conditioning technique, large deviations theory over paths, or Fourier analysis.

In this work, we turn the dynamical cavity method into a formal method of proof. To illustrate the technique, we analyze a general class of iterative algorithms, known as general first-order methods, that are defined by repeated multiplication by a random matrix and entry-wise non-linearities. They capture a wide variety of popular algorithms, including various forms of gradient descent, approximate message passing, and many others.

This is joint work with Yatin Dandi, David Gamarnik, and Lenka Zdeborová.