Approximate Survey Propagation for Statistical Inference <s> C. Optimality and restored Nishimori condition <s> It is shown that the power expansion of the Gibbs potential of the SK model up to second order in the exchange couplings leads to the TAP equation. This result remains valid for the general (including a ferromagnetic exchange) SK model. Theorems of power expansions and resolvent techniques are employed to solve the convergence problem. The convergence condition is presented for the whole temperature range and for general distributions of the local magnetisations. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> C. Optimality and restored Nishimori condition <s> We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold αc separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) αc. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message-passing procedure which generalizes the usual methods like Sum-Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> C. Optimality and restored Nishimori condition <s> This paper has been withdrawn due to a critical error near equation (71). This error causes the entire argument of the paper to collapse. ::: Emmanuel Candes of Stanford discovered the error, and has suggested a correct analysis, which will be reported in a separate publication. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> C. Optimality and restored Nishimori condition <s> In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or"free energy") in Bayesian inference problems. The proof techniques that have emerged appear to be quite general, despite they have been worked out on a case-by-case basis. Unfortunately, a common point between all these schemes is their relatively high level of technicality. We present a new proof scheme that is quite straightforward with respect to the previous ones. We call it the stochastic interpolation method because it can be seen as an extension of the interpolation method developped by Guerra and Toninelli in the context of spin glasses, with a trial"parameter"which becomes a stochastic process. In order to illustrate our method we show how to prove the replica formula for three non-trivial inference problems. The first one is symmetric rank-one matrix estimation (or factorisation), which is the simplest problem considered here and the one for which the method is presented in full details. Then we generalize to symmetric tensor estimation and random linear estimation. In addition, we show how to prove a tight lower bound for the mutual information of non-symmetric tensor estimation. We believe that the present method has a much wider range of applicability and also sheds new insights on the reasons for the validity of replica formulas in Bayesian inference. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> C. Optimality and restored Nishimori condition <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> BIB005
The Bayes-optimal setting, as reminded in Sec. II B, is a very special situation: the Nishimori condition Eq. BIB004 guarantees that the replica symmetry is preserved and that AMP is optimal (in absence of a 1st order phase transition). One consequence of the Nishimori condition is that the typical overlap with the ground truth M and the self-overlap Q, as defined in Eqs. BIB003 , are equal. In this case the MSE is then given by and the minimum MSE is obtained at the maximum overlap M . For mismatching models M and Q are typically different from each other and it is not immediate to realize under what conditions the MSE is minimized. We highlighted this property in the main panel of Fig. 2 : apart from the trivial solutions M = Q = 0 (for large ∆ 0 and ∆) and M = Q = 1 (for very small ∆ 0 ), the overlap with the ground truth M and the self-overlap Q are very close only near the Nishimori line. The Nishimori line is also the region in which AMP is optimal, so it is spontaneous to ask what is the relation (if any) between these two properties in a general setting. Consider a situation in which we have two or more parameters to tune. These can be parameters in the prior, the variance of the noise ∆ or also the free parameters in the general belief-propagation equations, see for example the parameter s for the ASP algorithm that we will describe in Eqs. (59)-(64). The fundamental question is then for which set of values for the parameters it is possible to obtain optimal estimation error, and how to find them algorithmically. One evident answer is that if all the parameters are chosen to exactly match the values of the ground truth distribution, one ends up on the Nishimori line and then we know that the inference is optimal, and the MSE minimum. But this is not the unique answer. Let us illustrate what we found with a simple example. The data Y are generated by the planted SK model with ∆ 0 = 0.8. In this case the Bayes-optimal inference, knowing the correct prior and noise, would get MSE = 0.776. Consider now instead a situation in which one (wrongly!) assumes that the variance of the noise is ∆ = 0.5 but also, being not sure about the correct prior, assume a more general Rademacher-Bernoulli prior with some unknown parameter ρ. In Fig. 4 we show the values of M , Q and MSE obtained by the SE Eqs. (21)- (23) as a function of ρ while ∆ is kept fixed at 0.5. Taking ρ = 1, which corresponds to the correct prior, we obtain Q 0.521, M 0.29 and MSE 0.94, considerably worse than the Bayes-optimal error. The maximum M is obtained for ρ 0.95, where Q 0.48 and MSE 0.90. But, if we look to restore the optimality condition M = Q, we are led to accept the value ρ = 0.623: here M = Q = 0.224 and MSE = 0.776, equal to the value obtained by Bayes-optimal inference. The above observations leads us to a hypothesis: Any combination of the values of parameters that restores the condition M = Q, achieves the same performances of the Bayes-optimal setting. We tested this hypothesis in several settings of the low-rank matrix estimation problem, including sparse cases with first order transition BIB005 . While we always found it true, the underlying reason for this eludes us and is left for future work. The optimality from the restoration of the M = Q condition is relevant in cases in which we assume a wrong functional form of prior, as in the previous example, so that it is indeed impossible to actually reduce to the Bayes-optimal setting. Note that it is nontrivial to turn the above observation into an algorithmic procedure. A common parameter learning procedure is to maximize the Bethe free energy of the model, Eq. BIB002 . This procedure gives asymptotically the Bayes-optimal parameters, if learning of the exact prior and noise is possible. Nevertheless, if the functional form of the prior and noise is incorrect, this procedure does not return the optimal values of the parameters -that, in our hypothesis, would be the ones associated with the restoration of the M = Q condition. In the previous example, the Bethe free energy is monotonically increasing in [0, 1] and has a local maximum only at ρ 1.26, where the prior is not a well-defined probability distribution and the MSE is larger than 1, cf. Fig. 4 . It is interesting to look at the RS eigenvalue Eq.  BIB001 , the only solution is the trivial M = Q = 0, MSE = 1. These two extremes give the finite interval 0.42 ρ 0.90 in which one should indeed look to find the optimal ρ. We will discuss further about this observation in Sec. III C about the use of ASP.