Technical Program

Paper Detail

Paper IDG.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

Visit Website!