Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <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> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <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> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> The metastable states of a glass are counted by adding a weak pinning field which explicitly breaks the ergodicity. Their entropy, that is the logarithm of their number, is extensive in a range of temperatures $T_G<T<T_C$ only, where $T_G$ and $T_C$ correspond to the ideal calorimetric and kinetic glass transition temperatures respectively. An explicit self-consistent computation of the metastable states entropy for a non disordered model is given. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass problem at a level of approximation which is equivalent to a one step replica symmetry breaking solution. The results compare well with numerical simulations. The method can be used for many finite connectivity problems appearing in combinatorial optimization. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold α c are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below α c , where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability. <s> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> In this note we explain the use of the cavity method directly at zero temperature, in the case of the spin glass on a lattice with a local tree like structure, which is the proper generalization of the usual Bethe lattice to frustrated problems. The computation is done explicitly in the formalism equivalent to “one step replica symmetry breaking;” we compute the energy of the global ground state, as well as the complexity of equilibrium states at a given energy. Full results are presented for a Bethe lattice with connectivity equal to three. The main assumptions underlying the one step cavity approach, namely the existence of many local ground states, are explicitely stated and discussed: some of the main obstacles towards a rigorous study of the problem with the cavity method are outlined. <s> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> In this work, we consider compressed sensing reconstruction from M measurements of K-sparse structured signals which do not possess a writable correlation model. Assuming that a generative statistical model, such as a Boltzmann machine, can be trained in an unsupervised manner on example signals, we demonstrate how this signal model can be used within a Bayesian framework of signal reconstruction. By deriving a message-passing inference for general distribution restricted Boltzmann machines, we are able to integrate these inferred signal models into approximate message passing for compressed sensing reconstruction. Finally, we show for the MNIST dataset that this approach can be very effective, even for M <; K. <s> BIB007 </s> Approximate Survey Propagation for Statistical Inference <s> III. THE APPROXIMATE SURVEY PROPAGATION: A 1RSB VERSION OF AMP <s> Despite decades of work, gaining a first-principle understanding of amorphous materials remains an extremely challenging problem. However, recent theoretical breakthroughs have led to the formulation of an exact solution in the mean-field limit of infinite spatial dimension, and numerical simulations have remarkably confirmed the dimensional robustness of some of the predictions. This review describes these latest advances. More specifically, we consider the dynamical and thermodynamic descriptions of hard spheres around the dynamical, Gardner and jamming transitions. Comparing mean-field predictions with the finite-dimensional simulations, we identify robust aspects of the description and uncover its more sensitive features. We conclude with a brief overview of ongoing research. <s> BIB008
AMP is an established approach to analyze systems with a ferromagnet-like transition, where one expects to have just two possible fixed-points of the iterations. There are, however, situations where there exists a huge number of fixed-points for the AMP equations. In particular, we have shown in the previous section that in the low-rank matrix estimation problem with mismatching models there is a region where the replica symmetry is broken and the AMP algorithm does not converge. In this case one needs to use the cavity method in conjunction with a replica symmetry breaking (RSB) approach, as was introduced by Mézard and Parisi BIB005 BIB004 BIB006 . In the following we show how this approach can be carried out for the low-rank matrix estimation problem and how this provides a systematic method to deal with mismatching models in a natural way. Note that we need to insist on the notion of independence of the noise elements, that is an essential for belief-propagation-based approaches to work. A. Derivation of the ASP algorithm for the low-rank matrix estimation problem We derive here the 1-step replica symmetry breaking (1RSB) approximate massage passing, that we call approximate survey propagation (ASP) algorithm, for the low-rank matrix estimation problem. To derive the correct equations in this case, let us consider a replicated inference problem, basically turning the method of Monasson BIB003 into a message passing algorithm. Given the matrix Y ij and a = 1, . . . , s, being s the number of real replicas, we assume that where ξ (a) ij are independent Gaussian noises with zero mean and variance ∆. The partition function becomes where w j / √ N and P X (x) and g have the same definition as the previous sections, cf. Eq. (2). If s = 1 we get back the usual inference problem of Eq. (1). The factor graph representing the structure of the replicated posterior measure whose partition function is described in Eq. BIB007 . The variable nodes are replicated variables x i ≡ {x In order to evaluate the marginals over the variables {x i }, we need to write the BP equations for the replicated system. In the following let us omit normalization factors when they are irrelevant (they can be determined a posteriori). The BP equations are where we have introduced the notation x i = {x i }. This follows directly from the factor graph represented in Fig. 5 . At this point we introduce a 1RSB parametrization for the cavity distributions The form of this ansatz elucidates why we are considering a replicated system: if the posterior measure Eq. (2) develops a 1RSB structure, the phase space of the solutions of the inference problem gets clustered in exponentially many basins of solutions BIB002 . Therefore, if we consider a set of s real copies of the same inference problem and we infinitesimally couple them, they will acquire a finite probability to fall inside the same cluster of solutions. This line of reasoning is exactly the same as the one considered to describe the real replica approach for glasses BIB003 BIB008 and the ansatz of Eq. (42) reproduces the infinite dimensional caging ansatz (at the 1RSB level) for hard spheres in infinite dimension   . The ansatz of Eq. (42) allows for three relevant correlation functions where the averages are taken with the measure defined in Eq. BIB001 . The last two lines give access to the correlation between cavity messages from one copy to another. Note that if ∆ (0) j→ij = 0 different replicas become uncorrelated. Therefore in the limit ∆ (0) j→ij → 0 one recovers the replica symmetric AMP. Equivalently, if one fixes s = 1 the ansatz reduces naturally to the RS parametrization for the cavity messages and one gets back again to the AMP algorithm. Given the 1RSB ansatz, we can plug Eq. (42) in Eq. (41) to get where the matrices S ij andR ij are the same as introduced in Eq. (7). Plugging this result inside the first one of Eqs. (41) we get where we have defined We can now close the equations. We have where we have introduced the function Using Eqs. (43), we obtain i→ij . The Eqs. (52)- (54) together with Eqs. (45)- (47) constitute the 1RSB-BP equations, within the Gaussian ansatz of Eq. (42), and with Parisi parameter s. Finally, the moments of the marginal distributions are obtained by introducing through which we havex where the square brackets [·] indicate the average over the replicated posterior measure defined in Eq. BIB007 . The complexity of the 1RSB-BP algorithm described in Eqs. (45)- (47), (52)- (54) can be reduced by working directly with the moments of the real marginals instead using the moments of the cavity marginals. This TAPification procedure is well known in inference problems (cf. Sec. II A 1 and references therein). The result is the ASP algorithm for the low-rank matrix estimation problem: Strictly speaking we have different algorithms for different values of the Parisi parameter s. We will comment more about the use of this parameter in Sec. II C. Note that for s = 1 the equations depend only on σ i = ∆ (1) and the algorithm reduces to the Low-RAMP Eqs. (9)- (12) with B i = T i and Observe also that, similarly to what happens in Low-RAMP, the equations can be further simplified replacing S 2 ij by its mean, without changing the leading order in N . This simplification allows to express Eqs. (59)-(61) simply as matrix multiplications, cf. Sec. III B 2. The introduction of a RSB structure in the algorithm allows ASP to converge point-wise and to obtain a low MSE also in regions where the RS solution is unstable and AMP does not converge point-wise, cf. Fig. 6 . The fixed-points of the ASP equations are stationary points of the following free energy: This free energy is known in statistical physics literature as the 1RSB potential and is useful to compare different fixed-points at same s, in the same spirit of the RS case. Note that when one tries to compare fixed-points of ASP that are associated to different values of s, the extremization of this free energy does not correspond to the minimum MSE, cf. Sec. III C.