Search papers, labs, and topics across Lattice.
The authors develop an algorithmic framework for sampling over highly magnetized Hamming slices ($k \ll d$) at low temperatures, applying it to both Sherrington–Kirkpatrick (SK) spin glasses and Bayesian sparse linear regression. For the SK model, their method achieves polynomial-time sampling at arbitrarily low temperatures under strong external fields, coming within constant factors of the Almeida–Thouless replica-symmetry-breaking transition. For canonical Gaussian spike-and-slab posterior inference, the framework sharply reduces the required measurement complexity from $n \gtrsim k^3 \log^3 d$ to $n \gtrsim k^{3/2}\log^2 d + k\log^3 d$.
Polynomial-time sampling in spin glasses and sparse Bayesian regression is tractable deep into low-temperature regimes, slashing the measurement barrier for spike-and-slab posteriors from $k^3$ to $k^{3/2}$ while approaching the Almeida–Thouless phase boundary.
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.
