Improved algorithms enable sampling and sparse regression at low temperatures
High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
Data Structures and AlgorithmsMachine Learning
Summary
Sampling or picking examples with specific patterns, especially very few positive signs in large datasets, is challenging when things are noisy or complicated. The authors developed new computational methods that work efficiently even in tough cases involving magnetic models and statistical regression with lots of noise. Their approach reduces the amount of data needed and improves the ability to sample at very low temperatures, where systems are usually harder to analyze. These advances build on mathematical properties of sparsity, or having many zeros, to speed up complex computations.
What this means in practice
- •For machine learning engineers: Train sparse regression models with fewer data samples by efficiently sampling from complex posterior distributions under noisy conditions.
- •For statistical physicists: Simulate Ising spin systems at fixed magnetization and low temperatures more efficiently, even near critical phase boundaries.
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 $\mathcal{X}_k^d:=\{\mathbf{x}\in\{\pm 1\}^d:|\{i:\mathbf{x}_i=1\}|=k\}$, in high-dimensional regimes where $k\ll d$ (i.e., where $\mathcal{X}_k^d$ 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 $\mathcal{X}_k^d$. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature $β>0$, under arbitrary external fields, provided that $k\le 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\gtrsim k^3\log^3 d$ Gaussian measurements. We improve this requirement to $n\gtrsim k^{3/2}\log^2 d+k\log^3 d$, using a common sparsity-aware framework underlying both our results.