Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes the large-n dynamics of general first-order methods (GFOM) on both random and deterministic matrices by calculating the traffic distribution of the input matrix. They compute the traffic distribution for deterministic matrices like Walsh-Hadamard and discrete sine/cosine transforms, resolving conjectures about GFOM dynamics on these inputs. The authors also design a new approximate message passing (AMP) iteration that generalizes to new input types and provides a combinatorial interpretation of the Onsager correction.
GFOM dynamics on structured deterministic matrices, such as Walsh-Hadamard, can be understood and even exploited with a new AMP iteration, unifying previous variants and generalizing to new input types.
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).