2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
