Probabilistic inference is a key problem in statistics, signal processing and machine learning.
To make predictions on unobserved random quantities given observed data, averages over conditional distributions have to be computed. For high-dimensional inference problems, the resulting sums or integrals can usually not be performed exactly. To overcome
this problem, efficient approximate inference algorithms, known as message passing, have been developed [1]}. Prominent examples are belief propagation and expectation propagation [2]}, [3]}, [4]}, [5]}.
More recently, the so-called approximate message passing (AMP) algorithms
designed for probabilistic models on densely connected networks, have been applied
to various inference problems, e.g. Refs. [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]}, [15]}. Methods of statistical physics have played an important role in the design and the theoretical analysis of such algorithms, e.g., fixed points of AMP–style algorithms were shown to coincide with the solutions of
the advanced Thouless-Anderson-Palmer (TAP) mean-field equations developed in the statistical physics of disordered systems [16]}. This shows that under certain
statistical assumptions on network couplings, message passing algorithms
can achieve exact predictions in the thermodynamic limit of large systems.
Using techniques of information theory and statistical physics, exact solutions for the dynamics of the AMP-style message passing iterations have also become possible [17]}, [18]}, [19]}, [20]}, [21]}, [22]}, [23]}. So far, the theoretical analysis has concentrated on the simplest type of dynamics, the parallel update of all dynamical variables or nodes in the algorithm.
