DeLTA seminar by Gábor Lugosi
Gábor Lugosi, Pompeu Fabra University
Learning the structure of graphical models by covariance queries
The dependence structure of high-dimensional distributions is oftenmodeled by graphical models. The problem of learning the graphunderlying such distributions has received a lot of attention instatistics and machine learning. In problems of very high dimension,it is often too costly even to store the sample covariance matrix. Wepropose a new model in which one can query single entries of thecovariance matrix. We construct computationally efficient algorithmsfor structure recovery in Gaussian graphical models with computationalcomplexity that is quasi-linear in the dimension. We presentalgorithms that work for trees and, more generally, for graphs ofsmall treewidth. The talk is based on joint work with JakubTruszkowski, Vasiliki Velona, and Piotr Zwiernik.
DeLTA is a research group affiliated with the Department of Computer Science at the University of Copenhagen studying diverse aspects of Machine Learning Theory and its applications, including, but not limited to Reinforcement Learning, Online Learning and Bandits, PAC-Bayesian analysis