Spin Glass Theory and Beyond

The following sections are included:

• PREFACE

• CONTENTS

Often in life we find out that our goals are mutually incompatible: we have to renounce some of them and we feel frustrated. For example, I may want to be a friend of both Mr. White and Mr. Smith. Unfortunately, they hate each other: it is then rather difficult to be a good friend of both of them (a very frustrating situation)…

The following sections are included:

• Quenched Averages and Replicas

• Replica Symmetric Solution of the SK Model

• Stability

• References

The following sections are included:

• Mean Field Solution for a Given Sample

• About the Number of Solutions of the TAP Equations

• Local Field Distribution

• Stability and the Solutions of the TAP Equations

• References

The following sections are included:

• Pure States

• Distribution of the Distance between the Pure States: the Order Parameter is a Function

• Computation of P(q) with Replicas: Existence of Many States and the Breaking of the Replica Symmetry

• A First Stage of Replica Symmetry Breaking

• Replica Symmetry Breaking: the Final Formulation

• How to Compute P(q)

• References

The following sections are included:

• The Discovery of Ultrametricity

• The Fluctuations of P_j(q) with J_ij

• The Foliation of the Tree

• The Energies and Free Energies as Independent Random Variables
  • The SK model
  • Two instructive models: the REM and the GREM

• Self Averageness and Reproducibility

• A Branching Diffusion Process as a Generator of Ultrametricity

• References

The following sections are included:

• Introduction

• The Stability of the Thermodynamical Limit
  • Inside a state—A new derivation of the TAP equations
  • Inside a cluster—Self-consistency of ultrametricity and the exponential distribution of the states

• Fluctuations around the Mean Field

• References

The following sections are included:

• Introduction

• Dynamics on Finite Time Scales

• Dynamics on Infinite Time Scales and Statics

• References

A new theory of the class of dilute magnetic alloys, Called the spin glasses, is proposed which offers a simple explanation of the cusp found experimentally in the susceptibility. The argument is that because the interaction between the spins dissolved in the matrix oscillates in sign according to distance, there will be no mean ferro or antiferromagnetism, but there will be a ground state with the spins aligned in definite directions, even if these directions appear to be at random. At the critical temperature, the existence of these preferred directions affects the orientation of the spins, leading to a cusp in the susceptibility. This cusp is smoothed by an external field. If the potential between spins on sites i, j is J_ijS_i · S_j then it is shown that

An analysis of disorder is given, based on the concept of local invariance. The frustration effect is defined and several fundamental concepts are introduced. Spin glasses are considered here as representative of a new vast class of condensed matter phases …

We consider an Ising model in which the spins are coupled by Infinite-ranged random interactions independently distributed with a Gaussian probability density. Both “spin-glass” and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied …

A class of infinite-ranged random model Hamiltonians is defined as a limiting case in which the appropriate form of mean-field theory, order parameters and phase diagram to describe spin-glasses may be established. It is believed that these Hamiltonians may be exactly soluble, although a complete solution is not yet available. Thermodynamic properties of the model for Ising and XY spins are evaluated using a “many-replica” procedure. Results of the replica theory reproduce properties at and above the ordering temperature which are also predicted by high-temperature expansions, but are in error at low temperatures. Extensive computer simulations of infinite-ranged Ising spin-glasses are presented. They confirm the general details of the predicted phase diagram. The errors in the replica solution are found to be small, and confined to low temperatures. For this model, the extended mean-field theory of Thouless, Anderson, and Palmer gives physically sensible low-temperature predictions. These are in quantitative agreement with the Monte Carlo statics. The dynamics of the infinite-ranged Ising spin-glass are studied in a linearized mean-field theory. Critical slowing down is predicted and found, with correlations decaying as e^{−I(T−T_c)/TI2} for T greater than T_c, the spin-glass transition temperature. At and below T_c spin-spin correlations are observed to decay to their long-time limit as I^−t/2.

The stationary point used by Sherrington and Kirkpatrick in their evaluation of the free energy of a spin glass by the method of steepest descent is examined carefully. It is found that, although this point is a maximum of the integrand at high temperatures, it is not a maximum in the spin glass phase nor in the ferromagnetic phase at low temperatures. The instability persists in the presence of a magnetic field. Results are given for the limit of stability both for a partly ferromagnetic interaction in the absence of an external field and for a purely random interaction in the presence of a field.

The Sherrington-Kirkpatrick model of a spin glass is solved by a mean field technique which is probably exact in the limit of infinite range interactions. At and above T_c the solution is identical to that obtained by Sherrington and Kirkpatrick (1975) using the n→0 replica method, but below T_c the new result exhibits several differences and remains physical down to T = 0.

