Learning Ising Models from Evolutions
In this work, we revisit the problem of learning the structure and parameters of an Ising model from dynamics. While the problem of learning from i.i.d. samples has been intensively studied in several communities (Chow and Liu, 1968; Ravikumar et al., 2010; Bresler, 2015; Klivans and Meka, 2017; Vuffray et al., 2016), recent work has considered learning from temporally correlated samples arising from some stochastic process. However, all prior work (Bresler et al., 2018; Dutt et al., 2021; Gaitonde and Mossel, 2024; Gaitonde et al., 2025) studied this problem in the syn¬thetic observation model that assumes knowledge of internal steps of the standard algorithm for generating samples, which goes far beyond what we should expect to naturally observe from the system evolution in important physics and network applications. Extending these algorithmic guarantees to more realistic observation models has been an important direction highlighted in recent work (Bresler et al., 2018; Gaitonde et al., 2025). We give the first efficient algorithm for learning from the natural continuous-time observation model where we only observe the actual evolution of the state of the system, as opposed to usually unobservable details like failed update attempts of sites. For Ising models with maximum degree d, our algorithm first recovers the graph structure in poly(d) n2 log n time, which qualitatively matches the state-of-the-art even in the cleaner i.i.d. setting, and then estimates the parameters in additional Ȭ(2d n) time. Our analysis is based on a new family of cycle statistics, which crucially remains measurable for any stochastic process, and in fact succeeds more generally for a broad family of reversible, single-site Markov chains that includes both the Glauber dynamics and the Metropolis chain.1.
