Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality

Yatin Dandi, David Gamarnik, Lenka ZdeborováarXiv 2023 · DOI · arXiv

Abstract: We consider $h$-stable local optima of Ising spin glass models, defined as spin configurations such that for nearly all of the spins, flipping their values results in increasing energy by at least a given amount $h$. For spin glasses as well as sparse and dense random graphs, while restricting to bisections, we prove the existence of a phase transition for the normalized energy level $h$ around a universal value $h^*$. For $h$ below the phase transition value $h^*$, bisections exist where the number of spins (nodes) which are not $h$-stable is sublinear. Above the phase transition level $h^*$ the smallest number of spins that are not $h$-stable is linear. This confirms a conjecture from Behrens et al. (2022). Our results also allow the characterization of possible energy values of stable local optima for varying $h$. In particular, for $h=0$, this rigorously proves seminal results in statistical physics regarding metastable states. Our proofs are obtained by analyzing the model on sparse random graphs and adopting Lindeberg's type universality method to lift the results from sparse to dense graphs and spin systems.

Introduction

Complex systems, ranging from protein folding to social network dynamics, are often characterized by "rugged landscapes"—mathematical spaces where configurations vary in stability and energy. A fundamental question in statistical physics and computer science is determining the maximum possible stability of local optima within these landscapes. This paper investigates $h$-stable local optima in Ising spin glass models and $h$-friendly partitions in random graphs. A configuration is $h$-stable if flipping almost any single component increases the system's energy by at least a margin $h$.

The Universal Stability Threshold

The researchers identify a universal phase transition for the stability level $h$ around a critical value $h^* \approx 0.3513$. This threshold is remarkably robust, appearing across sparse random graphs, dense Erdős-Rényi graphs, and the Sherrington-Kirkpatrick (SK) spin glass model.

The phase transition of h-stability: below $h^*$, almost all vertices can be stable; above it, a linear fraction must be unstable.

As shown in Figure 1, for any threshold $h < h^*$, there exist configurations where the number of non-$h$-stable vertices is sublinear ($o(n)$), meaning nearly every vertex satisfies the stability condition. Conversely, once $h$ exceeds $h^*$, the minimum number of unstable vertices grows linearly with the system size ($\Theta(n)$). This sharp transition confirms a recent conjecture and provides a precise limit on the "depth" of local optima in random landscapes.

Stability is intrinsically linked to the energy level of a configuration. The study characterizes the range of energy values $E$ for which $h$-stable states can exist. For a fixed stability requirement $h$ below the critical threshold, there is a specific "energy band" $[E_{min}(h), E_{max}(h)]$ within which configurations can achieve maximal stability.

Maximum proportion of h-stable vertices as a function of energy for $h_{cor} < h < h^*$. High stability is achievable within a specific energy range.

Figure 2 illustrates this relationship for a range of $h$ values. When the energy $E$ falls within the plateau, almost all vertices can be $h$-stable. Outside this range, the proportion of stable vertices drops significantly. This rigorous characterization for $h=0$ confirms long-standing predictions in statistical physics regarding the energy of "metastable states" in spin glasses, originally proposed by Bray and Moore in 1981.

Methodological Innovations

To prove these results across diverse models, the authors employ a sophisticated "lift-and-shift" strategy. They first analyze sparse random graphs, which are locally tree-like and amenable to the "second moment method." To extend these findings to dense graphs and Gaussian spin glasses, they utilize Lindeberg's universality method—a technique inspired by the Central Limit Theorem. This allows them to show that the macroscopic behavior of these systems depends only on the first few moments of the underlying distributions, establishing the universality of the $h^*$ threshold.

Implications and Future Work

The existence of such maximally stable states has profound implications for computational complexity. These states often exhibit the "Overlap Gap Property," suggesting that any two such configurations are either nearly identical or vastly different. This structural property is typically associated with algorithmic hardness, implying that while these "deepest grooves" exist, finding them efficiently may be impossible for standard algorithms.

Future research may explore whether every single node can be made $h$-stable (rather than just $n-o(n)$) and extend these findings to more complex $p$-spin models involving multi-node interactions.

Reference: Dandi, Y., Gamarnik, D., & Zdeborová, L. (2023). Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality. arXiv:2305.03591v2.

Summary updated

Abstract

We consider $h$-stable local optima of Ising spin glass models, defined as spin configurations such that for nearly all of the spins, flipping their values results in increasing energy by at least a given amount $h$. Spins satisfying this condition are referred to as $h$-stable spins for that configuration. Similarly, we consider a very related notion of $h$-friendly partitions of a graph. These are defined as bi-partitionings such that for most nodes, the normalized number of neighbors within the node's partition exceed the normalized number of neighbors outside the partition by a certain amount $h$. For spin glasses as well as sparse and dense random graphs, while restricting to bisections, we prove the existence of a phase transition for the normalized energy level $h$ around a universal value $h^*$. For $h$ below the phase transition value $h^*$, bisections exist where the number of spins (nodes) which are not $h$-stable (not $h$-friendly) is sublinear. Above the phase transition level $h^*$ the smallest number of spins that are not $h$-stable (not $h$-friendly) is linear. This confirms a conjecture from Behrens et al. (2022). Our results also allow the characterization of possible energy values of stable local optima for varying $h$. In particular, for $h=0$, this rigorously proves seminal results in statistical physics regarding the so-called metastable states, such as in the work of Bray and Moore (1981). Our results extend a recent proof of the so-called Friendly Partition Conjecture in Ferber et al. (2022) from the case $h=0$ to the case when $h$ takes general values. Our proofs are obtained by analyzing the model on sparse random graphs and adopting Lindeberg's type universality method to lift the results from sparse to dense graphs and spin systems.
BibTeX
@misc{dandi2023maximally,
  author = {Yatin Dandi and David Gamarnik and Lenka Zdeborová},
  title = {{Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality}},
  year = {2023},
  eprint = {2305.03591},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.03591},
}
Figure