🔢 mathematics

Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $\beta < 1$

This paper presents a polynomial-time algorithm that samples from the Gibbs measure of the Sherrington-Kirkpatrick model with vanishing error for any inverse temperature $\beta < 1$ by combining algorithmic stochastic localization with Jarzynski's equality, leveraging local regularity properties of the TAP free energy to extend previous results that were limited to $\beta < 1/2$ .

Original authors: Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

Published 2026-09-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of statistical physics, there exists a class of problems known as spin glasses, which model complex systems where individual components interact in conflicting ways. Imagine a collection of tiny magnets, each trying to align with its neighbors, yet pulled in opposite directions by different forces. This tug-of-war creates a rugged landscape of possibilities, where finding the most stable arrangement is notoriously difficult. For decades, scientists have studied a specific, idealized version of this problem called the Sherrington-Kirkpatrick model. It serves as a testing ground for understanding how complex systems behave, particularly when they are heated up. At high temperatures, the system is chaotic and easy to predict; at low temperatures, it becomes frozen into a complex, glassy state that is incredibly hard to navigate. A critical question has long lingered: at what point does the difficulty of sampling from this system become so great that no efficient computer algorithm can solve it?

For a long time, the boundary between the easy and the hard was believed to be a specific threshold. Below this threshold, the system behaves in a way that allows computers to quickly generate random samples that accurately reflect the system's natural state. Above it, the system is thought to fracture into so many competing possibilities that any computer trying to find its way through would get stuck, taking an impossibly long time. This threshold is defined by a value known as the inverse temperature. When this value is low, the system is hot and fluid; as it rises, the system cools and solidifies. Previous work had successfully built algorithms to sample from the system when it was relatively hot, but the region just below the critical freezing point remained a stubborn obstacle. The challenge was that the mathematical landscape in this region is not smooth and predictable; it is riddled with local traps that can fool standard algorithms into thinking they have found the best solution when they have not.

A team of researchers has now pushed the boundary of what is computationally possible, creating a new algorithm that can efficiently sample from this difficult system at any temperature below that critical freezing point. Their work demonstrates that even in the complex, glassy regime just before the system freezes, it is still possible to navigate the landscape of possibilities quickly and accurately. The key to their success was a shift in strategy. Instead of trying to enforce a rule that the entire mathematical landscape must be smooth and predictable everywhere, they realized they only needed to ensure smoothness in the specific regions where the system is actually likely to travel. By focusing their efforts on these "safe" zones, they could bypass the confusing, jagged areas that do not matter for the final result.

The researchers achieved this by combining two powerful techniques. The first involves a process of gradually adding a guiding force to the system, slowly steering it from a state of total chaos toward a specific, desired configuration. This is akin to gently nudging a wandering traveler toward a destination, rather than trying to map the entire terrain at once. The second technique is a method of correcting the path as it is traveled, using a mathematical tool that allows the algorithm to account for the distortions introduced by the guiding force. By carefully monitoring the system's movement and only accepting paths that stay within the safe, predictable zones, the algorithm avoids the traps that would otherwise cause it to fail. If a path ventures into a dangerous, unpredictable area, the algorithm simply discards it and tries again, ensuring that the final collection of samples is perfectly accurate.

This approach required a deep understanding of the system's underlying geometry. The researchers proved that while the entire landscape of possibilities is indeed complex and full of traps, the specific paths the system takes when guided by their method remain within a region that is locally smooth and well-behaved. They showed that within this region, the system's behavior is stable and predictable, allowing the algorithm to move forward with confidence. This discovery is significant because it confirms that the computational hardness of the problem is believed to begin only when the system actually freezes. Below that point, even in the most complex and glassy conditions, the system remains accessible to efficient computation. The work provides a rigorous step towards fully resolving the conjecture that the transition to computational difficulty happens exactly at the physical phase transition, addressing a long-standing question about the limits of what computers can achieve in statistical physics.

The implications of this finding extend beyond the specific model studied. The techniques developed by the researchers offer a new way of thinking about how to solve complex optimization and sampling problems. By relaxing the requirement for global smoothness and focusing instead on local stability along likely paths, they have opened a door to solving problems that were previously thought to be intractable. This method could potentially be applied to other complex systems where the landscape of possibilities is rough and full of local traps, provided that the system's natural behavior keeps it within a manageable region. The work stands as a testament to the power of combining physical intuition with rigorous mathematical analysis, showing that even in the most chaotic environments, there are patterns that can be harnessed to find order.

In the end, the paper does not just offer a new algorithm; it offers a new perspective on the nature of computational difficulty. It suggests that the barrier to solving these problems is not an inherent property of the system's complexity, but rather a limitation of the tools used to explore it. By refining those tools to match the system's actual behavior, the researchers have shown that the boundary between the easy and the hard is sharper and more precise than previously thought. For anyone interested in the limits of computation and the behavior of complex systems, this work provides a clear and concrete answer: as long as the system is not frozen, there is a way through.

Technical Summary: Potential Hessian Ascent IV: Sampling the Sherrington–Kirkpatrick Model at $\beta < 1$

Problem Statement
The paper addresses the computational problem of sampling from the Gibbs measure of the Sherrington–Kirkpatrick (SK) spin glass model. The model is defined on a system of size $n$ with a random symmetric matrix $A \sim \text{GOE}(n)$ and inverse temperature $\beta$ . The goal is to design a polynomial-time algorithm that produces a sample from the Gibbs distribution $\mu_{\beta A}$ with total variation distance (TVD) error vanishing as $n \to \infty$ (i.e., $o_n(1)$ ).

