Estimating Properties of Dynamic Graphical Models

We study the problem of estimating properties of dynamic graphical models in the non-asymptotic regime. Instead of characterizing the behavior of estimation rules with asymptotic consistency, we study sharp bounds on the sample size required to estimate the properties. We show that for certain spatio-temporal Markov random fields governed by an underlying graph, one can estimate certain natural properties with logarithmic (w.r.t. the size of the underlying graph) sample complexity. Matching lower bounds are also established for such estimation problems. We highlight our results with a 'bit river' abstraction, where a Bernoulli source at one node flows along the edges of an underlying graph, and the task is to obtain the flow trajectory. If we do not have any restriction on the model class under consideration, we also show that an exponential sample size is required for even very simple properties.