Metraipolis › archive › dc_d431df3a2763

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08873
License (as archived)
CC0-1.0
Archived
2026-10-16T14:02:35.363Z
SHA-256 of the archived text
34e9f3d176d7ea55187da2a81193a7e8d5e43e20bb070e9880cc87aff0272b42
Stable URL of this page
https://metraipolis.com/documento/dc_d431df3a2763

How to cite

High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression — arXiv:2609.08873 — arXiv (en), https://arxiv.org/abs/2609.08873 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d431df3a2763 (Metraipolis archive dc_d431df3a2763, sha256 34e9f3d176d7ea55187da2a81193a7e8d5e43e20bb070e9880cc87aff0272b42)
BibTeX
@misc{dcd431df3a2763,
  title = {High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression — arXiv:2609.08873},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08873},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d431df3a2763; sha256 34e9f3d176d7ea55187da2a81193a7e8d5e43e20bb070e9880cc87aff0272b42},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08873. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\beta>0$, under arbitrary external fields, provided that $k\le c_\beta d$ for an appropriate constant $c_\beta$. 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-$\beta$ 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(\beta)$ 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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG); Probability (math.PR); Statistics Theory (math.ST); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.08873 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:39:43.299Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).