Graphical Model Selection: Polynomial-time Schemes

Event Details
  • Date/Time:
    • Thursday January 29, 2009
      10:00 am - 11:00 am
  • Location: Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Nicoleta Serban
ISyE
Contact Nicoleta Serban
404-385-7255
Summaries

Summary Sentence: Graphical Model Selection

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

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.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
Graphical model
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 4:36pm
  • Last Updated: Oct 7, 2016 - 9:47pm