Approximate Survey Propagation for Statistical Inference <s> Point-wise convergence of ASP <s> From a variational principle the authors derive a closed set of equations for the spin glass mean-field theory in terms of a local magnetisation on long timescales and a distribution of gradually frozen local fields. These equations are useful for deriving general relations and they find that the frozen field obeys a Langevin equation. Numerical solutions of the equations are obtained at T=0. The local field distribution shows a linear behaviour for small fields. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> Point-wise convergence of ASP <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> Point-wise convergence of ASP <s> We reconsider the one-step replica-symmetry-breaking (1RSB) solutions of two random combinatorial problems: k-XORSAT and k-SAT. We present a general method for establishing the stability of these solutions with respect to further steps of replica-symmetry breaking. Our approach extends the ideas of [A.Montanari and F. Ricci-Tersenghi, Eur.Phys.J. B 33, 339 (2003)] to more general combinatorial problems. It turns out that 1RSB is always unstable at sufficiently small clauses density alpha or high energy. In particular, the recent 1RSB solution to 3-SAT is unstable at zero energy for alpha<alpha_m, with alpha_m\approx 4.153. On the other hand, the SAT-UNSAT phase transition seems to be correctly described within 1RSB. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> Point-wise convergence of ASP <s> We consider the problem of coloring Erdös-Rényi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it to the ground state, we provide evidence that the 1RSB solution gives exact threshold values c(q) for the transition from the colorable to the uncolorable phase with q colors. We also study the asymptotic thresholds for q>>1 finding c(q) =2q ln q-ln q-1+o (1) in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem. <s> BIB004
The inclusion of a 1RSB structure into the ASP algorithm extends the region of parameters in which the algorithm converges point-wise with respect to AMP. Note that the range of parameters for which AMP does not converge point-wise corresponds exactly to the range of parameters for which the large iteration time behavior of ASP depends on the Parisi parameter s, see Fig. 8 , where below the vertical line is exactly where the replicon eigenvalue eq. (35)  Interestingly, this corresponds to a well known quantity in the replica theory BIB002 BIB001 , that appears in the stability of the 1RSB solution against further breaking of replica symmetry. In in this case (see Appendix A) two kind of instabilities are often discussed  BIB003 BIB004  and the two eigenvalues that express the 1RSB stability can be written as where with V (1) , V (0) given by Eqs. (73)-(74) and x, x (0) and W being random variables distributed according P (x), P (0) (x) and a standard Gaussian distribution, respectively. A change of variable, as in Appendix A, shows that λ ASP = λ I : the convergence of the ASP algorithm is determined by the first-type instability towards further replica symmetry breaking, just as it is for Survey Propagation BIB003 BIB004  . In the region of RS stability ∆ (0) = V (0) = 0 and the two eigenvalues are equal and coincide with the RS replicon eigenvalue in Eq.  . To understand the meaning of these two eigenvalues consider that the 1RSB structure consists of equivalent metastable states whose distance from each other is given by Q. There are then two ways in which a further hierarchical level of RSB states can appear: the 1RSB states can aggregate in a way to establish a new scale of distance between states (type I instability, associated to negative λ I ), or each metastable state can split into a hierarchy of new states (type II instability, associated to negative λ II ). Let us discuss the behavior of the eigenvalues as we move away from the Nishimori line. To be concrete, we keep referring to the case of the planted SK model Eq. (8), cf. Fig. 11 . In the RS stability region, the two eigenvalues are equal and positive. At the boundary of the RS stability region, the eigenvalues become marginal and the replica symmetry gets broken: beyond this line the solution of the 1RSB-SE depends on s and so do λ I and λ II . For the low-rank matrix estimation problem, the transition is towards a full replica symmetry broken (FRSB) state BIB002 , so that the 1RSB states are always unstable and at least one among λ I and λ II is negative beyond the RS instability line. Nevertheless, unlike the RS algorithm laid out by AMP, in ASP there is a scale of distance among state -tuned via the s parameter -so that the algorithm can converge point-wise also when the inner structure of the states is more complicated than 1RSB. In Fig. 11 we show the value of λ I and λ II crossing the RS stability line for several values of s. We see λ I is positive for s sufficiently small, indicating that ASP converges point-wise for such values also in the RSB region (cf. Fig. 6 ).