TITLE:  Graphical models with missing data:  Practical estimators
and information-theoretic limits

SPEAKER:  Martin Wainwright

Given a black box that generates samples from a Markov random field
model, how to efficiently estimate the structure and parameters of the
underlying graph?  This model selection problem underlies many
applications of graphical models, and has attracted significant
attention in recent years.  New challenges are presented when the data
is only partially observed, missing at random, or corrupted with
noise.  In this talk, we present computationally efficient methods for
graphical model selection for such problems.  Interestingly, some of
them involve solving a non-convex program, but we nonetheless show
that a simple first-order gradient method converges to within
statistical error of the set of global optima.  We complement these
achievable results with information-theoretic lower bounds that are
matching up to constant factors.

Based on joint work with Po-Ling Loh.