PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu

arXiv:2609.08873v1cs.DScs.LGmath.PRmath.STstat.MLstat.TH

TL;DR

The paper asks how sparsity can make high-dimensional sampling tractable, including for hard-constrained SK models and Bayesian sparse regression. It develops sparsity-aware sampling frameworks, yielding polynomial-time fixed-magnetization SK sampling and lower measurement requirements for spike-and-slab posterior sampling.

  • Problem

    The paper asks whether hard magnetization constraints make SK sampling tractable and what measurement threshold permits polynomial-time spike-and-slab posterior sampling, a computationally challenging route to uncertainty in variable selection.

    Source: §1 · p. 4

  • Method

    It builds a shared sparsity-aware framework around down-up-walk analysis, then applies it to fixed-magnetization SK sampling and Bayesian posterior sampling.

    Source: §1 · pp. 4–5, §1.2 · p. 7

  • Results

    Polynomial-time SK sampling holds for k ≤ c_βd at fixed β and arbitrary fields; high-field sampling reaches within constant factors of the AT line, while Bayesian SLR needs n ≳ k^1.5 polylog(d).

    Source: §1.1 · pp. 5–6, §1 · p. 5

  • Takeaways & Limitations

    Sparsity serves as a shared structural handle for both Ising-model sampling and Bayesian posterior sampling.

    Source: §1 · p. 3

    The approach retains an extra k factor over frequentist sparse recovery; avoiding its worst-case union bound remains open.

    Source: §1.2 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The introduction develops sparsity-aware approaches to tractable high-dimensional sampling, with applications to high-magnetization SK models and Bayesian sparse linear regression. It outlines how sparse recovery, annealing, and trickle-down analysis support the samplers and positions their guarantees in relation to prior work.

1 Introduction

  • The paper asks whether imposing high magnetization as a hard constraint can make SK sampling tractable, and uses that sparsity-aware framework to motivate Bayesian sparse linear regression sampling.The introduction contrasts hard-constrained sparsity with sparsity induced by a strong external field.Source: §1 · pp. 3–4

1.1 Our results

  • For fixed-magnetization SK models with GOE interactions, polynomial-time sampling succeeds for any fixed β > 0 when k ≤ c_βd, under arbitrary external fields and with high probability over J.The algorithm is the down-up walk on the Hamming slice.Source: §1.1 · p. 5
  • The strong-field threshold h_HM(β) = 2(1 + o(1))h_AT(β) is within a constant factor of the AT line, versus h = Ω(β^2√log β) for.With access to the signs of the mean vector, a modified sampler works at h ≥ (1 + o(1))h_AT(β).Source: §1.1 · p. 6
  • n ≈ k^1.5 log^2 d measurements improve quadratically in k over the n = Ω(k^3 log^3 d) requirement of [KSTZ25] for spike-and-slab posterior sampling.The algorithm is polynomial-time and applies for every σ > 0.Source: §1.1 · p. 6

1.2 Our techniques

  • The sparse Dobrushin condition controls the down-up walk using conditional-law discrepancies, yielding a variant of the SK result for k ≤ c_βd/log d.For fixed-magnetization Ising models, the discrepancy is controlled by β max_{i≠j}|J_ij| independently of the external field; the condition does not capture cancellation among signed interactions.Source: §1.2 · pp. 6–7
  • The trickle-down framework reduces global mixing to spectral expansion of link graphs and uses sparse-operator-norm bounds to extend the SK result to k = Θ(d).The link weights are treated as a perturbation of rank-one weights, with a second-order expansion controlling the second eigenvalue.Source: §1.2 · p. 7
  • Annealing lifts fixed-magnetization samplers to bounded-magnetization sampling by estimating the normalizing constants that weight the mixture of slices.The reduction builds on the estimator of.Source: §1.2 · p. 8
  • The posterior sampler combines sparse-recovery preprocessing, annealing to fixed magnetization, and trickle-down analysis of the residual posterior’s down-up walk.Preprocessing identifies nearly deterministic coordinates; after pinning a core, the induced weights involve inverse and determinant terms, with a Schur-complement correction making the perturbation depend on the core.Source: §1.2 · p. 8
  • The union-bound estimate yields an n ≳ k^1.5 bottleneck; removing the extra k factor beyond frequentist sparse-recovery complexity is left open.The proposed direction is average-case trickle-down theorems that avoid the union bound over worst-case dependencies.Source: §1.2 · p. 8

