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

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

by Thuy-Duong (June) Vuong

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning
🎙 Thuy-Duong (June) Vuong 👥 75K 📅 August 8, 2026 ⏱ 43 min 👁 380 📄 original study 🧭 2026-08-09
Available in: English (current) Français

Keywords

learning-to-sampleIsing modelphase transitionGlauber dynamicscryptographic hardness

Summary

The talk presents a rigorous study of the learning-to-sample problem for Ising models, a canonical family of energy-based models. The speaker defines learning-to-sample as the task of producing a sampler that, given i.i.d. samples from an unknown distribution, outputs new samples close in total variation distance. She also introduces a weaker notion, learning-to-generalize, which formalizes avoiding memorization and hallucination. The main result is a computational phase transition at the spectral threshold λ_max(J)-λ_min(J)=1. For models below this threshold, a simple algorithm based on Glauber dynamics with learned transition probabilities is efficient. For models above the threshold, the problem is cryptographically hard, even when the learner has access to the model parameters. The hardness holds for a family of bounded-width Ising models, under standard cryptographic assumptions. This shows that learning-to-sample can be harder than parameter learning. The talk also discusses the relationship between learning-to-generalize and learning-to-sample, and outlines the proof techniques, including a reduction from a cryptographic problem and the use of the Kesten-Stigum threshold. The presentation is technical and aimed at a specialized audience in theoretical computer science and machine learning.

180 words

Critical Evaluation

The talk presents a significant contribution to the theoretical understanding of generative modeling, specifically the learning-to-sample problem for Ising models. The speaker clearly defines the problem and introduces a useful weaker notion, learning-to-generalize, which captures the practical concerns of memorization and hallucination. The main result is a sharp computational phase transition at the spectral threshold, which is both surprising and insightful. The proof sketch is well-structured, and the speaker takes care to explain the intuition behind the technical steps. The use of cryptographic assumptions to establish hardness is standard in computational complexity, but it means the hardness result is conditional. The talk is rigorous and well-presented, with appropriate attention to definitions and formal statements. The speaker also addresses questions from the audience, clarifying subtle points. The sources cited are relevant and include prior work on parameter learning for Ising models. The talk is part of a workshop on diffusion generative modeling, and it provides a theoretical foundation that complements more applied work. The main limitation is that the talk focuses on a specific family of distributions, and the practical implications for real-world generative models are not directly addressed. However, the results are valuable for guiding the design of algorithms and understanding the fundamental limits of learning-to-sample. Overall, this is a high-quality theoretical contribution.

213 words

Title / Content Match

The title accurately reflects the content: the talk presents a computational phase transition for learning-to-sample from Ising models, with a sharp threshold at the spectral gap.

Quality & Reliability

8/10

Presentation of original research with rigorous theoretical results, including formal definitions, proofs sketches, and connections to prior work. The speaker is a researcher at UC San Diego, and the talk is hosted by the Simons Institute, a reputable venue. The results are based on two joint works with established researchers. The presentation is clear and technically detailed, but the lack of full proofs and the reliance on cryptographic assumptions limit the immediate verifiability.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

The talk provides a novel computational phase transition for learning-to-sample from Ising models, identifying a sharp threshold at the spectral gap. This is a fundamental contribution to the theory of generative modeling, as it delineates the boundary between tractable and intractable regimes. The introduction of the learning-to-generalize notion offers a new perspective on the practical goals of generative models, focusing on avoiding memorization and hallucination. The hardness result, based on cryptographic assumptions, establishes that learning-to-sample can be strictly harder than parameter learning, which is a surprising and important finding.

Pour aller plus loin :

  • Ising model — The Ising model is a canonical example of an energy-based model and Markov random field, central to the talk.
  • Glauber dynamics — The algorithm used in the easy regime; a Markov chain Monte Carlo method for sampling from Ising models.
  • Kesten-Stigum threshold — A related threshold in the context of reconstruction on trees, which may be relevant to the hardness construction.

158 words

Radar Profile

The radar profile shows high scores in quality of information, technical level, and reliability, with a slightly lower score for quantity of information, reflecting the focused and deep nature of the talk. The overall profile indicates a technically rigorous and reliable presentation.

Reliability 8/10