Exact solution to the random sequential dynamics of a message passing algorithm
arXiv:2101.01571 · doi:10.1103/PhysRevE.103.L030101
Abstract
We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. We derive exact results for the two-time correlation functions and the speed of convergence. The {\em de Almedia-Thouless} stability criterion of the static problem is found to be necessary and sufficient for the global convergence of the random sequential dynamics.
Accepted for publication in Physical Review E Letter
References in corpus (11)
- Message Passing Algorithms for Compressed Sensing
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Inverse statistical problems: from the inverse Ising problem to data science
- Replica Field Theory for Deterministic Models (II): A Non-Random Spin Glass with Glassy Behavior
- Statistical physics-based reconstruction in compressed sensing
- Mean-Field Equations for Spin Models with Orthogonal Interaction Matrices
- Expectation propagation as a way of life: A framework for Bayesian inference on partitioned data
- A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
- Memory-free dynamics for the TAP equations of Ising models with arbitrary rotation invariant ensembles of random coupling matrices
- A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines
- Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach