Generalization of the cavity method for adiabatic evolution of Gibbs states

Mean-field glassy systems have a complicated energy landscape and an enormous number of different Gibbs states. In this paper, we introduce a generalization of the cavity method in order to describe the adiabatic evolution of these glassy Gibbs states as an external parameter, such as the temperature, is tuned. We give a general derivation of the method and describe in details the solution of the resulting equations for the fully connected $p$-spin model, the XOR-satisfiability (SAT) problem and the antiferromagnetic Potts glass (coloring problem). As direct results of the states following method we present a study of very slow Monte Carlo annealings, the demonstration of the presence of temperature chaos in these systems and the identification of an easy/hard transition for simulated annealing in constraint optimization problems. We also discuss the relation between our approach and the Franz-Parisi potential, as well as with the reconstruction problem on trees in computer science. A mapping between the states following method and the physics on the Nishimori line is also presented.

Figure 1

(Color online) A cartoon of the energy landscape in mean-field glassy systems. The different valleys correspond to different Gibbs states and are separated by extensive barriers. For energies lower than $e_d$ (the uppermost brown line), ergodicity breaks because of these barriers. The ground-state energy of the system is $e_{\text{GS}}$ (the lowermost green line). The standard cavity and replica method can compute how many states of a given size/entropy are present at a given energy/temperature $e/T$. The states following method we develop in this paper instead pins down one state (in red, marked by the point, in the figure) that is one of the equilibrium ones at energy $e_e$ (corresponding to temperature $T_e$, the blue line with a point) and computes its properties (entropy, energy) for another temperatures $T_a$: we are thus following a given state as temperature (or any other parameter) is changed. At $T_a=0$, this leads, for instance, to the properties of the bottom of the state as, e.g., the limiting energy $e_{\text{bottom}}$.

Figure 2

A sketch of the basic cavity recursion in the factor graph representation of XOR-SAT. The square represents a constraint involving the product of three spins while the circles represent the spin variables. The message passing procedure called belief propagation uses messages from constraints to variables $\left(\psi \right)$ and from variables to constraints $\left(\chi \right)$.

Figure 3

(Color online) (a) Recursive construction of an equilibrium configuration at temperature $T_e$ in XOR-SAT. Given the tree, and a random choice of interactions (full square $J=1$, empty square $J=-1$), one starts from the root, and chooses iteratively the configuration of the ancestors (full circles $s=1$, empty circle $s=-1$) randomly such that it satisfies the constraints with probability $1-ϵ\left(T_e\right)$, Eq. (15), here $ϵ=3/7$. Violated constraints have dashed/red borders. (b) The problem can also be gauge transformed using Eq. (29), see Sec. 3F, into a fully polarized configuration with all $s=1$ but where the $J$’s are chosen from distribution, Eq. (30).

Figure 4

(Color online) Adiabatic evolution of states in the fully connected three-spin model, where $T_d=0.6815$ and $T_K=0.6513$. The continuous (blue) curve that crosses the graph shows the equilibrium energy $e_e\left(T\right)$ of the model versus the temperature (with the Gardner transition toward full RSB phase at low temperature). We have applied the states following method and the red curves (five roughly parallel curves) mark the adiabatic evolution of states from equilibrium with $T_e=0.6815,0.675,0.67,0.66,0.6513$ for temperatures $T_a\ne T_e$. Left: this is the RS result where we follow states using the RS ansatz, Eqs. (40, 41, 43). Upon warming, the states exist until meeting a spinodal point at much larger temperature. Upon cooling the states can be followed until they become unstable against 1RSB (dashed), eventually a nonphysical spinodal point makes the RS solution vanish. Note that the RS solution for the equilibrium state at $T_e=T_d$ vanishes as soon as $T_a<T_e$ and is thus not even seen on this picture. Right: we follow states using the 1RSB ansatz (the dashed part of the red curves), Eqs. (44, 45, 46, 47, 48). The 1RSB solution is actually also unstable to further steps of RSB and (most probably) the full RSB should be used instead. The 1RSB is therefore a (good) lower bound to the correct result. Note also that the nonphysical spinodal points for low temperatures do not appear and that the 1RSB approach has mostly cured the problem with the exception of the states corresponding to $T_e\approx T_d$. The green dotted line is an example of a region where even the 1RSB equations do not have a physical solution. The green dotted line is a lower bound computed by the construction suggested in Sec. 5G2.

Figure 5

(Color online) A direct quantitative look at the shape of states in the energy landscape of the fully connected three-spin model. The energy of four different states is plotted as a function of their entropy; we plot $s/2$ and $-s/2$ such that the width corresponds to the entropy. The shapes of the curves show how the valleys look in the energy landscape. The outermost curve (blue) is the total equilibrium energy versus entropy. The four inside red curves correspond to different states that are at equilibrium at temperatures $T_e=0.6815,0.67,0.66,0.6513$, and their equilibrium energy $e_e$ are marked by horizontal (black) dotted lines. The highest bottom of these states marks a lower bound on the best possible limiting energy for a slow annealing.

Figure 6

(Color online) Explicit demonstration of the presence of temperature chaos below the Kauzmann temperature in the fully connected three-spin model. Left: the energy as a function of temperature for states below the Kauzmann transition: the four curves correspond to temperatures $T_e=0.4,0.5,0.6,0.6513$. Right: the crossing of free energies of different states as a function of temperature. The lower envelope (blue) is the equilibrium free energy: it results from the crossings of many states; here we show three such states that are the equilibrium ones at temperatures $T_e=0.4,0.55,0.65$. Inset: to make the crossing more evident, we plot the difference between the free energy of these three different states and the equilibrium free energy.

Figure 7

(Color online) The phase diagram of the fully connected three-spin model with a ferromagnetic bias (left), or equivalently, the phase diagram in function of the two temperatures $T_a$ and $T_e$ in the state following formalism. True phase transitions are marked by thick lines while spinodals and the Nishimori lines are drawn thin and dashed. The two phase diagrams are given to highlight how the physics of states following can be understood intuitively from the ferromagnetically biased model. Note that the line denoting the transition from spin glass to ferromagnet (computed at the 1RSB level) is almost but not completely straight.

Figure 8

(Color online) The replica symmetric free energy of a state at temperature $T_a$ as a function of the distance $m$ from an equilibrium configuration at $T_e$ in the three-spin fully connected model. The points indicate the minima corresponding to what the state following method finds. Left: in this case $T_a=T_e$; a minimum starts to form around the equilibrium configuration for $T_e<T_d=0.6815$ while in the liquid phase $T_e>T_d$ no such minimum exists. Right: we now use $T_a\ne T_e$ (here $T_e=0.67$) and we observe how the curves are evolving with $T_a$. Upon warming, the minimum happens at lower free energies and $m$ is decaying, indicating that the state gets larger until finally a spinodal point is reached and no more minimum exist; this is the moment where the state melts into the liquid. Upon cooling, we thus expect that both the free energy and $m$ increase. This is indeed the case but for low temperature (here $T_a=0.46$) we start to observe a nonmonotonous behavior for $m$. Worse, if the temperature is again lowered (here $T_a=0.4$) the minimum disappears. These are nonphysical features and are clear signs that replica symmetry must be broken for low temperatures.

Figure 9

(Color online) Left: comparison between the RS Franz-Parisi potential lower curve (red) and the 1RSB one upper curve (blue). The point marks the minima on the 1RSB curve. Right: magnetization of the minima as a function of temperature $T_a$. Again the lower (red) curve is the RS result, the upper (blue) curve is the 1RSB result. The increasing or nonexisting part of the curve in unphysical, the size of the unphysical region is much smaller in the 1RSB result.

Figure 10