1.3 Related work

  • Unlike [CDKP22] [KPPY25], whose magnetization thresholds decay exponentially in β and are nontrivial only up to β ≈ log d, our frameworks improve as k → 1 and tolerate β up to poly(d).The earlier works study fixed-magnetization problems with improved phase transitions or critical β as the positive-spin count k decreases.Source: §1.3 · p. 9
  • Against, the field-strength tolerance reaches within constant factors of the Almeida–Thouless line, or within 1 + o(1) when given the mean-vector signs.The Almeida–Thouless line is the benchmark for the replica-symmetry transition in the SK model with a homogeneous external field.Source: §1.3 · p. 9
  • [KSTZ25] gave the first provable spike-and-slab posterior samplers for arbitrary SNR with sublinear n, and our result quadratically improves their k dependence.The passage identifies [KSTZ25] as the closest prior work.Source: §1.3 · p. 10

2 Preliminaries

The preliminaries establish shared notation, Markov-chain tools, and statistical models used by the paper’s analyses.

2.1 Notation

  • Notation covers vector and matrix norms, sparse quantities, Hamming distance, probability measures, and standard vector and matrix conventions.Informal comparison symbols suppress polylogarithmic factors; formal statements specify dependencies explicitly.Source: §2.1 · pp. 10–11

2.2 Markov chains

  • The down-up walk removes one element from a size-k set, then adds an element sampled from the conditional target measure.Its stationary measure is the target distribution; Poincaré inequalities provide a route to mixing-time bounds.Source: §2.2 · pp. 12–13
  • A path-coupling tool bounds mixing by contracting adjacent states under a suitable metric and extending the contraction along paths.The paper develops this tool for fixed- or bounded-magnetization measures.Source: §2.2 · p. 13

2.3 Statistical models

  • The statistical models include fixed- or bounded-magnetization Ising measures, SK and Gaussian Hopfield interactions, and spike-and-slab Bayesian regression.The regression goal is posterior sampling given Gaussian measurements and observed responses.Source: §2.3 · pp. 14–15

3 Sparse Dobrushin Condition

This section introduces a sparse Dobrushin condition as a sufficient condition for rapid mixing of the down-up walk, then applies the framework to fixed-magnetization Ising models. The Ising application controls the condition using interaction strengths and yields a mixing bound independent of the external field.

3 Sparse Dobrushin Condition

  • The framework applies a sparse Dobrushin condition to the down-up walk over k-element subsets of a discrete universe.The abstract universe formulation recovers the Hamming-slice setting by taking U = [d].Source: §3 · pp. 15–16
  • This section’s Ising applications generally have weaker parameter tradeoffs than the later framework, while trading stricter parameter requirements for faster mixing.The authors present them as a proof-of-concept for temperature improvements in fixed-magnetization settings.Source: §3 · p. 15

3.1 Basic analysis

  • For neighboring states, a coupling coordinates down-steps and then couples the up-step additions to control expected Hamming distance.When the down-step states match, the subsequent up-step can be perfectly coupled.Source: §3.1 · pp. 16–17
  • Under the stated sparse Dobrushin condition, the down-up walk mixes in O(k log(k/ε)) steps.The proposition allows any initial distribution and takes α at most a constant factor below 1/k.Source: §3.1 · p. 17

3.2 Fixed-magnetization Ising models

  • For fixed-magnetization Ising models, the sparse Dobrushin parameter is controlled by the largest off-diagonal entry of J, yielding a mixing bound independent of h.The section also gives sufficient sampling conditions for Models 1 and 2.Source: §3.2 · pp. 18–20
  • The Ising bound is independent of h because the conditional distributions exclude the differing coordinates that induce the external-field difference.The argument combines the Ising condition bound with the general mixing proposition.Source: §3.2 · p. 19

4 Spectral Mixing via Trickle Down

This section develops a trickle-down framework for mixing on fixed-magnetization measures and tightens the SK mixing analysis, including high-probability sampling conditions. It applies the framework to SK and Gaussian Hopfield models and establishes tighter parameter tradeoffs than the sparse Dobrushin approach.

