Abstract
We consider the problem of learning graphical models, also known as Markovrandom fields (MRFs) from temporally correlated samples. As in many traditionalstatistical settings, fundamental results in the area all assume independentsamples from the distribution. However, these samples generally will notdirectly correspond to more realistic observations from nature, which insteadevolve according to some stochastic process. From the computational lens, evengenerating a single sample from the true MRF distribution is intractable unless$\mathsf{NP}=\mathsf{RP}$, and moreover, any algorithm to learn from i.i.d.samples requires prohibitive runtime due to hardness reductions to the paritywith noise problem. These computational barriers for sampling and learning fromthe i.i.d. setting severely lessen the utility of these breakthrough resultsfor this important task; however, dropping this assumption typically onlyintroduces further algorithmic and statistical complexities. In this work, we surprisingly demonstrate that the direct trajectory datafrom a natural evolution of the MRF overcomes the fundamental computationallower bounds to efficient learning. In particular, we show that given atrajectory with $\widetilde{O}_k(n)$ site updates of an order $k$ MRF from theGlauber dynamics, a well-studied, natural stochastic process on graphicalmodels, there is an algorithm that recovers the graph and the parameters in$\widetilde{O}_k(n^2)$ time. By contrast, all prior algorithms for learningorder $k$ MRFs inherently suffer from $n^{\Theta(k)}$ runtime even in sparseinstances due to the reductions to sparse parity with noise. Our results thussurprisingly show that this more realistic, but intuitively less tractable,model for MRFs actually leads to efficiency far beyond what is known andbelieved to be true in the traditional i.i.d. case.