Approximate Survey Propagation for Statistical Inference <s> MSE as a function of the Parisi parameter s <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> MSE as a function of the Parisi parameter s <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
The most interesting quantity from the inference point of view is the mean-squared error reached by the ASP algorithm for different values of the Parisi parameter s. In Fig. 8 we show the MSE for the planted SK model for two values of ∆ 0 (the two panels) as a function of ∆ for various values of the Parisi parameter s. First we note that in the whole region of convergence of AMP, i.e. in the RS stability region, ASP converges for every value of s to the same fixed point as AMP, cf. Fig. 8 . In this sense, ASP provides a strong test (on a single instance) of the replica symmetry of the problem: if ASP converges to the same fixed point for any value of s, we have an argument to claim replica symmetry (in absence of discontinuous phase transitions). The horizontal line in Fig. 8 is the optimal MSE reached by AMP in the Bayes-optimal case where ∆ = ∆ 0 . The black line corresponds to the MSE reached for the equilibrium value of s * (∆) for which the complexity Eq. (81) vanishes, or equivalently where the free energy Eq. (80) is maximized. These are the states dominating the Boltzmann measure if 1RSB was the correct description of the system (which it is not in this model, as well known and explained in the next section). We denote by s mMSE the value of the Parisi parameter that minimizes the MSE. Quite remarkably, we see in Fig. 8 that for some cases the Bayes-optimal MSE is reached also when ∆ = ∆ 0 for a particular value of the Parisi parameter that we denote s opt . This is also seen in Fig. 12 left panel where the MSE is plotted as a function of s for a variety of values of ∆. Moreover, we remark and illustrate in Fig. 9 that the value of the Parisi parameter s mMSE that minimizes the MSE, and s opt for which the Bayes optimal error is reached, are unrelated to the equilibrium value s * . Note that, somehow counter-intuitively, very closely under the RS instability the optimality condition M = Q cannot typically be achieved for any value of s (see, e.g., the yellow curve corresponding to ∆ = 0.6 in Fig. 12 ): in this case the 1RSB solution depends weakly on s and one explores only a narrow interval in M and Q (that may not include the case M = Q > 0) before jumping to the trivial solution M = Q = 0. In Fig. 9 we show the s opt , and the value s mMSE for which the MSE is minimum at given ∆ (when s opt exists the two are equal) and the region where MSE < 1 for the SK model with ∆ 0 = 0.84. Near the RS instability the MSE depends weakly on s and the s opt does not exist: in this case the minimum MSE is obtain for the minimum s for which the solution is not trivial (green line). In the same figure we also plot the value of s * that extremizes the Bethe free energy of the model: it is well distinct from s opt . To clarify the origin of the above observation that Bayes-optimal error can be restored for s opt we remind that in Sec. II C we noticed that the inference can be optimal out of the Nishimori line. More precisely, we have put forward a hypothesis that the estimation is optimal every time the Nishimori condition M = Q > 0 is restored. We showed one example in Fig. 4 : introducing a nonzero density of zeros in the prior distribution, it is possible to obtain optimal estimation in the SK model using AMP out of Nishimori. The ASP algorithm naturally introduces a free parameter in the form of the Parisi parameter s, cf. Eq. (39). In Fig. 10 we illustrate that minimization of the MSE as a function of s is again related to restoration of the Nishimori condition M (s) = Q(s) > 0. This can also be seen analytically by computing the derivative of the MSE with respect to the parameter s at the fixed-point of 1RSB-SE. In the replica theory notation BIB002 BIB001 we can express this derivative, cf. Appendix B, as while  So, if there exists a value of s such that D(s, h) is zero for all h, we have that for such value M = Q and MSE is extremized. This is exactly what we observe: at the solution where MSE is minimum the function D(s, h) is zero for all h (and so M = Q > 0). In this sense we could define the optimal s opt as the value for which at the fixed-point of 1RSB-SE it happens that (if exists) It seems to us that there should be a deeper theoretical reason behind the observation that the restoration of the Nishimori condition leads to the optimal estimation error. We have not found it and let this question for future work.