[Theory] 1/8 Talks at TTIC: Frederic Koehler, MIT

[Mary Marre]

*When:*      Friday, January 8th at 11:10 am CT



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_3DqSDK9uT9qD71bj-g0LUw>*)



*Who: *       Frederic Koehler, MIT


*Title:       *Learning Some Ill-Conditioned Gaussian Graphical Models

*Abstract: *Gaussian Graphical models have wide-ranging applications in
machine learning and the natural and social sciences where they are one of
the most popular ways to model statistical relationships between observed
variables. In most of the settings in which they are applied, the number of
observed samples is much smaller than the dimension and the goal is to
learn the model assuming the underlying model is sparse. While there are a
variety of algorithms (e.g. Graphical Lasso, CLIME) that provably recover
the graph structure with a logarithmic number of samples, they all require
that the precision matrix is in some way well-conditioned. Here we give the
first fixed polynomial-time algorithms for learning attractive GGMs and
walk-summable GGMs with a logarithmic number of samples and without any
such assumptions. In particular, our algorithms can tolerate strong
dependencies among the variables. We complement our results with
experiments showing that many existing algorithms fail even in some simple
settings where there are long dependency chains. Joint work with Jon
Kelner, Raghu Meka, and Ankur Moitra.

*Host: *Madhur Tulsiani <madhurt at ttic.edu>



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210101/bd5a9e5b/attachment.html>