Computationally sufficient statistics for the Ising model

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. However, for numerous systems of interest that arise in physical contexts, expecting a full sample to be observed is not practical. We examine the trade-offs between the power of computation and observation within this scenario, employing the Ising model as a paradigmatic example. We demonstrate that it is computationally tractable to reconstruct the model parameters for a model with $l_1$ width $\gamma$ by observing statistics up to an order of $O(\gamma)$. This approach allows us to infer the model's structure and also learn it's couplings and magnetic fields. We also discuss settings where prior information about structure and homogeneity of the model is available.