Timezone: »

 
Oral
High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Animashree Anandkumar · Vincent Tan · Alan S Willsky

Wed Dec 14 01:20 AM -- 01:40 AM (PST) @
in Oral Session 6 »

We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as conditional mutual information test. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n= Omega(J{min}^{-4} log p), where p is the number of nodes and J{min} is the minimum edge potential. We also prove novel non-asymptotic necessary conditions for graphical model selection.

Author Information

Animashree Anandkumar (NVIDIA / Caltech)
Vincent Tan (University of Wisconsin-Madison)
Alan S Willsky (Massachusetts Institute of Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors