All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD1-S6-T3.2
Paper Title Estimating Properties of Dynamic Graphical Models
Authors Changlong Wu, Narayana Santhanam, University of Hawaii at Manoa, United States
Session D1-S6-T3: Inference in Graphical Models
Chaired Session: Monday, 12 July, 23:40 - 00:00
Engagement Session: Tuesday, 13 July, 00:00 - 00:20
Abstract 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.