November 10, 2017, Yue Lu, Harvard University

Friday, November 10, 2017, 3pm-4pm
8 St. Mary’s Street, PHO 211
Refreshments at 2:45pm

Yue Lu
Harvard University

The Scaling Limit of Iterative Algorithms for High-Dimensional Inference

This talk presents our work on analyzing the exact transient dynamics of iterative algorithms for solving various signal estimation and inference problems. We will focus on two prototypical examples: linear regression with general (convex or nonconvex) regularizers and sparse principal component analysis. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measure of the target vector and the estimates provided by the algorithm will converge weakly to a deterministic measured-valued process that can be characterized as the unique solution of a nonlinear PDE. Numerical solutions of this PDE, which involves two spatial variables and one time variable, can be efficiently obtained. These solutions provide detailed information about the performance of the algorithms, as many practical performance metrics are functionals of the joint empirical measures. Although our analysis is asymptotic in nature, numerical simulations show that the theoretical predictions are accurate for moderate signal dimensions. In addition to providing a tool for analyzing algorithms, our asymptotic results also offer useful insights. In particular, in the high-dimensional limit, the original coupled dynamics associated with the algorithm will be asymptotically “decoupled”, with each coordinate independently solving a 1-D effective minimization problem via stochastic gradient descent. Exploiting this insight to design new algorithms for achieving optimal trade-offs between computational and statistical efficiency may prove an interesting line of research. Joint work with Chuang Wang (Harvard University) and Jonathan Mattingly (Duke University). 

Yue M. Lu was born in Shanghai. After finishing undergraduate studies at Shanghai Jiao Tong University, he attended the University of Illinois at Urbana-Champaign, where he received the M.Sc. degree in mathematics and the Ph.D. degree in electrical engineering, both in 2007. From September 2007 and October 2010, he was a postdoctoral researcher at the Audiovisual Communications Laboratory at Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He then joined Harvard University, where he is currently an Associate Professor of Electrical Engineering at the John A. Paulson School of Engineering and Applied Sciences.

He received the Most Innovative Paper Award of IEEE International Conference on Image Processing (ICIP) in 2006 for his paper (with Minh N. Do) on the construction of directional multiresolution image representations, the Best Student Paper Award of IEEE ICIP in 2007, and the Best Student Presentation Award at the 31st SIAM SEAS Conference in 2007. Student papers supervised and coauthored by him won the Best Student Paper Award (with Ivan Dokmanic and Martin Vetterli) of IEEE International Conference on Acoustics, Speech and Signal Processing in 2011 and the Best Student Paper Award (with Ameya Agaskar and Chuang Wang) of IEEE Global Conference on Signal and Information Processing (GlobalSIP) in 2014. He is a recipient of the 2015 ECE Illinois Young Alumni Achievement Award. He has been an Associate Editor of the IEEE Transactions on Image Processing since December 2014, an Elected Member of the IEEE Image, Video, and Multidimensional Signal Processing Technical Committee since January 2015, and an Elected Member of the IEEE Signal Processing Theory and Methods Technical Committee since January 2016.

Faculty Host: Vivek Goyal
Student Host: Tingting Xu