CS Paper Radar

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

Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu

cs.DS cs.LGmath.PRmath.STstat.ML ·submitted 2026-09-08 15:13 UTC · v1

Abstract

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.

Comment
61 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Rapid mixing within a phase for Ising models

cs.DS math.PRmath-ph ·2026-10-16 ·Vasyl Paliy, Youngtak Sohn
theory similarity 0.60
Abstract · 42 pages

We study Glauber dynamics for Ising measures conditioned to have a sufficiently large majority of $+1$ spins. Under a sparse spectral width condition on the interaction matrix, we derive a Poincaré inequality for the conditioned measures from a magnetization drift condition, and a modified logarithmic Sobolev inequality from a stronger, entropy weighted condition. As applications, we obtain approximate posterior sampling in total variation distance for $\mathbb{Z}_2$ synchronization at high enough signal-to-noise ratio using $O(n\log n)$ Glauber updates from a spectral initialization. For ferromagnetic Ising models on random $d$-regular graphs, we prove rapid phase ordering down to inverse temperatures of order $1/d$, extending the temperature range of Gheissari, Sly, and Sohn (2025). Finally, we extend these inequalities to unconditioned Ising measures under an inward drift condition outside the conditioned region. This yields $O(n\log n)$ mixing of Glauber dynamics for the Sherrington-Kirkpatrick model at every fixed inverse temperature when the external field is sufficiently large.

0.20

Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

cs.DS math.PR ·2026-10-07 ·Zhe Hou, Jingcheng Liu, Yixiao Yu
similarity 0.59
Abstract

We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.

0.39

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

cs.DS math.PR ·2026-08-19 ·Zhidan Li, Kuan Yang
similarity 0.58
Abstract

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

0.18

Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

cs.LG stat.MLmath.PR ·2026-09-06 ·Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar, Hoang-Son Tran
benchmark similarity 0.58
Abstract

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{$ε$-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{$(k,z)$-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible $\varepsilon$-coreset for $(k,z)$-clustering in $\mathbb R^d$ whose dependence on $1/\varepsilon$ has exponent strictly smaller than $2$ when $d$ is fixed. This improves over the worst-case $\varepsilon^{-2}$ barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.

0.16

Large-System Analysis of Sparse Bayesian Learning

eess.SP cs.IT ·2026-09-06 ·Fangqing Xiao, Dirk T. M. Slock
similarity 0.58
Abstract

Sparse Bayesian learning is widely used for sparse linear inverse problems, yet its large-system stationary behavior remains poorly understood because all variance hyperparameters are estimated from the same data. We study classical sparse Bayesian learning, formulated as evidence maximization (type-II maximum likelihood), for underdetermined linear models with sensing matrices having independent and identically distributed Gaussian entries, Gaussian measurement noise, and an unknown deterministic signal sequence. Hyperparameter reoptimization induces a nonvanishing feedback term: a typical coordinate obeys a reoptimization-corrected scalar Gaussian law whose signal coefficient is governed by the normalized adaptive response rather than the frozen resolvent trace. A one-coordinate leave-one-out construction gives an exact conditional Gaussian law, which is transferred to a selected full stationary branch without assuming asymptotic closeness of the reduced and full stationary vectors. Combining this law with the Karush--Kuhn--Tucker conditions of the evidence objective yields a generally set-valued scalar relation and three branchwise large-system consistency relations. If the model noise variance is jointly estimated by evidence maximization, interior joint stationarity yields an exact finite-dimensional equality between the normalized residual energy and normalized resolvent trace. When the limiting signal law has nonzero mass at zero, this identity further yields a parameter-free asymptotic chi-square null law. Under an additional differentiability condition on the selected scalar branch, the large-system characterization also gives a closed relation for the reconstruction error of the posterior mean. The analysis is stationary-point based and permits multiple stationary branches.

0.32

SelectPFN: Amortized Bayesian Variable Selection for Sparse Nonlinear Regression with Prior-Data Fitted Networks

cs.LG stat.ML ·2026-10-15 ·Bin Luo
similarity 0.57
Abstract

Tabular foundation models based on prior-data fitted networks (PFNs) predict on a new data set in a single forward pass, but they cannot report which inputs their predictions depend on. We propose SelectPFN, a PFN that performs Bayesian variable selection and prediction jointly for sparse nonlinear regression. In one forward pass it returns posterior inclusion probabilities for every variable, and its predictions are computed from sampled subsets only, so excluded variables provably cannot affect them; we show this is exactly what the Bayesian model prescribes. The network is pretrained once on synthetic tasks from a meta-prior built around a group spike-and-slab sparse-input neural network. Column-permutation equivariance combined with random interleaving of original and knockoff columns yields knockoff statistics with exact finite-sample false discovery rate control, even when the meta-prior is wrong. We develop theory for amortized selection: a Bayes-regret bound for the amortized median probability model, a characterization showing that the information needed to detect a variable grows like $(2/λ)\log(1/ω)$ in the prior weight $ω$ of structures that can use it, where $λ\le1$ is an efficiency, and a negative result showing that average-case training does not transfer to frequentist guarantees at a fixed truth. On out-of-prior nonlinear designs with p up to 500, SelectPFN improves the area under the precision-recall curve by 0.23-0.28 over the lasso, BART, DART, LassoNet and a group-penalized sparse neural network, at a false discovery proportion of about 0.07 and 0.04 seconds per data set. The advantage persists on real covariate matrices, and, as the theory predicts, detection of interaction-only variables rises monotonically with their prior weight.

0.31

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.57
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

cs.IT math.PRcs.LGmath.CO ·2026-10-08 ·Thomas Weinberger
theory similarity 0.57
Abstract

For a known finite-dimensional model subspace, classical Gaussian regression theory guarantees that least squares eventually attains the parametric rate, with prediction error scaling as the subspace dimension divided by the sample size. Yet subspaces with the same number of unknown coefficients can require very different sample sizes to reach this regime. For subspaces of polynomials on the Boolean cube, a fundamental question is how restrictions on degree and ambient dimension jointly determine this threshold. Our main result sharply characterizes the worst-subspace minimax sample threshold over a substantial parameter range, revealing an exponential dependence on degree and precisely quantifying the joint effects of degree, ambient dimension, and subspace dimension. A small modification of our lower-bound construction reveals a strong separation: a single subspace can admit noiseless recovery with optimal sample complexity independent of degree, yet require essentially the worst-case sample size, exponential in degree, to attain the noisy parametric rate. To establish the sampling lower bound, we sharpen the Polyanskiy-Samorodnitsky uncertainty principle (J. Funct. Anal., '19) to uniformly optimal precision and extend its concentration guarantee to large subspaces in which every function concentrates most of its energy on one shared Hamming ball. The sampling upper bound follows from the sharp moment bound of Kirshner and Samorodnitsky (IEEE Trans. Inf. Theory, '21) combined with empirical-process bounds.

0.33