Message Passing Algorithms, Random Convex Problems and the Risk of Lasso

Andrea Montanari
Standord University

Monday, November 8, 2010 at 12:30PM
54-134 Engineering IV Building
Refreshments Served

Abstract: One of the key factors enabling modern large-scale statistical inference is the use of low complexity algorithms that scale to problems with millions of variables. I will survey recent progress towards the construction and analysis of low complexity algorithms. In particular, I will explain a circle of ideas based on connections with the theory of graphical models, message passing algorithms and statistical mechanics.

The analysis of these algorithms allows to prove remarkably sharp results on the asymptotic behavior of some families of random convex problems. As a specific example, I will discuss the mean square error for LASSO estimation in the context of compressed sensing problems. [Based on joint work with David L. Donoho and Arian Maleki, and with Mohsen Bayati and Jose Bento.]

Biography: Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Thorique de l'Ecole Normale Suprieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Charg de Recherche (with Centre National de la Recherche Scientifique, CNRS) at LPTENS. In September 2006 he joined Stanford University as a faculty, and since 2010 he is Associate Professor in the Departments of Electrical Engineering and Statistics. He was co-awarded the ACM SIGMETRICS best paper award in 2008. He received the CNRS bronze medal for theoretical physics in 2006 and the National Science Foundation CAREER award in 2008.