Rigorous Systems Research Group (RSRG) Seminar

Friday October 14, 2011 4:00 PM

High Dimensional Graphical Model Selection: Tractable Graph Families and Parameter Regimes

Speaker: Animashree Anandkumar, Electrical Engineering and Computer Science, UC Irvine
Location: Annenberg 213
Capturing complex interactions among a large set of variables is a challenging task. Probabilistic graphical models or Markov random fields provide a graph-based framework for capturing such dependencies. Graph estimation is an important task, since it reveals important relationships among the variables. I will present a unified view of graph estimation and propose a simple local algorithm for graph estimation using only low-order statistics of the data. We establish that the algorithm has consistent graph estimation with low sample complexity for a class of graphical models satisfying certain structural and parameter criteria. We explicitly characterize these model classes and point out interesting relationships between the graph structure and the parameter regimes, required for tractable learning. Many graph families such as the classical Erdos-Renyi random graphs, random regular graphs, and the small-world graphs can be learnt efficiently under our framework.
Series Rigorous Systems Research Group (RSRG) Seminar Series

Contact: Sydney Garstang at x4555 sydney@caltech.edu