LTH-image

Learning graphical models: hardness and tractability

Devavrat Shah, Massachusetts Institute of Technology, USA

Abstract:

Abstract: Our understanding of the question of learning graphical model, despite it's fundamental importance, has been far from satisfactory. In this talk, I will discuss recent progresses we have made towards improving this status quo. Specifically, we will discuss the reasons for learning graphical model being hard, both computationally and statistically. We shall also discuss, somewhat surprising, conditions under which it becomes tractable. Time permitting, we shall discuss a variant of the `standard' graphical model learning problem from literature that might be more relevant to practice. 
 
This talk describes joint work with Guy Bresler and David Gamarnik, both at MIT.
Presentation slides

Biography:

Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC). His research focus is on theory of large complex networks which includes network algorithms, stochastic networks, network information theory and large scale statistical inference.

Devavrat Shah received his Bachelor of Technology in Computer Science and Engineering from Indian Institute of Technology, Bombay in 1999 with the Presidents of India Gold Medal – awarded to the best graduating student across all engineering disciplines. He received his PhD in Computer Science from Stanford University in 2004. His doctoral thesis titled “Randomization and Heavy Traffic Theory: New Approaches for Switch Scheduling Algorithms” was completed under supervision of Balaji Prabhakar. His thesis was adjudged winnder of George B. Dantzig best dissertation award from INFORMS in 2005. After spending a year between Stanford, Berkeley and MSRI, he started teaching at MIT in Fall 2005.

Devavrat Shah has been co-awarded best paper awards at the IEEE INFOCOM ’04, ACM SIGMETRICS/Performance ’06; and he has supervised best student paper awards at Neural Information Processing Systems ’08, ACM SIGMETRICS/Performance ’09 and Management Science and Operations Management Paper competition ’10.

He was awarded the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms. He received the 2010 Erlang Prize from INFORMS which is given to a young researcher for outstanding contributions to applied probability. He is currently an associate editor of Operations Research.