math.PRApr 13, 2026

Universality of first-order methods on random and deterministic matrices

Authors: Nicola Gorini, Chris Jones, Dmitriy Kunisky, Lucas Pesenti

Organizations: Bocconi University. · UC Davis. · Johns Hopkins University. · ETH Zürich.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities. A long line of work has sought to understand the large-n dynamics of GFOM, mostly focusing on "very random" input matrices and the approximate message passing (AMP) special case of GFOM whose state is asymptotically Gaussian. Yet, it has long remained unknown how to construct iterative algorithms that retain this Gaussianity for more structured inputs, or why existing AMP algorithms can be as effective for some deterministic matrices as they are for random matrices. We analyze diagrammatic expansions of GFOM via the limiting traffic distribution of the input matrix, the collection of all limiting values of permutation-invariant polynomials in the matrix entries, to obtain the following results: 1. We calculate the traffic distribution for the first non-trivial deterministic matrices, including (minor variants of) the Walsh-Hadamard and discrete sine and cosine transform matrices. This determines the limiting dynamics of GFOM on these inputs, resolving parts of longstanding conjectures of Marinari, Parisi, and Ritort (1994). 2. We design a new AMP iteration which unifies several previous AMP variants and generalizes to new input types, whose limiting dynamics are Gaussian conditional on some latent random variables. The asymptotic dynamics hold for a large and natural class of traffic distributions (encompassing both random and deterministic input matrices) and the algorithm's analysis gives a simple combinatorial interpretation of the Onsager correction, answering questions posed recently by Wang, Zhong, and Fan (2022).

Figures & tables

Figure 1: A cactus graph in C{\cal C} . Intuitively, a cactus is a “tree of cycles”.
Figure 2: Examples of treelike and Gaussian diagrams. The root vertex is circled.
Figure 3: Example for Proposition 5.8 of a 2-edge-connected graph which is not a cactus. If the open cactus in red is removed, the graph remains 2-edge-connected.
Figure 4: Illustration of the main diagrammatic manipulations in the proof of Lemma 5.20 .
Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Our Feynman diagram notation vs. the ’t Hooft double line notation.
Figure 6: The 12 Feynman diagrams associated to ⟨\Tr(\bA4)⟩GOE\langle\Tr(\bA^4)\rangle_{\textsf{GOE}} . The two red edges are matched in the orientation specified by the arrows, and similarly for the blue edges. Gluing either of the left two diagrams results in a “taco”. Gluing the remaining diagrams results in degenerate polyhedra. After gluing, the “tacos” have 3 vertices, the middle diagrams have 2 vertices, and the right diagrams have 1 vertex, respectively.
Figure 7: An illustration of the Kreweras complement operation on non-crossing partitions. The parts of a partition π∈NC(8)\pi\in\mathrm{NC}(8) are drawn in blue, and the parts of the Kreweras complement K(π)∈NC(8)K(\pi)\in\mathrm{NC}(8) in red.
Figure 8: An illustration of the matchings involved in Proposition B.5 and the arguments afterwards. Gray regions represent vertices of a cactus graph α\alpha , three triangles joined at a vertex with one 4-cycle attached to one of those triangles at a different vertex. This graph has ∣V∣=10|V|=10 and ∣E∣=13|E|=13 . Black dots in those regions represent half-edges of α\alpha . In blue, we draw the matching α~\widetilde{\alpha} realizing the graph α\alpha ; if the gray regions are each contracted to a point and only blue edges are retained, then the resulting graph is the cactus α\alpha . In red, we draw the unique α\alpha -local matching β\beta that maximizes ∣cyc(α~,β)∣=∣E∣−∣V∣+1=4|\mathrm{cyc}(\widetilde{\alpha},\beta)|=|E|-|V|+1=4 ; its being α\alpha -local corresponds to making matches only within the gray regions.
More in this topic

Approximate Message Passing

See all 10 papers

Explore similar work

CardsList
Mar 15, 2026

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

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.

Yatin Dandi, David Gamarnik, Francisco Pernice +1

Statistical Physics of Computation Laboratory, École polytechnique fédérale de Lausanne (EPFL) CH-1015 Lausanne. · Sloan School of Management, Operations Research Center and Institute of Data, Systems and Society (IDSS), MIT. · CSAIL and LIDS, MIT.

Approximate Message PassingMean-Field TheoryGradient Descent Dynamics
AskPDF
Jun 28, 2025

On Universality of Non-Separable Approximate Message Passing Algorithms

Mean-field characterizations of first-order iterative algorithms -- including Approximate Message Passing (AMP), stochastic and proximal gradient descent, and Langevin diffusions -- have enabled a precise understanding of learning dynamics in many statistical applications. For algorithms whose non-linearities have a coordinate-separable form, it is known that such characterizations enjoy a degree of universality with respect to the underlying data distribution. However, mean-field characterizations of non-separable algorithm dynamics have largely remained restricted to i.i.d. Gaussian or rotationally-invariant data. In this work, we initiate a study of universality for non-separable AMP algorithms. We identify a general condition for AMP with polynomial non-linearities, in terms of a Bounded Composition Property (BCP) for their representing tensors, to admit a state evolution that holds universally for matrices with non-Gaussian entries. We then formalize a condition of BCP-approximability for Lipschitz AMP algorithms to enjoy a similar universal guarantee. We demonstrate that many common classes of non-separable non-linearities are BCP-approximable, including local denoisers, spectral denoisers for generic signals, and compositions of separable functions with generic linear maps, implying the universality of state evolution for AMP algorithms employing these non-linearities.

Max Lovig, Tianhao Wang, Zhou Fan

Department of Statistics and Data Science, Yale University · Halicioglu Data Science Institute, University of California, San Diego

Mean-Field TheoryApproximate Message Passing
AskPDF
May 30, 2026

Easy, robust approximate message passing for planted spike models

We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let ε\varepsilon be a sufficiently small constant, and suppose that X∈Rn×nX \in \mathbb R^{n \times n} is a Gaussian matrix with a planted rank-11 spike, and E∈Rn×nE \in \mathbb R^{n \times n} is an adversarially chosen matrix supported on an εn×εn\varepsilon n \times \varepsilon n principal minor. Let vAMP(X)v_{\mathrm{AMP}}(X) be the output of an AMP iteration on the uncorrupted matrix XX. We give a procedure that, given access only to the corrupted matrix Y=X+EY = X + E, computes a vector vALG(Y)v_{\mathrm{ALG}}(Y) which is O~(ε)\tilde{O}(\sqrt{\varepsilon})-close to vAMP(X)v_{\mathrm{AMP}}(X), for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and Z2\mathbb Z_2 synchronization. Our algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.

Misha Ivkov, Tselil Schramm

*Stanford University. · †Stanford University.

Random Matrix TheoryPrincipal Component AnalysisAdversarial RobustnessApproximate Message PassingSpectral Methods
AskPDF