(Color online) Representative behavior of states in diluted mean-field systems. Left: the XOR-SAT problem with $K=3$ and $c=3$. Right: the XOR-SAT problem with $K=3$ and $c=4$. The value of energy here is the number of violated constraints per variable. The blue line crossing the diagram is the equilibrium energy computed from the standard cavity method, Eqs. (16, 17, 18, 19, 20, 21). The vertical lines denote the dynamical and Kauzmann temperatures. The red lines depict adiabatic evolution of states that are the equilibrium one at the temperature $T_e$ where the red curve crosses the blue one. The state evolution curves are obtained by solving Eqs. (24, 25, 26) when $T_e\ge T_K$ and Eqs. (32, 33, 34, 35, 36, 37) when $T_e<T_K$ (in the inset of the right-hand side). The dashed part of the red curves depicts the region of temperatures where the state is no longer stable toward replica symmetry breaking and splits into many substates. The ends of the red curves at nonzero temperature correspond to the nonphysical spinodal points beyond which Eqs. (24, 25, 26) have only the trivial liquid solution.

Figure 11

(Color online) Following states in the XOR-SAT problem with $c=3$ and $K=3$ with Monte Carlo simulations. On this picture, we have reproduced the data of Fig. 10 with Monte Carlo simulation (black and green crosses). We have prepared a large XOR-SAT system at equilibrium for $T=0.25$ and $T=0.22$ and performed slow cooling and heating with a Monte Carlo procedure: when the dynamics is slow enough (we have changed the temperature only by a factor $\Delta T={10}^{-8}$ at each Monte Carlo step) the energy in the simulation follows perfectly the predictions of the states following formalism. We have thus succeeded in predicting the adiabatic evolution of the dynamics starting from equilibrium.

Figure 12

(Color online) State following for the four-coloring of nine-regular random graphs. Equilibrium in blue, several states in red. Unlike in the XOR-SAT problem, here the states descent very fast to zero energies. Asterisk (green) represent the results of adiabatic simulations starting from an equilibrated configuration on a $N={10}^5$ graph and then using the BP equations initialized in the equilibrated configuration for different temperatures: the energy follows again the prediction of the states following formalism.

Figure 13

(Color online) Data from Figs. 10, 12 plotted in order to visualize the energy landscape. The energy $e$ is plotted against the entropy $s={\beta }_a\left(e-f\right)$ for different equilibrium states. We plotted $s\left(e\right)/2$ and $-s\left(e\right)/2$ such that the width corresponds to the logarithm of the number of configurations at energy $e$ for the Gibbs state. Left: XOR-SAT with $c=3$ and $K=3$. Right: four coloring of random graphs with $c=9$. The black curve corresponds to the equilibrium total entropy. The red curves are different equilibrium states, corresponding to $T_e=0.15,0.2,0.24$ (left) and $T_e=0.12$ (right), the energies corresponding to $T_e$ are depicted by horizontal black dashed lines. The left-side states, with their finite-energy bottoms, remind us of the valleys in Fig. 1 while the right side reminds of deep canyons that all reach the ground-state energy level. Note that our distinction between canyons and valleys is purely energetic, both canyons and valleys can have both zero or positive bottom entropy.

Figure 14

(Color online) Comparison between the exact adiabatic evolution of states and the isocomplexity lower bound. The black line is the energy of the bottoms of states that were the equilibrium ones at temperature $T_K\le T_e\le T_d$ in XOR-SAT for $c=3$ and $K=3$ (left, the inset is a zoom) and for $c=4$ and $K=3$ (right). The red (uppermost) line is the equilibrium energy at $T_e$. The blue line is the isocomplexity lower bound from Ref. 5.

Figure 15

(Color online) Iteration of belief propagation in the four-coloring problem of graph with average Poissonian degree $c=8.4$. The average magnetization of BP messages is plotted versus the number of iterations. When initialized in the equilibrium solution (obtained by planting), BP converge to the nontrivial magnetization, in agreement with the cavity prediction. On the very same graph, when initialized in a solution obtain by Walk-Col, it, however, converges to the trivial fixed point. This shows solutions found by heuristic solver are very different from the equilibrium ones, and instead belong to clusters that do not have an associated BP fixed point, as expected from the picture obtained by the following state method.