Approximate Survey Propagation for Statistical Inference

Abstract

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.

arXiv comment37 pages, 14 figures

References in corpus (19)

• Message Passing Algorithms for Compressed Sensing
• The Bethe lattice spin glass revisited
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Fractal free energy landscapes in structural glasses
• The structural glass transition and the entropy of the metastable states
• Statistical physics of inference: Thresholds and algorithms
• Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Exact theory of dense amorphous hard spheres in high dimension. III. The full RSB solution
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Emergence of Compositional Representations in Restricted Boltzmann Machines
• Mean-field message-passing equations in the Hopfield model and its generalizations
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• A note on classical ground state energies
• Statistical Mechanics of High-Dimensional Inference
• Absence of Replica Symmetry Breaking in a Region of the Phase Diagram of the Ising Spin Glass

Cited by in corpus (12)

• Mean-field inference methods for neural networks
• Disordered Systems Insights on Computational Hardness
• Solving the fully-connected spherical $p$-spin model with the cavity method: equivalence with the replica results
• Field theory for zero temperature soft anharmonic spin glasses in a field
• The effect of priors on Learning with Restricted Boltzmann Machines
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Proliferation of non-linear excitations in the piecewise-linear perceptron
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• The planted XY model: thermodynamics and inference
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization