Home
Speakers
Schedule
Location and Directions
Hotel Information
Martin Wainwright
University of California at Berkeley
Title: Graphical Model Selection in High-Dimensions: Trade-offs between Computational and Statistical Efficiency
Abstract: Graphical models provide a framework for capturing statistical dependencies among large collections of random variables, and are used in many fields (signal processing, communication, control, statistical physics, statistical learning). The problem of graphical model selection is to estimate the edge structure of the graph based on a set of samples from the unknown model. Exact solution is computationally intractable in general, due to the exponential number of possible graphs.
We analyze this problem under high-dimensional scaling, in which the graph size p, maximum degree d and sample size n are all allowed to scale. For discrete graphical models over binary variables, we discuss a polynomial-time algorithm based on logistic regression, and show that it can reliably recover the graph structure with n = &Omega(d^3 log p) samples. We also analyze the information-theoretic limits of the problem, and prove that no method can succeed with fewer than $n = O(d \log p)$ samples. We conclude by discussing various open problems and directions in the area.