Dynamics of Randomized Row-Action Methods for High-Dimensional Estimation

Jan 27

Wednesday, January 27, 2016

3:30 pm - 4:30 pm


Yue M. Lu John A. Paulson School of Engineering and Applied Sciences Harvard University

We consider efficient row-action methods for solving estimation problems widely encountered in signal processing, machine learning, and big data analytics. A flurry of current work has been focusing on establishing theoretical performance bounds for these methods. This intense interest is spurred by their remarkably impressive empirical performance as well as their linear complexity, the latter of which makes them well-adapted to the computational challenges faced in higher-dimensional settings. In this talk, I will present an exact analysis of a large class of online row-action methods for high-dimensional estimation. In the large systems limit, the dynamics of these algorithms converge to trajectories governed by a set of deterministic, coupled ODEs. Combined with suitable spectral initialization, our analysis establishes the theoretical performance guarantee of these methods for solving both convex and nonconvex estimation problems in high dimensions. Our ODE prediction agrees with simulation results, which also indicate that previous performance bounds in the literature can often be several orders of magnitude too high. Finally, I will outline a few more results and topics of current research in my group. Informal Luncheon chat with grad students/postdocs: 12noon, 330 Gross Hall