Technical Program

Paper Detail

 Paper ID G.1.2 Paper Title Minimax Prediction in Tree Ising Models Authors Guy Bresler, MIT, United States; Mina Karzand, University of Wisconsin-Madison, United States Session G.1: Graph Analytics Presentation Lecture Track Graphs, Games, Sparsity, and Signal Processing Manuscript Click here to download the manuscript Virtual Presentation Click here to watch in the Virtual Symposium Abstract Graphical models are often used to facilitate efficient computation of posteriors in order to make predictions. With this objective in mind, we consider the problem of estimating the parameters of a graphical model with known structure from samples such that posteriors computed using the model are accurate. Focusing on tree-structured binary Markov random fields, our main result is a sharp characterization of the dependence on number of samples needed for all pairwise marginals (and hence posteriors of one variable given another) to be accurate: $n= \Theta(\eta^{-2}\log p)$ samples are necessary and sufficient to estimate model parameters such that all marginals of arbitrary order $k$ are accurate to within $\sqrt{k}\,\eta$. The result implies that prediction error is bounded uniformly, with no dependence on the strength of interactions. We will also show that these guarantees are achievable using moment matching techniques.