High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
Abstract
Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice 𝒳kd:={x∈{± 1}d:|{i:xi=1}|=k}, in high-dimensional regimes where k≪ d (i.e., where 𝒳kd 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 𝒳kd. 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≳ k3log3 d Gaussian measurements. We improve this requirement to n≳ k3/2log2 d+klog3 d, using a common sparsity-aware framework underlying both our results.
Related
- SelectPFN: Amortized Bayesian Variable Selection for Sparse Nonlinear Regression with Prior-Data Fitted Networks
- Rapid reconstruction-free classification from Lissajous sparse sampling using deep learning
- Byzantine-Robust Sparse Regression with Missing Covariates
- Sparse-group Convoluted Smoothed Quantile Regression in High Dimension
- Decentralized Sparse Quantile Regression
BibTeX
@misc{kumar2026highmagnetization,
title = {{High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression}},
author = {Syamantak Kumar and Purnamrita Sarkar and Kevin Tian and Yusong Zhu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08873},
eprint = {2609.08873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08873},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
AU - Syamantak Kumar
AU - Purnamrita Sarkar
AU - Kevin Tian
AU - Yusong Zhu
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08873
UR - https://arxiv.org/abs/2609.08873
AB - Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice 𝒳_k^d:={x∈{± 1}^d:|{i:x_i=1}|=k}, in high-dimensional regimes where k≪ d (i.e., where 𝒳_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 𝒳_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≤ 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≳ k^3log^3 d Gaussian measurements. We improve this requirement to n≳ k^3/2log^2 d+klog^3 d, using a common sparsity-aware framework underlying both our results.
ER -