The number of solutions of the equations of Thouless, Anderson and Palmer is obtained as a function of temperature. The density of solutions with a given free energy is calculated for free energies greater than a (temperature-dependent) critical value …

We find an approximate solution of the Sherrington–Kirkpatrick model for spin glasses; the internal energy and the specific heat are in very good agreement with the computer simulations, the zero temperature entropy is unfortunately negative, although it is very small …

In the framework of the new version of the replica theory, we compute a sequence of approximated solutions to the Sherrington–Kirkpatrick model of spin glasses …

We study the breaking of the replica symmetry in spin glasses. We find that the order parameter is a function on the interval 0–1. This approach is used to study the Sherrington–Kirkpatrick model. Exact results are obtained near the critical temperature. Approximated results at all the temperatures are in excellent agreement with the computer simulations at zero external magnetic field …

We study the magnetic properties of spin glasses in a recently proposed mean field theory; in this approach the replica symmetry is broken and the order parameter is a function (q(x)) on the interval 0–1. Exact results at the critical temperature and approximated results at all the temperatures are derived. The comparison with the computer simulations is briefly presented.

The size dependence of slow relaxation processes in the infinite-range Ising spin-glass is investigated by computer simulation. Below the transition temperature, relaxation of variables which do not change sign under inversion of the spins is complete by a time ρ, where lnρ^∝N^¼ and so diverges as N, the number of spins, tends to infinity. The “ergodic time” τ_eg satisfies lnρ_eg^∝N½. These results are consistent with a physical picture where barriers between free-energy minima in phase space have a height proportional to the square root of the number of spins to be flipped.

We study, near T_c, the stability of Parisi's solution for the long-range spin-glass. In addition to the discrete, “longitudinal” spectrum found by Thouless, de Almeida, and Kosterlitz, we find “transverse” bands depending on one or two continuous parameters, and a host of zero modes occupying most of the parameter space. All eigenvalues are non-negative, proving that Parisi's solution is marginally stable.

An order parameter for spin-glasses is defined in a clear physical way: It is a function on the interval 0–1 and it is related to the probability distribution of the overlap of the magnetization in different states of the system. It is shown to coincide with the order parameter introduced by use of the broken replica-symmetry approach …

The recent interpretation of Parisi's order-parameter function q(x) in terms of a probability distribution for the overlap between magnetizations in different phases is investigated by Monte Carlo computer simulation for the infinite-range Ising spin-glass model. The main features of the solution for q(x) are reproduced, in particular q(x)∞ x as x→0 and q′(x) = 0 at q=q_max, the largest value. Finite-size effects prevent one from establishing with certainty whether there is a “plateau,” i.e., q′(x) = 0 for a range of x.

A probability distribution has been proposed recently by one of us as an order parameter for spin glasses. We show that this probability depends on the particular realization of the couplings even in the thermodynamic limit, and we study its distribution. We also show that the space of states has an ultrametric topology …

The hierarchical organization of the pure states of a S.K. spin glass (ultrametricity) is analysed in terms of self-averaging distributions of local magnetizations. We show that every pure state α defines an ultrametric distance Dα(i,j) among the N sites. Given two states α, β with overlap q there is a minimum distance d_m such that for two sites i, j with Dα(i, j) ≥ d_m the two distances Dα and Dβ coincide. It follows that the sites can be partitioned in disjoint cells inside which the total magnetization is the same for all the states with mutual overlap q. For this same family of states we then define an “ancestor” that has, inside each cell, constant local magnetization equal to the average magnetization of the descendants. The ancestors satisfy mean field like equations. The functional dependence of the local magnetization in terms of the local field is given by the solution of the diffusion equation in x space which is given a purely static interpretation.

The free energies of the pure states in the spin glass phase are studied in the mean field theory. They are shown to be independent random variables with an exponential distribution. Physical implications concerning the fluctuations from sample to sample are worked out. The physical nature of the mean field theory is fully characterized …

We introduce a new method, which does not use replicas, from which we recover all the results of the replica symmetry-breaking solution of the Sherrington-Kirkpatrick model …

A simple model of disordered systems–the random-energy model–is introduced and solved. This model is the limit of a family of disordered models, when the correlations between the energy levels become negligible. The model exhibits a phase transition and the low-temperature phase is completely frozen. The corrections to the thermodynamic limit are discussed in detail. The magnetic properties are studied, and a constant susceptibility is found at low temperature. The phase diagram in the presence of ferromagnetic pair interactions is described. Many results are qualitatively the same as those of the Sherrington-Kirkpatrick model. The problem of using the replica method is analyzed. Lastly, this random-energy model provides lower bounds for the ground-state energy of a large class of spin-glass models.

