# Approximate Survey Propagation for Statistical Inference

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2018.

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

- [The effect of priors on Learning with Restricted Boltzmann Machines](https://mlsanity.com/paper/2412.02623/) (2024)
- [Bayesian reconstruction of memories stored in neural networks from their connectivity](https://mlsanity.com/paper/2105.07416/) (2021)
- [Analysis of Random Sequential Message Passing Algorithms for Approximate Inference](https://mlsanity.com/paper/2202.08198/) (2022)
- [Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learning](https://mlsanity.com/paper/2201.09986/) (2022)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [Perfect reconstruction of sparse signals using nonconvexity control and one-step RSB message passing](https://mlsanity.com/paper/2512.17426/) (2025)

## Abstract (arXiv)

Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M=Q>0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure.