TITLE: Graphical model selection in high dimensions: Polynomial-time schemes and information-theoretic limits

SPEAKER: Professor Martin Wainwright

ABSTRACT:

Undirected graphical models or Markov random fields (MRF) provide a framework for capturing statistical dependencies among large collections of random variables, and are used in many application domains (e.g., spatial statistics, statistical image analysis, social network analysis). The problem of graphical model selection is to recover the edge structure of the graph based on a set of samples from the unknown model. In general, it is a challenging problem due to the exponential explosion in the number of possible graphs.

We analyze different methods for graphical model selection 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 present a polynomial-time algorithm based on $ell_1$-regularized logistic regression, and show that under mild conditions, it can reliably recover the graph structure with $n = Omega(d3 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.

Based on joint work with John Lafferty, Pradeep Ravikumar, and Prasad Santhanam.