4.2 Simple sufficient conditions for fast mixing

  • For SK, the sufficient-condition application yields fast mixing in the near-proportional magnetization regime k = Oβ(d log d), improving the allowable temperature range by a k factor.The result still cannot take arbitrary β = O(1) unless k is sufficiently sublinear in d, because a logarithmic factor obstructs the bound.Source: §4 · p. 20, §4.2 · p. 26
  • The same sufficient-condition approach also derives an analogous fast-mixing result for the Gaussian Hopfield model.The analysis uses both terms of the sufficient condition to accommodate the two-regime sub-exponential concentration of Wishart operator norms.Source: §4 · p. 20, §4.2 · p. 26

4.1 Trickle down framework

  • The framework bounds down-up walk mixing through spectral gaps of link graphs, using a perturbation-of-rank-one bound to control those gaps.For a perturbation K, the link-walk second eigenvalue is bounded by exp(m(K))ρ(K); the framework specializes this approach to fixed-magnetization Ising models.Source: §4.1 · pp. 21–23

4.2 Simple sufficient conditions for fast mixing

  • An interpretable sufficient condition qualitatively recovers sparse Dobrushin and supports improved mixing applications for fixed-magnetization Ising models.One specialization recovers the sparse Dobrushin condition; another controls the perturbation through a mixed-norm quadratic-form bound.Source: §4.2 · p. 24

4.3 Linear magnetization in low-temperature SK models

  • The tighter analysis removes the extraneous logarithmic factor from Corollary 3’s bounds on quantities required by Lemma 7.These results hold on a high-probability event under Model 1.Source: §4.3 · p. 27
  • On the stated event and assumptions, Lemma 13 bounds m(K) by C′ barβ^2 Δ for K = 4βJ.Here barβ = max(β, 1), and the lemma also derives estimates on ρ(K).Source: §4.3 · p. 28
  • Under the stated conditions, Theorem 4 gives a high-probability sampling guarantee for fixed-magnetization Ising models.Its proof uses a lazy down-up walk whose chi-squared divergence contracts by Ω(1/k) per iteration; the result assumes condition (31) and has a failure-probability restriction.Source: §4.3 · pp. 29–30
  • Theorem 4’s failure-probability condition permits δ = exp(−Ω(d)), and using barβ = max(β, 1) makes its k upper bound uniform over β ≥ 0.If the assumptions hold at a target β⋆, they hold for every intermediate β in [0, β⋆], which is relevant to annealing.Source: §4.3 · p. 30

5 Annealing

The framework decomposes bounded-magnetization Gibbs sampling into choosing a size and sampling conditionally at that size. It combines this procedure with fixed-magnetization samplers to obtain bounded-magnetization Ising samplers.

5.2 Approximate bounded-magnetization sampling

  • The framework first samples a cardinality using estimated mixture weights, then invokes the corresponding fixed-size sampler; coupling controls error from approximate samplers.Accurate mixture weights and component distributions suffice for an accurate approximation of the bounded-magnetization measure.Source: §5 · p. 30, §5.2 · p. 32

5.1 Estimating normalizing constants

  • Adapting, EstimateZ uses a sampler for tempered distributions to estimate a target normalizing constant, with success probability at least 1−δ.The initial normalizing constant is known exactly: Z(0)=|Ω|.Source: §5.1 · p. 31

5.3 Bounded-magnetization Ising models

  • On the bounded-magnetization domain, the potential variation from the all-negative configuration is at most (2k + 4d) ∥J∥_2k,op + 2 ∥h∥_k,1.This bound supplies a magnitude control for applying the general sampling framework.Source: §5.3 · p. 34
  • The bounded-magnetization SK sampler has total variation error at most δ and succeeds with probability at least 1−δ.The result applies by instantiating the framework with fixed-magnetization samplers.Source: §5.3 · p. 34

6 Bayesian Sparse Linear Regression

Section 6 develops a sparsity-aware approach to sampling the Gaussian spike-and-slab posterior, combining support-posterior analysis with preprocessing that reduces the support before sampling. It establishes conditions and potential and mixing bounds for rapid mixing on fixed-size restrictions as a step toward sampling the bounded-size posterior.

