Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the parallel complexity of sampling from the high-temperature Ising mixed $p$-spin Gibbs measure, introducing two distinct algorithms tailored for different accuracy regimes. The first algorithm employs a parallelized block dynamics Markov chain with an innovative rejection sampling step, achieving $\varepsilon$-close samples in $n^{\tfrac{1}{3}}\operatorname{polylog}(\tfrac{n}{\varepsilon})$ parallel time. The second algorithm leverages Picard iterations to enhance the Algorithmic Stochastic Localization process, yielding a doubly exponential improvement in runtime and an exponential reduction in total work compared to traditional methods.
Achieving a doubly exponential speedup in sampling from the $p$-spin model could revolutionize computational efficiency in spin glass research.
We study the parallel complexity of sampling from the high-temperature Ising mixed $p$-spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube $\{\pm 1\}^n$. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a parallel implementation of a Markov chain known as block dynamics, combined with an approximate rejection sampling step that uses an Ising model in a novel way as a proposal distribution to approximate the quadratic interaction terms of the $p$-spin Hamiltonian. For any $\varepsilon>0$, this algorithm runs in $n^{\tfrac{1}{3}}\operatorname{polylog}(\tfrac{n}{\varepsilon})$ parallel time with $\operatorname{poly}(n, \log(\tfrac{1}{\varepsilon}))$ work, and outputs a sample whose law is $\varepsilon$-close to the $p$-spin measure in total variation distance. Our second algorithm uses Picard iterations to parallelize the Algorithmic Stochastic Localization (ASL) process of El Alaoui, Montanari, and Sellke (2025), and for any $\varepsilon>\varepsilon_n$, takes $\operatorname{polylog}(\tfrac{n}{\varepsilon})$ parallel time and $\operatorname{poly}(\tfrac{n}{\varepsilon})$ work to produce a sample that is $\varepsilon$-close to the $p$-spin measure in the normalized 2-Wasserstein metric. Here, $\varepsilon_n>0$ is a threshold that goes to $0$ as $n \to \infty$. Our result constitutes a doubly exponential improvement in the $\varepsilon$ dependence of the runtime and an exponential improvement in the $\varepsilon$ dependence of the total work when compared to na\"ive ASL, whose runtime scales as $\exp(\operatorname{poly}(\tfrac{1}{\varepsilon}))$.