Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> We prove that the distribution functions of magnetization and spin glass order parameter coincide on the Nishimori line in the phase diagram of the ± J Ising model in any dimension. This implies absence of replica symmetry breaking because the distribution function of magnetization consists only of two delta functions, suggesting the same simple structure for the distribution of the spin glass order parameter. It then follows that the mixed (glassy) phase, where ferromagnetic order coexists with a complex phase space structure, should lie below the Nishimori line if it exists at all. We also argue that the AT line that marks the onset of RSB with a continous distribution of the spin glass order parameter (again, if it exists) would start with an infinite slope from the multicritical point where paramagnetic, ferromagnetic and spin glass phases merge. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> 1. Mean-field theory of phase transitions 2. Mean-field theory of spin glasses 3. Replica symmetry breaking 4. Gauge theory of spin glasses 5. Error-correcting codes 6. Image restoration 7. Associative memory 8. Learning in perceptron 9. Optimization problems A. Eigenvalues of the Hessian B. Parisi equation C. Channel coding theorem D. Distribution and free energy of K-Sat References Index <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers --in particular-- the analysis of generalized AMP, introduced by Rangan, and of AMP reconstruction in compressed sensing with spatially coupled sensing matrices. The proof technique builds on the one of [BM11], while simplifying and generalizing several steps. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> The replica extension theory has been developed for the purpose of investigating spin glass systems in the replica symmetry breaking phase. The replica extension theory is a replica theory for a specific sample and has the scheme of the one-step replica symmetry breaking ansatz. In this paper, using the Plefka expansion, we propose the perturbative expansion of Gibbs free energies of Ising systems with the replica extension theory, and we derive the explicit form of the second-?and third-order approximations. Our Plefka expansion systematically provides perturbative approximations taking the one-step replica symmetry breaking into account. In some numerical experiments, we show that our perturbative approximations are quantitatively superior to conventional perturbative approximations that do not take the one-step replica symmetry breaking into account in the spin glass phase. <s> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> We propose an iterative scheme for the solutions of the TAP-equations in the Sherrington–Kirkpatrick model which is shown to converge up to and including the de Almeida–Thouless line. The main tool is a representation of the iterations which reveals an interesting structure of them. This representation does not depend on the temperature parameter, but for temperatures below the de Almeida–Thouless line, it contains a part which does not converge to zero in the limit. <s> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic. <s> BIB007 </s> Approximate Survey Propagation for Statistical Inference <s> B. Phase diagram and convergence of AMP out of the Nishimori line <s> This article is an extended version of previous work of the authors [40, 41] on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a paralel with the study of vector-spin glass models - presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low- RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as different as the Sherrington-Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayes-optimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods. <s> BIB008
In the Bayes-optimal setting, where the knowledge of the model is complete as in Eq. (3), the statistical physics analysis of the problem presents important simplifications known as the Nishimori conditions BIB003 . Specifically, as direct consequence of the Bayesian formula and basic properties of probability distributions, it is easy to see that BIB007 Bayes-optimal: where f is a generic function and x 1 , x 2 and x are distributed according the posterior while The most striking property of systems that verify the Nishimori conditions is that there cannot be any replica symmetry breaking in the equilibrium solution of these systems 2 BIB002 . This simplifies considerably the analysis of the Bayes-optimal inference. From the algorithmic point of view, the replica symmetry assures that the marginals are asymptotically exactly described by the belief-propagation algorithms BIB007 . In this sense, AMP provides an optimal analysis of Bayes-optimal inference. In real-world situations it is, however, difficult to ensure the satisfaction of the Nishimori conditions, as the knowledge of the prior and of the noise is limited and/or the parameter learning is not perfect. The understanding of what happens beyond the Bayes-optimal condition is then crucial. Using state evolution Eqs. (21)- (23) -or equivalently replica theory for a replica symmetric ansatz -one can obtain the phase diagram of Low-RAMP in a mismatching models setting. As soon as we deviate from the Bayes-optimal setting and mismatch the models, the Nishimori conditions are not valid anymore and so the replica symmetry is not guaranteed and Low-RAMP is typically not optimal. If the mismatch is substantial, the replica symmetry gets broken and we enter in a glassy phase. To illustrate the behaviour of AMP out of the Bayes-optimal case, let us consider the planted SherringtonKirkpatrick (SK) model BIB001 , a well-known model both in computer science and physics communities. This is a particular case of the low-rank matrix estimation model Eq. (1) for a bimodal prior, cf. Eq. BIB004 . The output noise is Gaussian with the assumed variance ∆ mismatching the ground-truth variances ∆ 0 , cf. Eqs. (7), BIB005 . In Fig. 1 we show the phase diagram of the model obtained by the SE Eqs. (21)- (23) as ∆ and ∆ 0 are independently changed. The dashed line is the Nishimori line where the Bayes-optimal condition ∆ = ∆ 0 holds. For ∆ 0 > 1 the signal/noise ratio is too low and the estimation is impossible, M is always zero and MSE ≥ 1. Note that a MSE larger than 1 is worse than the error achieved by a random guess from the prior. At ∆ 0 = 1, the inference starts to be successful only on the Nishimori line. As one is further and further away from the Nishimori line, the algorithm needs a lower and lower value of noise in order to achieve a positive overlap M and a MSE lower than random guess. In particular, if ∆ is too large, i.e. ∆ > 1, one always reaches the trivial fixed point M = Q = 0. The case ∆ → 0 is also especially meaningful for an evaluation of the MAP estimator Eq. (5). In this case, the value of the overlap with the ground truth M is zero till ∆ 0 = 2/π ∼ 0.6366 BIB003 while the MSE is larger than 1 till ∆ 0 0.55, almost half than the equivalent threshold on the Nishimori line. in all the phase diagram. Single finite size instances of Low-RAMP do not converge point-wise too far from Nishimori line, cf. Fig. 2 . The analysis of the point-wise convergence on single instances of Low-RAMP can be obtained looking at the Hessian eigenvalues of Low-RAMP equations. A simple way to derive a necessary convergence criterium is to ask whether or not the fixed-point of AMP is stable with respect to weak, infinitesimal, random perturbations. Let us see how it can be derived with the notations of section II A 4. If we perform, in Eq. (28), the perturbation B t → B t + t , where is a i.i.d. infinitesimal vector sampled from N (0, ), then we may ask how this perturbation is carried out at the next step of the iteration. From the recursion (28)- (31), we see that (a) b t+1 is not modified to leading order, as η (B + δB) = η (B) + δBη (B) and the average in (30) makes the perturbation of The 2 norm of the perturbation has thus been multiplied, up to a constant E(S 2 ) = ∆ 0 /∆ 2 , by the empirical average of η (B). The fixed-point will be stable if the perturbation does not grow. This yields, coming back to the main notations of the article, to the following criterion: For positive λ the perturbation decreases and AMP algorithm converges, for negative λ it grows and the algorithm does not converge. Interestingly, condition (35) is equivalent to the stability of replica symmetric (RS) solutions in the replica theory given by RS replicon  (and indeed BIB006 has shown rigorously in the SK model, convergence of the AMP algorithm in a phase where the replica symmetric solution is stable). The line where the RS solution becomes unstable (and Low-RAMP stops converging point-wise) is shown in Fig. 1 with a yellow line. Note that, as expected, the RS stability line lies always below the Nishimori line and the two touch at the tri-critical point ∆ = ∆ 0 = 1. For small ∆ 0 , the stability line is roughly given by ∆ 4 ∆ 0 /(2π) exp(−1/(2∆ 0 ))/3 and it touches the ∆ = 0 axis only for ∆ 0 → 0. This means that for any finite ∆ 0 the RS solution becomes always unstable for ∆ small enough. The stability line is always above the M = 0 line, cf. Fig. 1 . Note that it is possible to get RS stable solutions with MSE > 1: so it is possible that AMP converges point-wise to something worse than random guess. In Fig. 2 we show the results obtained by running Low-RAMP for single instances of the same problem for N = 5000. We iterate the Low-RAMP equations, without any damping, for 10 3 steps or we stop when the average change of the variables in a single step of iteration is less than 10 −8 . The four regions highlighted in Fig. 1 are well distinguishable. We also show the value of |M − Q|, which is zero on the Nishimori line. In particular, it is clear that the point-wise convergence is very fast (less than 100 iterations) well inside the RS stability region, then the convergence time increases rapidly at the boundary of the RS stability region and then stops converging point-wise outside of it. The scenario illustrated in this section for SK is quite general within low-rank matrix estimation problems. Some differences arise when x is very sparse: in this case on the Nishimori line there is a first order transition BIB008 and the scenario becomes more complicated, with the coexistence of different phases close to the transition.