Learning Gibbs distributions using only sufficient statistics has long been recognized as a computationally hard problem. On the other hand, computationally efficient algorithms for learning Gibbs distributions rely on access to full sample configurations generated from the model. For many systems of interest that arise in physical contexts, expecting a full sample to be observed is not practical, and hence it is important to look for computationally efficient methods that solve the learning problem with access to only a limited set of statistics. We examine the trade-offs between the power of computation and observation within this scenario, employing the Ising model as a paradigmatic example. We show that the couplings of the model can be learned to a desired accuracy from statistics whose order grows linearly with the ℓ1 width of the model and only logarithmically with the inverse of the accuracy. In particular, for a fixed accuracy, the required order is proportional to the width. This allows us to infer the model's structure, using statistics whose order grows logarithmically with the inverse of the weakest coupling, and also to learn its magnetic fields. When the width and the accuracy are fixed, the running time is polynomial in the number of variables. We also discuss a setting where prior information about structure of the model is available and show that the learning problem can be solved efficiently with even more limited observational power.
Figures & tables
(i)
Replace e−Eu(σ,θu(t)) in the exact gradient by the degree- d approximation as in ( 6 ).
(ii)
Expand the resulting moments using ( 7 ).
(iii)
Substitute each monomial expectation E[∏i∈Kσi] by the table entry S[K] .
Algorithm 1 Interaction Screening with Moment-Based Approximate Gradients
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
(i)
Replace the exponential in the exact gradient by a degree- d approximation as in ( 47 ).
(ii)
Expand the resulting moments using ( 48 ).
(iii)
Substitute each monomial expectation E[∏i∈Kσi] by the table entry S[K] .
Appendix
Algorithm 2 Magnetic Field Learning with Moment-Based Approximate Gradients
Figure 1: Smallest degree d of the Taylor approximation for which Algorithm 1 , run on the exact moment table of order d+2−(dmod2) , learns all couplings of the long-range chain to error 0.02 ( p=12 ). The dashed line is the degree prescribed by Theorem 1 .
Figure 2: Coupling error of Algorithm 1 on empirical moment tables built from a shared dataset of n samples, for the long-range chain with γ=1 ( p=12 ), compared with Interaction Screening on the full samples. The curves for d=6 and for full samples coincide. Medians over 10 datasets; error bars show the interquartile range.
We study 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.
Andrej Risteski, Thuy-Duong Vuong
Machine Learning Department, Carnegie Mellon University. · Department of Computer Science and Engineering, UC San Diego.
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.
Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra +1
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA
Neural networks are increasingly used to infer hidden physical structure from dynamical observations, yet it remains unclear whether their out-of-distribution performance reflects transferable physical rule learning. We address this question in a controlled inverse problem: reconstructing interaction graphs of a kinetic Ising model from Glauber magnetization trajectories. Across convolutional, graph, Transformer, and hybrid architectures, we find that data-driven training produces distinct and reproducible statistical strategies under topology and temperature shifts. Edge-population diagnostics reveal that Transformer-based models tend to preserve the link density of the training ensemble, whereas convolutional models can collapse toward sparse- or no-link predictions that appear out-of-distribution stable by exploiting the majority no-link class. Thus, high in-distribution accuracy and apparent out-of-distribution robustness do not necessarily imply a learned dynamics-to-structure rule. Instead, neural reconstruction can be governed by architecture-dependent statistical priors. Our results identify a concrete failure mode of standard data-driven learning in physical inverse problems and motivate rule-guided principles for machine-learning-assisted scientific discovery.
Yuan-Bin Zhu, Shuang Qiao, Shi-Ju Ran
Center for Quantum Physics and Intelligent Sciences, Department of Physics, Capital Normal University, Beijing 10048, China