On Universality of Non-Separable Approximate Message Passing Algorithms

Max Lovig; Tianhao Wang; Zhou Fan

math.STDate pending

On Universality of Non-Separable Approximate Message Passing Algorithms

Authors: Max Lovig, Tianhao Wang, Zhou Fan

Abstract

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.

Explore similar work

May 30, 2026cs.DS

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 \in \mathbb R^{n \times n}

is a Gaussian matrix with a planted rank-

1

spike, and

E \in \mathbb R^{n \times n}

is an adversarially chosen matrix supported on an

\varepsilon n \times \varepsilon n

principal minor. Let

v_{\mathrm{AMP}}(X)

be the output of an AMP iteration on the uncorrupted matrix

X

. We give a procedure that, given access only to the corrupted matrix

Y = X + E

, computes a vector

v_{\mathrm{ALG}}(Y)

which is

\tilde{O}(\sqrt{\varepsilon})

-close to

v_{\mathrm{AMP}}(X)

, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and

\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

Principal Component Analysis Message Passing Neural Networks Binary Spikes

Ask PDF

May 12, 2026cs.LG

On the Approximation Complexity of Matrix Product Operator Born Machines

Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, but their efficient approximation capability remains unclear. We characterize this boundary from both negative and positive perspectives. First, we prove that KL approximation is NP-hard for MPO-BMs in the continuous setting, ruling out universal efficient approximation in the worst case. Second, for score-based variational inference, we show that, under a locality and spectral-gap conditions on the loss-induced Hamiltonian, structured targets (e.g., path-graph Markov random fields) admit MPO-BM approximations with polynomial bond dimension and provable KL guarantees. Third, under the same locality structure, we prove that polynomially many score queries suffice to estimate the induced Hamiltonian and obtain such guarantees. Our results provide a theoretical characterization of when MPO-BMs are fundamentally hard to approximate and when they become efficiently learnable.

Chao Li, Zerui Tao, Yuchen Cong +2

Tensor Networks Variational Inference Approximation Algorithms Quantum Machine Learning Matrix Multiplication Hamiltonian

Ask PDF

Jul 21, 2026cs.LG

RAMP: Recognition parametrisation by Amortised Message Passing

A central aim of unsupervised learning is to uncover latent factors that explain dependencies among observations. Probabilistic models typically achieve this by introducing multiple latent variables linked through a graph of conditional relationships, with distributional parameters and their dependence learnt from data. Learning relies either on distributional choices that allow tractable belief propagation, or on approximations that scale poorly with model size and complexity. We build on the recently developed recognition-parametrised modelling paradigm to propose an alternative approach: RAMP, a method that implicitly defines latent structure by learning a flexible, nonlinear, amortised message-passing framework. We show that RAMP enables efficient likelihood-based recovery of latent-variable distributions within expressive nonlinear models acting on complex high-dimensional data.

Lior Fox, Kai Biegun, James Heald +3

Latent Variable Unsupervised Message Passing Neural Networks

Ask PDF