Physically motivated stochastic dynamics are widely used to sample from high-dimensional distributions. However, such samplers often get trapped in metastable states, approximately sampling from a distribution that differs significantly from the desired stationary state. We rigorously show that for multivariable discrete distributions, the true stationary model can nevertheless be recovered from these metastable samples. This relies on a fundamental observation: for distributions satisfying a strong metastability condition, their single-variable conditional probabilities are on average extremely close to those of the true stationary distribution. This remains true even when the two distributions are far apart under global metrics such as Kullback-Leibler divergence. Consequently, we can effectively learn the true model using a conditional-likelihood estimator even when the samples are drawn from a restricted state space. Extending these general results to Ising models, we prove rigorous parameter and structure learning guarantees. Finally, we demonstrate this phenomenon numerically on higher-alphabet spin glass models.
We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold λmax(J)−λmin(J)=1, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.
Efficient sampling from Boltzmann distributions over discrete variables is a fundamental operation in a wide range of applications. While fast non-MCMC samplers have recently emerged as promising alternatives to conventional MCMC methods, their practical use for probabilistic learning remains hindered by the difficulty of estimating the effective temperature of the generated samples. In this work, we begin by introducing Langevin simulated bifurcation (LSB), a Boltzmann sampler that enables fast and parallel sampling with accuracy comparable to sequential MCMC methods. To address the challenge of unknown effective temperature, we propose conditional expectation matching (CEM), an efficient estimation method applicable to energy-based models (EBMs) with exploitable conditional independence structures. Building on these components, we further develop a learning framework, termed sampler adaptive learning (SAL), which adaptively adjusts the model temperature to match that of the distribution induced by fast non-MCMC sampling. We demonstrate the effectiveness of LSB, CEM, and SAL on semi-restricted Boltzmann machines (SRBMs), a class of EBMs that are difficult to train using conventional approaches. LSB achieves orders-of-magnitude acceleration over Gibbs sampling while maintaining comparable or higher accuracy, and CEM enables accurate temperature estimation of the resulting distribution with negligible computational overhead. As a consequence, SAL enables efficient training of SRBMs and outperforms conventional Boltzmann machine learning methods on synthetic spin-glass datasets. In addition, the trained models achieve strong performance across multiple tasks. These results establish LSB as a fast and accurate Boltzmann sampler and provide key insights that enable practical applications of fast non-MCMC sampling methods via efficient temperature estimation with CEM.
Rejection sampling is a technique for sampling from difficult distributions. However, its use is limited due to a high rejection rate. Common adaptive rejection sampling methods either work only for very specific distributions or without performance guarantees. In this paper, we present pliable rejection sampling (PRS), a new approach to rejection sampling, where we learn the sampling proposal using a kernel estimator. Since our method builds on rejection sampling, the samples obtained are with high probability i.i.d. and distributed according to f. Moreover, PRS comes with a guarantee on the number of accepted samples.
Akram Erraqabi, Michal Valko, Alexandra Carpentier +1