Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics

The usual setting for learning the structure and parameters of a graphical\nmodel assumes the availability of independent samples produced from the\ncorresponding multivariate probability distribution. However, for many models\nthe mixing time of the respective Markov chain can be very large and i.i.d.\nsamples may not be obtained. We study the problem of reconstructing binary\ngraphical models from correlated samples produced by a dynamical process, which\nis natural in many applications. We analyze the sample complexity of two\nestimators that are based on the interaction screening objective and the\nconditional likelihood loss. We observe that for samples coming from a\ndynamical process far from equilibrium, the sample complexity reduces\nexponentially compared to a dynamical process that mixes quickly.\n