Learning Ising Models from Evolutions (Extended Abstract)

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, recent work has considered learning from temporally correlated samples arising from some stochastic process. However, all prior work studied this problem in the {\em synthetic} 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, Gamarnik, Shah IEEE Trans. Inf. Theory 2018, Gaitonde, Moitra, Mossel STOC 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 $\mathsf{poly}(d)\cdot n^2\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 $\widetilde{O}(2^d\cdot n)$ time. Our analysis is based on a new family of cycle statistics, which crucially remains measurable for \emph{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.