We study a system of Ising spins with quenched random infinite ranged p-spin interactions. For p→∞, we can solve this model exactly either by a direct microcanonical argument, or through the introduction of replicas and Parisi's ultrametric ansatz for replica symmetry breaking, or by means of TAP mean field equations. Although the model is extremely simple it retains the characteristic features of a spin glass. We use it to confirm the methods that have been applied in more complicated situations and to explicitly exhibit the structure of the spin glass phase.

Langevin equations for the relaxation of spin fluctuations in a soft-spin version of the Edwards-Anderson model are used as a starting point for the study of the dynamic and static properties of spin-glasses. An exact uniform Lagrangian for the average dynamic correlation and response functions is derived for arbitrary range of random exchange, using a functional-integral method proposed by De Dominicis. The properties of the Lagrangian are studied in the mean-field limit which is realized by considering an infinite-ranged random exchange. In this limit, the dynamics are represented by a stochastic equation of motion of a single spin with self-consistent (bare) propagator and Gaussian noise. The low-frequency and the static properties of this equation are studied both above and below T_c. Approaching T_c from above, spin fluctuations slow down with a relaxation time proportional to |T–T_c|⁻¹ whereas at T_c the damping function vanishes as ω^½. We derive a criterion for dynamic stability below T_c. It is shown that a stable solution necessarily violates the fluctuation-dissipation theorem below T_c. Consequently, the spin-glass order parameters are the time-persistent terms which appear in both the spin correlations and the local response. This is shown to invalidate the treatment of the spin-glass order parameters as purely static quantities. Instead, one has to specify the manner in which they relax in a finite system, along time scales which diverge in the thermodynamic limit. We show that the finite-time correlations decay algebraically with time as t^−v at all temperatures below T_c, with a temperature-dependent exponent v. Near T_c, v is given (in the Ising case) as v(T)˜ ½ − π⁻¹(1 − T/T_c) + σ(1 − T/T_c)². A tentative calculation of v at T= 0 K is presented. We briefly discuss the physical origin of the violation of the fluctuation-dissipation theorem.

We discuss the dynamics of the infinite-range Sherrington-Kirkpatrick spin-glass model for which relaxation times diverge when N, the number of spins, tends to infinity. Calculations on a large but finite system are very difficult, so we mimic a large finite system in equilibrium by working with N = ∞ and imposing, by hand, a canonical distribution at an initial time. For short times, where no barrier hopping has occurred, we find that the Edwards-Anderson order parameter, q_EA, is identical to that obtained from an analysis of the mean-field equations of Thouless, Anderson, and Palmer and, with further assumptions, gives q(x = 1) in Parisi's theory, in agreement with earlier work. For times longer than the longest relaxation time (of the finite system), true equilibrium is reached and our theory agrees with previous statistical-mechanics calculations using the replica trick. There is no violation of the fluctuation-dissipation theorem.

Zero-temperature computer simulations are reported for the Sherrington-Kirkpatrick random Ising model of a spin glass, including an external field. Results are presented for the internal field distribution P(H), and for the ground state energy and magnetisation as functions of field. P(H) has a linear rise from H = 0 for all external fields. The zero-temperature susceptibility χ(0) is close to unity when equilibrium states are examined, in agreement with Parisi's replica symmetry breaking theory and in conflict with linear response theory. The linear response result χ(0) = 0 can be obtained by searching for metastable local energy minima close to the zero-field ground state in configuration space.

The following sections are included:

• Introduction

• Combinatorial Optimization Problems

• Optimization and Statistical Mechanics at Zero Temperature

• References

The Monte Carlo method¹ uses the power of computers to simulate the behaviour of a physical system at thermal equilibrium. It generates configurations of the system with a probability given by Gibbs' law

The following sections are included:

• General Thermodynamical Properties and Scalings

• The Matching Problem

• The Travelling Salesman Problem

• The Assignment Problem and its Relations with the Matching and TSP

• Graph Partitioning

• Some Remarks

• References

The following sections are included:

• Combinatorial Optimization

• Statistical Mechanics

• Physical Design of Computers

• Placement

• Wiring

• Traveling Salesmen

• Summary and Conclusions

• References and Notes

We use the replica method to study the (bipartite) weighted matching problem with independent random distances between the points. We propose a replica symmetric solution which fits the numerical values of the minimal length and the distribution of lengths of the occupied links in the optimal configuration.

Recently developed techniques of the statistical mechanics of random systems are applied to the graph partitioning problem. The averaged cost function is calculated and agrees well with numerical results. The problem bears close resemblance to that of spin glasses. We find a spin glass transition in the system, and the low temperature phase space has an ultrametric structure. This sheds light on the nature of hard computation problems …