6 Bayesian Sparse Linear Regression

  • The sampling pipeline uses sparse-recovery preprocessing to remove coordinates whose inclusion is determined by observations up to negligible posterior mass, then samples from the preprocessed support posterior [KSTZ25].The section applies the earlier local-to-global framework; its stated plan is to lift samplers for fixed-size restrictions to the bounded-size posterior.Source: §6 · p. 35

6.1 Setup

  • The preprocessing guarantee decomposes its output into a short vector with bounded sparse ℓ2 norm and a flat vector with bounded ℓ∞ norm, refining the guarantee needed from prior work [KSTZ25] [CLTZ26].The decomposition is used to obtain the improved sample-complexity analysis; the strategy is reminiscent of.Source: §6.1 · p. 35

6.2 Trickle down for support posterior

  • Proposition 4 states that, when the events of Proposition 3 and Lemma 18 hold, T DU,νs,β satisfies a 1/(2k)-Poincaré inequality.Source: §6.2 · p. 41
  • The support-posterior analysis bounds the potential range and combines it with mixing and spectral-gap guarantees to ensure lazy down-up-walk sampling within δ′ total variation of νs,β.The potential-range bound is recorded for use with Section 5.Source: §6.2 · pp. 43–44

6.3 Main result

  • Algorithm 3 outputs a draw within total-variation distance δ of π(· | X, y) with probability at least 1−δ under Model 3.The stated result assumes q ∈ [η, 1−η]^d for η > 0.Source: §6.3 · p. 44
  • The extended draw approximates the support posterior, the BMGibbsSampler draw approximates that extended draw, and the exact conditional draw cannot increase total-variation distance.The proof combines the support-posterior approximation with the sampler guarantee and then draws θ conditioned on the extended support.Source: §6.3 · p. 45
  • Under q ∈ [η, 1−η]^d, the potential FC is bounded by O(Q), and each down-up-walk step can be implemented in O(ndk) time.These bounds support the sampler's implementation-cost analysis.Source: §6.3 · p. 45

AI Disclosure

The disclosure describes the use of GPT 5.6 Pro to explore a proof-technique application and acknowledge literature assistance.

AI Disclosure

  • A reviewer suggestion prompted GPT 5.6 Pro exploration of trickle-down applications; the perturbation strategy in Lemma 7 was suggested by GPT and led to a weaker variant of Theorem 1.The authors state that they built on this approach in the final applications in Theorems 1 and 2.Source: AI Disclosure · p. 46
  • The authors also acknowledge LLM assistance in understanding Almeida–Thouless-line literature and preparing Appendices A and B.They state that the manuscript was written solely by the authors, who take responsibility for its organization and presentation.Source: AI Disclosure · p. 46

A Sampling Near the Almeida–Thouless Line

The section considers sampling near the Almeida–Thouless line, which separates predicted replica-symmetric and replica-symmetry-breaking regimes. The stated results require the more restrictive weak AT line to obtain a stronger quantitative concentration estimate.

A Sampling Near the Almeida–Thouless Line

A.1 Preliminaries

This section establishes asymptotic properties of the AT boundaries and shows how sufficiently large external fields concentrate the SK measure on high-magnetization states.

Preliminaries

  • The section’s preliminary results establish asymptotics for the AT and weak AT boundaries, then relate large fields to concentration on high-magnetization states.The concentration argument bounds the weights of states with large minority-spin sets and sums those bounds across layers.Source: §A.1 · pp. 54–56

Boundary asymptotics

  • The AT fixed point satisfies q_AT → 1 as β grows, and the weak AT fixed point is also shown to approach 1.The passages give 1 − q_AT ≤ β^-1 and 1 − q_wAT = β^-2.Source: §A.1 · pp. 54–55

Magnetization from field strength

  • The binary entropy H2(s) is used in bounding layer weights to show that sufficiently large fields concentrate the measure on high-magnetization states.The partition function is bounded below by the empty-set weight, and the layer bounds are summed over sizes above the target fraction.Source: §A.1 · pp. 55–56

Concentration bounds

  • A Gaussian tail bound and a union bound control the SK interaction over all nontrivial layers with high probability.The argument counts subsets of each size using binary entropy and applies the Gaussian tail bound to their interaction sums.Source: §A.1 · pp. 55–56

A.2 Sampling around 1d

