High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression

arXiv:2609.08873v1 Announce Type: cross Abstract: Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice X_k^d:={mathbf{x}in{pm 1}^d:|{i:mathbf{x}_i=1}|=k}, in high-dimensional regimes where kll d (i.e., where X_k^d is highly magnetized). We use our frameworks to design improved samplers for canonical problems in the study of Ising models and Bayesian sparse linear regression. Our first main result considers the Sherrington--Kirkpatrick (SK) model restricted to fixed-magnetization slices X_k^d. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature eta>0, under arbitrary external fields, provided that kle c_eta d for an appropriate constant c_eta. 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-eta limit, our framework permits sampling at field strengths within constant factors of the Almeida--Thouless line delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength h(eta) 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 Gaussian spike-and-slab posterior with expected sparsity k, at any signal-to-noise ratio, given ngtrsim k^3log^3 d Gaussian measurements. We improve this requirement to ngtrsim k^{3/2}log^2 d+klog^3 d, using a common sparsity-aware framework underlying both our results.

Source: arXiv cs.LG | 2026-09-09