Previous work by the authors [DLSS26a] achieved this for $\beta < 1/2$ . However, for $\beta > 1/2$ (specifically in the range $0.798 < \beta < 1$ ), the TAP (Thouless-Anderson-Palmer) free energy is known not to be globally strongly convex. This lack of global convexity breaks the regularity assumptions required by previous algorithmic stochastic localization (ASL) analyses, which relied on global Lipschitz and smoothness properties of the TAP Hessian inverse (the resolvent). The regime $\beta < 1$ is believed to be the threshold for computational hardness, as the system exhibits full replica-symmetry breaking (fRSB) for $\beta > 1$ .

Methodology
The authors extend their previous ASL framework by replacing global regularity requirements with local regularity around likely trajectories of the stochastic process. The core methodology involves:

Algorithmic Stochastic Localization (ASL) with Rejection Sampling: The algorithm follows the ASL process $dy_t = m_t dt + dB_t$ but utilizes the TAP free energy to approximate the magnetization $m_t$ . Crucially, the algorithm includes a rejection step: if the trajectory leaves a "safe set" $S_{\beta, A}(c)$ where the TAP Hessian is locally strongly convex, the trajectory is discarded and restarted.
Jarzynski's Equality (JE) with Survival: To correct for the bias introduced by the rejection sampling (stopping the process upon exiting the safe set), the authors derive a modified Jarzynski's equality. This allows for the reweighting of surviving paths to approximate the target distribution.
Local Strong Convexity via Celentano's Result: The existence of the safe set is established using a result by Celentano [Cel24], which proves that the TAP free energy is locally strongly convex in small balls around Approximate Message Passing (AMP) iterates for $\beta < 1$ . The authors combine this with the stability of the SK model under stochastic localization (from [AMS22]) to show that the ASL trajectory remains within these locally convex regions with high probability.
Resolvent Analysis and Regularization: To handle the non-convexity of the safe set and the potential singularity of the TAP Hessian outside this set, the authors introduce a $C^2$ regularization of the resolvent (the inverse of the TAP Hessian). They utilize free probability techniques and block-matrix representations (inspired by [BBv23]) to control the diagonal entries of the squared resolvent and establish uniform concentration bounds.
Lipschitz Extensions: Since the safe set is not convex, standard derivative bounds along straight lines do not apply. The authors construct short paths within the safe set and use the resolvent identity to derive Lipschitz bounds for the drift and diffusion coefficients, as well as the JE weight integrand, without relying on global convexity.

Key Contributions

Extension to $\beta < 1$ : The primary contribution is a polynomial-time sampling algorithm for the SK model for any fixed $\beta < 1$ , improving upon the previous $\beta < 1/2$ barrier.
Local Regularity Framework: The paper formulates a set of "desiderata" that relax the global regularity requirements of prior work to local regularity over a safe set. This framework is shown to be sufficient for the ASL-JE analysis.
Hybrid Convexity Proof: The authors prove that the TAP Hessian is uniformly locally strongly convex along the entire stochastic localization path by combining Celentano's local convexity result for AMP iterates with the stability of the SL process.
Refined Resolvent Analysis: The paper introduces a regularized resolvent extension and a simplified free interpolation argument using block-matrix representations to control the diagonal of the resolvent, bypassing previous technical bottlenecks related to tensor products and covariance structures.
Rejection Sampling Analysis: A rigorous analysis of the rejection sampling step using a "survival-based" Jarzynski equality is provided, ensuring that the error from discarding trajectories remains $o_n(1)$ .

Results
The paper establishes Theorem 1.1: For any fixed $0 < \beta < 1$ and $\delta > 0$ , there exists an $n_0(\beta, \delta)$ such that for all $n \geq n_0$ , with probability at least $1-\delta$ over the disorder $A$ , the proposed algorithm (Algorithm 2) outputs a sample from a distribution that is $o_n(1)$ close in TVD to the Gibbs measure $\mu_{\beta A}$ in polynomial time.

The analysis relies on verifying the updated desiderata:

(d1) Covariance estimation error is bounded.
(d2a) The TAP Hessian is uniformly locally strongly convex along the SL path.
(d2b) The TAP Hessian satisfies local regularity (Löwner sandwich) bounds.
(d3)-(d5) Drift, diffusion, and JE weight terms satisfy necessary Lipschitz and error bounds on the safe set.

Significance
The paper claims to be a significant step toward resolving the conjecture that Glauber dynamics exhibits fast mixing for the SK model below the de Almeida-Thouless (dAT) line ( $\beta < 1$ ). By demonstrating that algorithmic stochastic localization can bypass the global convexity barrier through local regularity and rejection sampling, the work provides a new pathway for sampling in spin glass models where global functional inequalities are difficult to establish. The authors note that their approach combines ASL with fast-mixing results for localized distributions (via [KSTZ26]) to achieve the final sampling guarantee.

The work also highlights that the regime $\beta < 1$ is sharp for their approach, as it is known that no stable algorithm (including ASL) can sample with small $W_2$ distance for $\beta > 1$ , and worst-case Glauber dynamics mixes exponentially slowly in that regime. The paper does not claim to solve the sampling problem for $\beta \geq 1$ or to prove fast mixing for Glauber dynamics directly, but rather provides an efficient sampler for the Gibbs measure in the high-temperature regime up to the believed computational threshold.

More like this