# On Universality of Non-Separable Approximate Message Passing Algorithms

arXiv: https://arxiv.org/abs/2506.23010 · HTML: https://mlsanity.com/paper/2506.23010/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2025.

## Built on by (most cited first, 4 of 4)

- [Universality of first-order methods on random and deterministic matrices](https://mlsanity.com/paper/2604.11729/) (2026)
- [Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models](https://mlsanity.com/paper/2512.19334/) (2025)
- [Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing](https://mlsanity.com/paper/2604.27883/) (2026)
- [Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing](https://mlsanity.com/paper/2610.05327/) (2026)

## Abstract (arXiv)

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.