arXiv:2605.24752cs.LGcs.CC2026-05

发现伊辛模型学习采样存在计算相变,阈值由谱间隙决定。

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

  • 基于谱间隙界定学习采样的难易边界,构造了硬实例。
  • 在参数已知且样本充足时仍难以高效采样,证明计算困难性。
  • 揭示学习器必出现记忆或幻觉的二元行为,适用于理论研究者。

我们研究伊辛模型中的学习采样任务,该任务是生成建模的基础。给定来自未知目标分布的独立同分布样本,目标是学习一个计算高效的生成过程,以产生近似相同分布的新样本。我们构造了一类常数宽度的伊辛模型,其谱间隙满足λ_max(J)−λ_min(J)=1,处于谱阈值之外,证明在此类模型上学习采样在标准密码学假设下是计算困难的,即使学习者拥有多项式数量的独立同分布样本并能直接访问模型参数。结合[AJKPV24,KLV25]在谱阈值以下的可解性结果,这确立了谱阈值处的尖锐计算相变。此外,结合[KM17,WSD19,VML20]中关于有限宽度伊辛模型参数学习的结果,表明学习采样可能比参数学习更难。最后,我们证明任何高效学习器在这些困难实例上必然表现出自然的记忆-幻觉二分:学习器要么输出经简单变换后与训练数据匹配的配置,要么在目标分布概率极低的配置上分配显著质量。

原文摘要 · Abstract (English)

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.

生成模型伊辛模型计算复杂性相变

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。