The Statistics Seminar Speaker for October 21 is Yudong Chen, an assistant professor in the School of Operations Research and Information Engineering (ORIE) at Cornell University. His research interests include machine learning, high-dimensional and robust statistics, and convex optimization. Dr. Chen obtained a Ph.D. in Electrical and Computer Engineering in 2013 from The University of Texas at Austin. From 2013 to 2015 he was a postdoc in the EECS department at the University of California, Berkeley, and in 2014 was an academic visitor at the National University of Singapore. He received a B.S. and M.S. from Tsinghua University and worked as an intern at Raytheon BBN, IBM and Siemens. For more information, please visit his website.
Title: Fast Low-rank Estimation via Non-convex Projected Gradient Descent
Abstract: Fitting a rank-r matrix to noisy data arise in many applications. The popular approach of nuclear/trace norm minimization, while in principle polynomial-time computable with strong (sometimes minimax optimal) statistical guarantees, is often computationally infeasible for large problems. In this talk, we consider a scalable approach via projected gradient descent over the (non-convex) space of n-by-r matrices. We develop a unified framework characterizing the convergence of such methods as well as the statistical properties of the resulting fixed point. Our results apply to a broad range of concrete models, including noisy matrix sensing, matrix completion with real and one-bit observations, matrix decomposition, structured PCA and graph clustering problems. For these problems non-convex projected gradient descent runs in near linear time, and provides statistical guarantees that match (and sometimes better than) the best known results provided by convex relaxation methods.
Refreshments will be served after the seminar in 1181 Comstock Hall.