Spin glasses: A challenge for mathematicians. Cavity and mean field models.

*(English)*Zbl 1033.82002
Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge 46. Berlin: Springer (ISBN 3-540-00356-8/hbk). ix, 586 p. (2003).

Spin glasses are the prime example of many particle systems with highly irregular and non-cooperative interactions. The mathematical models for such systems that were proposed in the 1970’s are formally rather simple spin systems of the Ising type: one considers a graph \(\mathbf G\) and places spin variables \(\mathbf s_i\) on each vertex \(i\). Each \((ij)\) is equipped with an random variable \(J_{ij}\) that represents the interaction between spins. The key object of interest is the Hamiltonian function \(H_\mathbf G(\mathbf s;J)=\sum_{(ij)\in \mathbf G}J_{ij}\mathbf s_i\mathbf s_j\). One is interested in Gibbs measure \(e^{- \beta H_\Gamma}/Z_{\beta,N}\) as a function of \(\beta\) for typical realizations of the couplings \(J\). The subject of the book concerns mean field spin glasses, in which case \(\mathbf G\) is the complete graph on \(N\) vertices.

From a purely mathematical point of view, the SK model can be described as a Gaussian process on the hypercube \(\{-1,1\}^N\). The theoretical physics community, through an ingenious intuition of Giorgio Parisi, has devised methods to compute fine properties of these systems, such as the value of \(\lim_{N\uparrow\infty} \max_{\mathbf s}N^{-1} H_N(\mathbf s)\), that were unaccessible to the conventional tools of mathematical analysis. That the method of Parisi [see M. Mézard, G. Parisi and M. A. Virasoro, Spin glass theory and beyond, Lect. Notes Phys. 9, Teaneck, NJ (1987; Zbl 0992.82500)] was from a mathematical point of view obscure, to say the least, was motivation enough for the author to set out a systematic analysis of the problem with rigorous mathematical tools. The book gives a comprehensive account of this endeavor by its author, as well as some selected works of other people in the same field.

The mathematics in this problem involved is not limited to the SK model, nor is it to Gaussian processes on the hypercube. In fact, it had been long noticed that a great number of other problems that are highly relevant in diverse application areas fall into the same category. These include, but are not limited to, models of neural networks, such as perceptron models and the Hopfield model, the \(K\)-SAT and other problems from computer science, which are all covered here.

The approach presented here orbits around the so-called cavity method. The cavity method essentially consists in the attempt to compute key quantities of interest (functionals of the random process at hand) by inductions over the number \(N\) (the volume). That is, given a function \(F_N\) of the process, one tries to derive a recursion relation for this function in the variable \(N\). Usually, in this attempt it turns out that no closed form can be achieved, and a number of new functions have to be introduced. The goal is to show that it is enough to introduce a finite set of such functions, while all further terms produced in the program can be treated as error terms. The limit of the function \(F_N\) can then be obtained as the solution of a fix-point equation. This basic idea was present in non-rigorous work of Parisi, Mézard and others, and the first attempt to exploit it for rigorous work was made by Pastur and Shcherbina in the early 1990’s, but Talagrand has turned this a powerful tool to prove that results obtained with the help of the replica method at least in the simpler situations where so-called “replica symmetry” holds. Unfortunately, the book appeared too early to include the last triumph of the method, the author’s announced proof of the correctness of the Parisi solution of the SK model in general, based on a brilliant and ingenious idea of F. Guerra [Broken replica symmetry bounds in the mean field spin glass model. Commun. Math. Phys. 233, 1–12 (2003; Zbl 1013.82023)] (the latter, fortunately, is explained in Section 2.11.).

The book is divided into 8 Chapters and an appendix. The first explains some basic ideas in the simple setting of the Random Energy model, i.e. in the context of independent random variables. This allows the reader to get acquainted to some of the simpler techniques in a context that is easy to grasp.

The second chapter is devoted to the standard Sherrington-Kirkpatrick model. The bulk of the 170 pages is devoted to the high temperature, respectively “replica-symmetric” phase which is analyzed in great detail. This section explains how to use the cavity method to obtain conditions under which the Gibbs measures converge to (random) product measures, and to compute the parameters of these measures. The somewhat alternative approach of F. Guerra and F. L. Toninelli [Quadratic replica coupling in the Sherrington-Kirkpatrick mean field spin glass model. J. Math. Phys. 43, 3704–3716 (2002)], that uses Gaussian interpolation methods is also explained. The culmination of the section is Chapter 2.11, where the proof of Guerra, showing that the free energy computed using the Parisi replica symmetry breaking scheme is a rigorous upper bound for the true free energy of the model for all values of the temperature and the magnetic field.

The following three sections take us into the realm of neural network models. Section 3 deals with the capacity of the Ising perceptron. Basically, the problem here is as follows. Take a vector \(g\) made of \(N\) i.i.d. standard normal random variables, consider the half space made of vectors \(x\) such that \((x,g)\geq0\). Taking \(M\) such Gaussian vectors, one is interested in the volume of the intersection of all these half-spaces intersected with the hypercube \(\{-1,1\}^N\). This should behave like \(\exp(-\phi(M/N))\), if both \(M\) and \(N\) are large. This purely geometric problem can be cast into a problem on Gibbs measures by associating to each configuration \(\mathbf s\) a weight that increases whenever one more constraint is satisfied., and zero otherwise, i.e. defining \(H_N(\mathbf s)=\sum_{k=1}^M \mathbf 1_{(x,g_k)\geq 0}\). The computation of the partition function \(Z_{\beta,N}=\sum_{\mathbf s} \exp(H_N(\mathbf s))\), can then be seen as a “softened” version of the original counting problem. The problem can be further generalized by replacing the indicator function by a smooth approximation. The resulting problem is again susceptible to be treated with the replica method. The last part of the chapter is devoted to remove boundedness conditions on the function \(u\), using methods inspired from a paper by M. Shcherbina and B. Tirozzi [Rigorous solution of the Gardner problem. Commun. Math. Phys. 234, 383–422 (2003; Zbl 1034.82042)], used in the case of the analogous problem where the hypercube is replaced by the \(N\)-dimensional unit sphere, and that is the subject of Section 4.

Section 5 treats the Hopfield model. Basically we encounter the same type of methods as before, with the same types of results: a domain of parameters is established where the predictions of the heuristic methods predict replica symmetry, and it is shown that these predictions are correct (on a subset of this set). In this case, this is not limited to low temperatures. The main new feature here is the necessity to have a priori some control on the Gibbs measures that says that it concentrates on the number of disjoint small subsets of the configuration space. On each of these sets, the cavity method is then applicable. The decomposition of the Gibbs measure observed in the Hopfield model is a desired feature of the model and closely related to its purpose, namely to serve as a model of associative memory. In fact, the sets where the measure concentrates (at low temperatures) are neighborhoods of the “stored patterns”, a set of (random) spin configurations on which the Hamiltonian depends. In the model described in the following section, the \(p\)-spin SK model with \(p\) large, a similar lumping phenomenon occurs spontaneously. Here the model is again a Gaussian process on the hypercube, with covariance proportional to the \(p\)-th power of the scalar product (“overlap”) of the spin configurations. This section makes use of another amazing idea due to F. Guerra and S. Ghirlanda [General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity. J. Phys. A, Math. Gen. 31, 9149–9155 (1998; Zbl 0953.82037)], the so-called Ghirlanda-Guerra identities. These relations, that follow essentially from Gaussian integration by parts formulas, give some a priori structural information on the random geometrical structure of the Gibbs measures.

The two final sections deal with further applications of the methods to the dilute SK model, the \(K\)-sat (satisfiability) problem, and the random matching problem.

Each section of the book ends with some comments on the literature. One would have appreciated those to be more detailed and enlightening. The author has apparently put a great effort into rendering the exposition as clear as possible. In spite of these efforts, few will find the book easy to read, but for this the nature of the problems is to blame rather than the author.

The book will, certainly, find a favorite place on the desk of anyone working in the field.

From a purely mathematical point of view, the SK model can be described as a Gaussian process on the hypercube \(\{-1,1\}^N\). The theoretical physics community, through an ingenious intuition of Giorgio Parisi, has devised methods to compute fine properties of these systems, such as the value of \(\lim_{N\uparrow\infty} \max_{\mathbf s}N^{-1} H_N(\mathbf s)\), that were unaccessible to the conventional tools of mathematical analysis. That the method of Parisi [see M. Mézard, G. Parisi and M. A. Virasoro, Spin glass theory and beyond, Lect. Notes Phys. 9, Teaneck, NJ (1987; Zbl 0992.82500)] was from a mathematical point of view obscure, to say the least, was motivation enough for the author to set out a systematic analysis of the problem with rigorous mathematical tools. The book gives a comprehensive account of this endeavor by its author, as well as some selected works of other people in the same field.

The mathematics in this problem involved is not limited to the SK model, nor is it to Gaussian processes on the hypercube. In fact, it had been long noticed that a great number of other problems that are highly relevant in diverse application areas fall into the same category. These include, but are not limited to, models of neural networks, such as perceptron models and the Hopfield model, the \(K\)-SAT and other problems from computer science, which are all covered here.

The approach presented here orbits around the so-called cavity method. The cavity method essentially consists in the attempt to compute key quantities of interest (functionals of the random process at hand) by inductions over the number \(N\) (the volume). That is, given a function \(F_N\) of the process, one tries to derive a recursion relation for this function in the variable \(N\). Usually, in this attempt it turns out that no closed form can be achieved, and a number of new functions have to be introduced. The goal is to show that it is enough to introduce a finite set of such functions, while all further terms produced in the program can be treated as error terms. The limit of the function \(F_N\) can then be obtained as the solution of a fix-point equation. This basic idea was present in non-rigorous work of Parisi, Mézard and others, and the first attempt to exploit it for rigorous work was made by Pastur and Shcherbina in the early 1990’s, but Talagrand has turned this a powerful tool to prove that results obtained with the help of the replica method at least in the simpler situations where so-called “replica symmetry” holds. Unfortunately, the book appeared too early to include the last triumph of the method, the author’s announced proof of the correctness of the Parisi solution of the SK model in general, based on a brilliant and ingenious idea of F. Guerra [Broken replica symmetry bounds in the mean field spin glass model. Commun. Math. Phys. 233, 1–12 (2003; Zbl 1013.82023)] (the latter, fortunately, is explained in Section 2.11.).

The book is divided into 8 Chapters and an appendix. The first explains some basic ideas in the simple setting of the Random Energy model, i.e. in the context of independent random variables. This allows the reader to get acquainted to some of the simpler techniques in a context that is easy to grasp.

The second chapter is devoted to the standard Sherrington-Kirkpatrick model. The bulk of the 170 pages is devoted to the high temperature, respectively “replica-symmetric” phase which is analyzed in great detail. This section explains how to use the cavity method to obtain conditions under which the Gibbs measures converge to (random) product measures, and to compute the parameters of these measures. The somewhat alternative approach of F. Guerra and F. L. Toninelli [Quadratic replica coupling in the Sherrington-Kirkpatrick mean field spin glass model. J. Math. Phys. 43, 3704–3716 (2002)], that uses Gaussian interpolation methods is also explained. The culmination of the section is Chapter 2.11, where the proof of Guerra, showing that the free energy computed using the Parisi replica symmetry breaking scheme is a rigorous upper bound for the true free energy of the model for all values of the temperature and the magnetic field.

The following three sections take us into the realm of neural network models. Section 3 deals with the capacity of the Ising perceptron. Basically, the problem here is as follows. Take a vector \(g\) made of \(N\) i.i.d. standard normal random variables, consider the half space made of vectors \(x\) such that \((x,g)\geq0\). Taking \(M\) such Gaussian vectors, one is interested in the volume of the intersection of all these half-spaces intersected with the hypercube \(\{-1,1\}^N\). This should behave like \(\exp(-\phi(M/N))\), if both \(M\) and \(N\) are large. This purely geometric problem can be cast into a problem on Gibbs measures by associating to each configuration \(\mathbf s\) a weight that increases whenever one more constraint is satisfied., and zero otherwise, i.e. defining \(H_N(\mathbf s)=\sum_{k=1}^M \mathbf 1_{(x,g_k)\geq 0}\). The computation of the partition function \(Z_{\beta,N}=\sum_{\mathbf s} \exp(H_N(\mathbf s))\), can then be seen as a “softened” version of the original counting problem. The problem can be further generalized by replacing the indicator function by a smooth approximation. The resulting problem is again susceptible to be treated with the replica method. The last part of the chapter is devoted to remove boundedness conditions on the function \(u\), using methods inspired from a paper by M. Shcherbina and B. Tirozzi [Rigorous solution of the Gardner problem. Commun. Math. Phys. 234, 383–422 (2003; Zbl 1034.82042)], used in the case of the analogous problem where the hypercube is replaced by the \(N\)-dimensional unit sphere, and that is the subject of Section 4.

Section 5 treats the Hopfield model. Basically we encounter the same type of methods as before, with the same types of results: a domain of parameters is established where the predictions of the heuristic methods predict replica symmetry, and it is shown that these predictions are correct (on a subset of this set). In this case, this is not limited to low temperatures. The main new feature here is the necessity to have a priori some control on the Gibbs measures that says that it concentrates on the number of disjoint small subsets of the configuration space. On each of these sets, the cavity method is then applicable. The decomposition of the Gibbs measure observed in the Hopfield model is a desired feature of the model and closely related to its purpose, namely to serve as a model of associative memory. In fact, the sets where the measure concentrates (at low temperatures) are neighborhoods of the “stored patterns”, a set of (random) spin configurations on which the Hamiltonian depends. In the model described in the following section, the \(p\)-spin SK model with \(p\) large, a similar lumping phenomenon occurs spontaneously. Here the model is again a Gaussian process on the hypercube, with covariance proportional to the \(p\)-th power of the scalar product (“overlap”) of the spin configurations. This section makes use of another amazing idea due to F. Guerra and S. Ghirlanda [General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity. J. Phys. A, Math. Gen. 31, 9149–9155 (1998; Zbl 0953.82037)], the so-called Ghirlanda-Guerra identities. These relations, that follow essentially from Gaussian integration by parts formulas, give some a priori structural information on the random geometrical structure of the Gibbs measures.

The two final sections deal with further applications of the methods to the dilute SK model, the \(K\)-sat (satisfiability) problem, and the random matching problem.

Each section of the book ends with some comments on the literature. One would have appreciated those to be more detailed and enlightening. The author has apparently put a great effort into rendering the exposition as clear as possible. In spite of these efforts, few will find the book easy to read, but for this the nature of the problems is to blame rather than the author.

The book will, certainly, find a favorite place on the desk of anyone working in the field.

Reviewer: Anton Bovier (Berlin)

##### MSC:

82-02 | Research exposition (monographs, survey articles) pertaining to statistical mechanics |

82B44 | Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics |

82D30 | Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) |