Date:
Location:
The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, information theory, computer science, and other related fields. The upcoming seminar takes place on Friday, November 3, from 10:30-11:30am EST. This week's speaker is Marco Mondelli from IST Austria. To attend the seminar, please use the following Zoom link: https://harvard.zoom.us/j/5238360756
Title: From Spectral Estimators to Approximate Message Passing… And Back
Abstract:
In a generalized linear model (GLM), the goal is to estimate a d-dimensional signal x from an n-dimensional observation of the form f(Ax, w), where A is a design matrix and w is a noise vector. Well-known examples of GLMs include linear regression, phase retrieval, 1-bit compressed sensing, and logistic regression. We focus on the high-dimensional setting in which both the number of measurements n and the signal dimension d diverge, with their ratio tending to a fixed constant. Spectral methods provide a popular solution to obtain an initial estimate, and they are also commonly used as a ‘warm start’ for other algorithms. In particular, the spectral estimator is the principal eigenvector of a data-dependent matrix, whose spectrum exhibits a phase transition.
In the talk, I will start by discussing the emergence of this phase transition and provide precise asymptotics on spectral methods for an i.i.d. Gaussian design A. Next, I will combine spectral methods with Approximate Message Passing (AMP) algorithms, thus solving a key problem related to their initialization. Finally, I will consider two instances of GLMs that capture the heterogeneous and structured nature of practical data models: (i) a mixed GLM with multiple signals to recover, and (ii) a GLM with a correlated design matrix. To study spectral estimators in these challenging settings, the plan is to go back to Approximate Message Passing: I will demonstrate that the AMP framework not only gives Bayes-optimal algorithms, but it also unveils phase transitions in the spectrum of random matrices, thus leading to a precise asymptotic characterization of spectral estimators.
Based on a series of joint works with Hong Chang Ji, Andrea Montanari, Ramji Venkataramanan, and Yihan Zhang.
Speaker Biography:
Marco Mondelli received the B.S. and M.S. degree in Telecommunications Engineering from the University of Pisa, Italy, in 2010 and 2012, respectively. In 2016, he obtained his Ph.D. degree in Computer and Communication Sciences at the École Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He is currently an Assistant Professor at the Institute of Science and Technology Austria (ISTA). Prior to that, he was a Postdoctoral Scholar in the Department of Electrical Engineering at Stanford University, USA, from February 2017 to August 2019. He was also a Research Fellow with the Simons Institute for the Theory of Computing, UC Berkeley, USA, for the program on Foundations of Data Science from August to December 2018. His research interests include data science, machine learning, information theory, and modern coding theory. He was the recipient of a number of fellowships and awards, including the Jack K. Wolf ISIT Student Paper Award in 2015, the STOC Best Paper Award in 2016, the EPFL Doctorate Award in 2018, the Simons-Berkeley Research Fellowship in 2018, the Lopez-Loreta Prize in 2019, and Information Theory Society Best Paper Award in 2021.