Structure learning and property testing in graphical models

The dependence structure of high-dimensional distributions is often modeled by graphical models. The problem of learning the graph underlying such distributions has received a lot of attention in statistics and machine learning. In problems of very high dimension, it is often too costly even to store the sample covariance matrix. We propose a model in which one can query single entries of the covariance matrix. We construct efficient algorithms for structure recovery in Gaussian graphical models with query complexity that is quasi-linear in the dimension. We present algorithms that work for trees and, more generally, for graphs of small treewidth. We also discuss hypothesis testing of properties of the underlying graph. The talk is based on joint work with Luc Devroye, Jakub Truszkowski, Vasiliki Velona, and Piotr Zwiernik.