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

Technical Summary: A Computational Phase Transition for Learning-to-Sample from Ising Models

Problem Statement
This paper investigates the algorithmic task of "learning-to-sample," a foundational abstraction underlying modern generative modeling. The goal is to design an efficient procedure that, given $k$ i.i.d. samples from an unknown target distribution $\nu$, generates new samples that follow approximately the same law. The authors focus on Ising models, a standard testbed in theoretical computer science and machine learning.

A central question addressed is whether access to training samples, combined with explicit access to the model parameters, can circumvent computational barriers that exist when only parameters are known. While parameter learning (estimating model parameters from data) and density estimation are distinct tasks, learning-to-sample requires generating fresh samples. The paper specifically targets the regime near the "spectral threshold" defined by $\lambda_{\max}(J) - \lambda_{\min}(J) = 1$, where $J$ is the interaction matrix. Prior work established that sampling is tractable below this threshold, but the computational complexity of learning-to-sample in the near-critical regime remained open.

Methodology
The authors construct a family of bounded-width Ising models that are computationally hard to learn-to-sample, even when the learner is provided with both the model parameters and polynomially many training samples. The proof relies on a reduction from the security of digital signature schemes, specifically under the Computational Diffie-Hellman (CDH) assumption.

The construction proceeds in two main stages:

1. Embedding Signature Verification into Ising Models:
   The authors adapt the technique of embedding circuits into Ising models (following Moitra et al. and Bogdanov et al.). They construct an Ising model $\mu_{pk}$ for a fixed public key $pk$ such that its high-probability configurations encode valid message-signature pairs $(msg, \sigma)$ for a signature scheme with deterministic verification.

   • The verification algorithm of the signature scheme is encoded as a circuit.
   • The Ising model is designed such that sampling from it corresponds to generating valid message-signature pairs.
   • By the security definition of signature schemes (existential unforgeability under chosen-message attacks), no efficient algorithm can generate a valid signature for a new message after seeing signatures for a set of queried messages. This implies that any efficient learner for these Ising models must either "memorize" the training data (outputting pairs for queried messages) or "hallucinate" (outputting invalid pairs).

2. Phase-Gadget Construction (Near-Critical Embedding):
   The initial construction yields potentially dense Ising models with arbitrary interaction strengths. To address the spectral threshold, the authors introduce a "phase-gadget" construction.

   • Each vertex of the original Ising model is replaced by a gadget graph consisting of a "core" set of spins ($R_v$) and "interface" sets ($S_v$) connected to neighbors.
   • The gadget is designed to have two dominant phases (majority spins $+1$ or $-1$) that simulate the effective spin of the original vertex.
   • By carefully tuning the gadget parameters (sizes of sets and edge weights), the authors ensure the resulting Ising model $\tilde{\mu}$ has a bounded interaction width ($O(1)$) and its spectral width $\lambda_{\max}(\tilde{J}) - \lambda_{\min}(\tilde{J})$ lies arbitrarily close to 1 (specifically, $1 < \lambda_{\max} - \lambda_{\min} \le \gamma$ for any constant $\gamma > 1$).
   • Crucially, this transformation preserves the hardness of the "learning-to-generalize" problem. The authors prove that if an efficient learner could sample from $\tilde{\mu}$ without memorizing or hallucinating, one could construct an efficient algorithm to sample from the original hard instance $\mu$, thereby breaking the signature scheme.

Key Contributions and Results

• Hardness Near the Spectral Threshold: Under the standard CDH assumption, the authors construct a family of Ising models with bounded width and spectral width $1 < \lambda_{\max}(J) - \lambda_{\min}(J) \le \gamma$ (for any $\gamma > 1$) for which learning-to-sample is computationally hard. This holds even when the learner is given the explicit parameters $(J, h)$ and polynomially many i.i.d. samples.
• Separation from Parameter Learning: The constructed hard instances lie in a regime where parameter learning is known to be efficient (based on results by Klivans and Meka, Wu et al., and Vuffray et al.). This establishes a separation: parameter learning is easy, but learning-to-sample is hard.
• Memorization-Hallucination Dichotomy: The paper formalizes a dichotomy for any efficient learner on these hard instances. Any such learner must either:
  1. Memorize: Output configurations that, after a simple transformation, match the training data.
  2. Hallucinate: Place substantial probability mass on configurations that have negligible probability under the target distribution (the "hallucination set").
     This result rules out the existence of an efficient algorithm that can reliably learn-to-sample or perform sample amplification for these distributions.
• Sharp Phase Transition: Combined with recent tractability results for learning-to-sample below the spectral threshold (Anari et al., Koehler et al.), this work establishes a sharp computational phase transition at the spectral threshold for the learning-to-sample task.

Significance
The paper claims that its results provide a fundamental understanding of the limitations of generative modeling. By demonstrating that learning-to-sample can be strictly harder than parameter learning, even in regimes where the model parameters are known and learning is theoretically possible, the work challenges the intuition that access to data and parameters guarantees efficient generation.

The formalization of the memorization-hallucination tradeoff offers a theoretical lens for empirical phenomena observed in generative models, suggesting that for certain distributions, a generator cannot generalize to new data without either overfitting (memorization) or producing unrealistic outputs (hallucination). The results are framed as a cryptographic separation, relying on standard assumptions (CDH) rather than unproven complexity conjectures, thereby grounding the hardness of learning-to-sample in well-studied cryptographic primitives.

The authors note that while they prove hardness for any fixed $\gamma > 1$, the behavior at the exact threshold $\gamma = 1 + o(1)$ remains an open question. Additionally, they leave open whether other distribution families exhibit similar phase transitions or if the thresholds for sampling and learning-to-sample can differ in other contexts.