A computational phase transition for learning-to-sample from Ising models

Time: 9:30, Tuesday, July 14, 2026

Venue: Room 301,  A5 Building

Abstract: In this talk, we give study \emph{learning-to-sample} -- the 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.  While this task is related to classical problems such as parameter learning and sampling given the model parameters, it is fundamentally distinct from both. We show that for Ising models, learning- to-sample undergoes a computational phase transition at the spectral threshold   \lambda_{\max}(J)-\lambda_{\min}(J)=1  where Jis the interaction matrix. Specifically, we show that Ising models with  \lambda_{\max}(J)-\lambda_{\min}(J)<1,  admit a simple and efficient learning-to-sample algorithm: we run the classical Glauber dynamics initialized from the empirical distribution, using transition probabilities learned from the provided samples.  In contrast, we show that when   \lambda_{\max}(J)-\lambda_{\min}(J)>1, learning-to-sample is cryptographically hard. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold \lambda_{\max}(J)-\lambda_{\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.Together 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.

Based on joint works with Frederic Koehler, Holden Lee and Andrej Risteski.