This section gives a field-strength-based route to sampling the SK measure by reducing it to sampling on a high-magnetization region. The resulting algorithm runs in polynomial time under the stated conditions.

Sampling around 1d

  • The section’s basic variant uses a field threshold tied to the AT boundary to obtain concentration on high-magnetization states.The passage states that the field must exceed h_AT(β) by an additional amount, but the supplied text does not preserve that amount fully.Source: §A.2 · p. 56
  • A polynomial-time algorithm samples from π_β,h within total variation distance δ when the field makes the measure concentrate on states with at most k minority spins.The result holds with probability at least 1 − δ over the SK model, under the section’s stated conditions on β, h, k, and δ.Source: §A.2 · pp. 56–57
  • The method reduces sampling from π_β,h to sampling conditioned on at most k minority spins, then applies the bounded-magnetization sampler.The proof chooses k from the sparsity lower-bound parameter and combines concentration with the bounded-magnetization guarantee.Source: §A.2 · pp. 56–57

A.3 Sampling around the mean

This section strengthens the field-based SK sampler by centering sparsity around the signs of the mean magnetization. Under its assumptions, it gives polynomial-time sampling at a field threshold matching the AT and weak AT scales up to a 1 + o(1) factor.

Sampling around the mean

  • Theorem 7 gives a polynomial-time sampler at field strengths h ≥ h_OC(β), with threshold matching the AT and weak AT thresholds up to a 1 + o(1) factor.The result also assumes access to the signs of the mean magnetization vector and the stated sparsity and concentration bounds.Source: §A.3 · p. 60
  • The proof uses D := diag(τ⋆) to show that the fixed-magnetization sampler in Theorem 4, and hence the bounded-magnetization sampler in Corollary 5, is invariant under J ← DJD.The rest of the proof is identical to Theorem 6 under the change of variables x ← Dx.Source: §A.3 · p. 60
  • The field threshold scales as h = Ω(β^2√log β), roughly β times larger than h_AT(β).The paper states that h_OC(β) matches the AT and weak AT thresholds up to a 1 + o(1) factor.Source: §A.3 · p. 60
  • Theorem 7 is conditional on knowing τ⋆, the signs of the mean magnetization vector; computing τ⋆ efficiently remains open.The algorithm recenters its notion of sparsity on disagreement with τ⋆ rather than disagreement with 1d.Source: §A.3 · pp. 57, 60
  • The chosen h_OC(β) may include unnecessary low-order terms, and improving the threshold enough to sample throughout the AT region remains open.The paper attributes the extra terms to a mismatch between the weak AT condition and the sparsity requirement of the bounded-magnetization sampler.Source: §A.3 · pp. 58, 60

B Scaling of Infinite ∆-Regular Tree Threshold

This section relates the infinite regular-tree threshold to sparsity levels in prior graph-based results and to the temperature range of the paper’s framework. For Models 1 and 2, the framework allows inverse temperatures as large as poly(d) when k is sufficiently small.

Infinite Δ-regular tree threshold

  • The infinite Δ-regular tree has a critical inverse temperature β_c(Δ) = log(Δ/(Δ−2)), with a unique message-passing fixed point below it and two new fixed points above it.The corresponding sparsity threshold satisfies 1 − η_β = exp(−Δβ + O_Δ(1)).Source: B Scaling of Infinite ∆-Regular Tree… · pp. 60–61
  • The tree-threshold calculation gives 1 − η_β = exp(−Δβ + O_Δ(1)).This asymptotic follows by approximating tanh at large arguments and substituting into the definition of η_β.Source: B Scaling of Infinite ∆-Regular Tree… · p. 61

Threshold implications

  • For constant-degree graphs, the sparsity regime in [CDKP22] is meaningful only for inverse temperatures β = O(log d), and [KPPY25] is subject to the same restriction.The section compares allowable temperatures for the sparsity-aware framework, not the direct performance of its samplers on those graph models.Source: B Scaling of Infinite ∆-Regular Tree… · p. 61
  • For Models 1 and 2, the framework permits inverse temperatures as large as β = poly(d) when k is sufficiently small.This statement concerns the temperature range tolerated by the framework, unlike its application to the cited graph-based models.Source: B Scaling of Infinite ∆-Regular Tree… · p. 61

Related papers

Loading 2609.08873v1…