We propose and analyse a replica symmetric solution for random link travelling salesman problems. This gives reasonable analytical estimates for thermodynamic quantities such as the length of the shortest path.

It is far from evident that the type of organization present in biosystems should in any way resemble those encountered in physics. Organic matter surely obeys basic physical laws but still, the collective behaviour of large aggregations in typical physical systems could be irrelevant for the understanding of the corresponding behaviour in a biosystem…

In the study of the origin of life one can distinguish a moment in which, in the primordial ocean, an abundant supply of amino acids and nucleotides already exists while no microorganism subject to natural evolution has yet appeared…

The goal is to build a model of the brain where the pecularities of its performance emerge naturally. A realistic model is unfortunately out of question (and perhaps useless given its potential complexity). Therefore one is led to try to abstract which are the important features responsible for its idiosyncratic behavior…

The following sections are included:

• The Assembly of Neurons as a Spin Glass

• The Hebb Rule. Different Proposals

• The Analytical Solution of Hopfield's Model
  • The replica method
  • The cavity method
  • Fluctuations around the mean field

• References to Chapters X-XIII

Computational properties of use to biological organisms or to the construction of computers can emerge as collective properties of systems having a large number of simple equivalent components (or neurons). The physical meaning of content-addressable memory is described by an appropriate phase space flow of the state of a system. A model of such a system is given, based on aspects of neurobiology but readily adapted to integrated circuits. The collective properties of this model produce a content-addressable memory which correctly yields an entire memory from any subpart of sufficient size. The algorithm for the time evolution of the state of the system is based on asynchronous parallel processing. Additional emergent collective properties include some capacity for generalization, familiarity recognition, categorization, error correction, and time sequence retention. The collective properties are only weakly sensitive to details of the modeling or the failure of individual devices.

Two dynamical models, proposed by Hopfield and Little to account for the collective behavior of neural networks, are analyzed. The long-time behavior of these models is governed by the statistical mechanics of infinite-range Ising spin-glass Hamiltonians. Certain configurations of the spin system, chosen at random, which serve as memories, are stored in the quenched random couplings. The present analysis is restricted to the case of a finite number p of memorized spin configurations, in the thermodynamic limit. We show that the long-time behavior of the two models is identical, for all temperatures below a transition temperature T_c. The structure of the stable and metastable states is displayed. Below T_c, these systems have 2p ground states of the Mattis type: Each one of them is fully correlated with one of the stored patterns. Below T˜0.46T_c, additional dynamically stable states appear. These metastable states correspond to specific mixings of the embedded patterns. The thermodynamic and dynamic properties of the system in the cases of more general distributions of random memories are discussed.

The Hopfield model for a neural network is studied in the limit when the number p of stored patterns increases with the size N of the network, as p = αN. It is shown that, despite its spin-glass features, the model exhibits associative memory for α < α_c, α_c ≳ 0.14. This is a result of the existence at low temperature of 2p dynamically stable degenerate states, each of which is almost fully correlated with one of the patterns. These states become ground states at α < 0.05. The phase diagram of this rich spin-glass is described.

A model of learning by selection is described at the level of neuronal networks. It is formally related to statistical mechanics with the aim to describe memory storage during development and in the adult. Networks with symmetric interactions have been shown to function as content-addressable memories, but the present approach differs from previous instructive models. Four biologically relevant aspects are treated—initial state before learning, synaptic sign changes, hierarchical categorization of stored patterns, and synaptic learning rule. Several of the hypotheses are tested numerically. Starting from the limit case of random connections (spin glass), selection is viewed as pruning of a complex tree of states generated with maximal parsimony of genetic information.

In the original formulation of Hopfield's memory model, the learning rule setting the interaction strengths is best suited for orthogonal words. From the point of view of categorization, this feature is not convenient unless we reinterpret these words as primordial categories. But then one has to complete the model so as to be able to store a full hierarchical tree of categories embodying subcategories and so on. We use recent results on the spin glass mean field theories to show that this completion can be done in a natural way with a minimal modification of Hebb's rule for learning Categorization emerges naturally from an encoding stage structured in layers.

In this letter we study the influence of a strong asymmetry of the synaptic strengths on the behaviour of a neural network which works as an associative memory. We find that the asymmetry in the synaptic strengths may be crucial for the process of learning …

We consider a family of models, which generalizes the Hopfield model of neural networks, and can be solved likewise. This family contains palimpsestic schemes, which give memories that behave in a similar way as a working (short-term) memory. The replica method leads to a simple formalism that allows for a detailed comparison between various schemes, and the study of various effects, such as repetitive learning.

The following sections are included:

• REFERENCES