High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
Authors: Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
Abstract
Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice Xkd:={x∈{±1}d:∣{i:xi=1}∣=k}, in high-dimensional regimes where k≪d (i.e., where Xkd is \emph{highly magnetized}). We use our frameworks to design improved samplers for canonical problems in the study of \emph{Ising models} and \emph{Bayesian sparse linear regression}. Our first main result considers the \emph{Sherrington--Kirkpatrick} (SK) model restricted to fixed-magnetization slices Xkd. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature β>0, under arbitrary external fields, provided that k≤cβd for an appropriate constant cβ. By combining this result with an annealing strategy for estimating normalizing constants, we obtain polynomial-time samplers for the SK model at arbitrarily low temperatures under a sufficiently strong external field of strength h. In the large-β limit, our framework permits sampling at field strengths within constant factors of the \emph{Almeida--Thouless line} delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength h(β) required by the recent work of [BAR26]. Our second main result concerns the measurement complexity of polynomial-time Bayesian sparse linear regression. Recent work by [KSTZ25] shows how to sample from the canonical \emph{Gaussian spike-and-slab posterior} with expected sparsity k, at any signal-to-noise ratio, given n≳k3log3d Gaussian measurements. We improve this requirement to n≳k3/2log2d+klog3d, using a common sparsity-aware framework underlying both our results.
We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold λmax(J)−λmin(J)=1, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.
Autoregressive Neural Networks based on dense or convolutional layers have recently been shown to be a viable strategy for generating classical spin systems. Unlike these methods, sampling with transformers is commonly considered to be computationally inefficient. In this work, we propose a novel approach to transformer-based neural samplers in which we generate not a single spin per step but groups of spins. As an additional improvement, we construct a model of approximated probabilities, further improving the efficiency of the algorithm. Despite our approach being computationally heavier than dense networks or CNN-based approaches, we were able to sample larger systems of up to 180×180 spins in case of the Ising model. The Effective Sample Size of our sampler is ∼20 times larger than that of the previous state-of-the-art neural sampler when trained for the 128×128 Ising model at critical temperature. Finally, we also test our algorithm on the 2D Edwards-Anderson model, where we train 64×64 spin systems.
Efficient sampling from Boltzmann distributions over discrete variables is a fundamental operation in a wide range of applications. While fast non-MCMC samplers have recently emerged as promising alternatives to conventional MCMC methods, their practical use for probabilistic learning remains hindered by the difficulty of estimating the effective temperature of the generated samples. In this work, we begin by introducing Langevin simulated bifurcation (LSB), a Boltzmann sampler that enables fast and parallel sampling with accuracy comparable to sequential MCMC methods. To address the challenge of unknown effective temperature, we propose conditional expectation matching (CEM), an efficient estimation method applicable to energy-based models (EBMs) with exploitable conditional independence structures. Building on these components, we further develop a learning framework, termed sampler adaptive learning (SAL), which adaptively adjusts the model temperature to match that of the distribution induced by fast non-MCMC sampling. We demonstrate the effectiveness of LSB, CEM, and SAL on semi-restricted Boltzmann machines (SRBMs), a class of EBMs that are difficult to train using conventional approaches. LSB achieves orders-of-magnitude acceleration over Gibbs sampling while maintaining comparable or higher accuracy, and CEM enables accurate temperature estimation of the resulting distribution with negligible computational overhead. As a consequence, SAL enables efficient training of SRBMs and outperforms conventional Boltzmann machine learning methods on synthetic spin-glass datasets. In addition, the trained models achieve strong performance across multiple tasks. These results establish LSB as a fast and accurate Boltzmann sampler and provide key insights that enable practical applications of fast non-MCMC sampling methods via efficient temperature estimation with CEM.