*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
