Polynomial time algorithm samples Sherrington Kirkpatrick model below critical temperature
Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $β< 1$
Data Structures and Algorithms
Summary
Sampling complex systems described by the Sherrington-Kirkpatrick (SK) model, such as certain types of magnets or neural networks, is difficult at low temperatures. The authors developed a new algorithm that efficiently generates approximate samples from this model for temperatures above a specific threshold (inverse temperature β less than 1). Their method improves upon previous work by using local properties of the system instead of requiring global smoothness, making the sampling more practical. This advance relies on mathematical tools from statistical physics and probability theory to better understand the underlying energy landscape.
What this means in practice
- •For computational physicists: Generate efficient approximate samples from spin glass models for studying disordered magnetic systems and complex networks.
- •For machine learning practitioners: Use the algorithm to better sample from complex energy landscapes arising in optimization and probabilistic inference problems.
Authors
Holden Lee, Juspreet Singh Sandhu, Jonathan Shi
Abstract
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $β< 1$. The algorithm combines algorithmic stochastic localization (ASL) with rejection sampling over path-space via Jarzynski's equality (JE). The analysis extends the authors' prior $β< 1/2$ result [arXiv:2605.03718] by replacing all global regularity requirements in the stochastic differential equation (SDE) error analysis with local regularity around likely trajectories. The relaxed regularity is established using Celentano's proof of the local strong convexity of the TAP free energy [arXiv:2208.09550]. The analysis utilizes the cavity interpolation theory and free probability toolkit developed in the authors' previous result, where the former applies nearly verbatim and the latter applies supplemented with Lipschitz and $C^2$ extensions of various functions. The ASL and JE analysis arises from using the TAP free energy as an efficiently computable proxy for the actual free energy of the stochastically localized Gibbs measure [$ §$ 3, arXiv:2605.03718]. We give a list of \vocab{desiderata} encapsulating the approximation and regularity properties required of the TAP free energy, relaxing those of [$ §$ 2.5, arXiv:2605.03718] to only require local regularity. These generic desiderata are potentially applicable in other settings where a free energy surrogate exists, giving algorithmic sampling guarantees while bypassing the usual functional inequalities based approach.