Accelerating Ill-conditioned Low-rank Estimation via Scaled Gradient Descent

Abstract:  Many problems encountered in sensing and imaging can be formulated as estimating a low-rank object from incomplete, and possibly corrupted, linear measurements; prominent examples include matrix completion and tensor completion. Through the lens of matrix and tensor factorization, one of the most popular approaches is to employ simple iterative algorithms such as gradient descent to recover the low-rank factors directly, which allow for small memory and computation footprints. However, the convergence rate of gradient descent depends linearly, and sometimes even quadratically, on the condition number of the low-rank object, and therefore, slows down painstakingly when the problem is ill-conditioned. This talk introduces a new algorithmic approach, dubbed scaled gradient descent (ScaledGD), that provably converges linearly at a constant rate independent of the condition number of the low-rank object, while maintaining the low per-iteration cost of gradient descent. A nonsmooth variant of ScaledGD provides further robustness to corruptions by optimizing the least absolute deviation loss. In addition, ScaledGD continues to admit fast global convergence, again independent of the condition number, from a small random initialization when the rank is over-specified. In total, ScaledGD highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the symmetry in low-rank factorization.

Bio:  Dr. Yuejie Chi is a Professor in the department of Electrical and Computer Engineering, and a faculty affiliate with the Machine Learning department and CyLab at Carnegie Mellon University. She received her Ph.D. and M.A. from Princeton University, and B. Eng. (Hon.) from Tsinghua University, all in Electrical Engineering. Her research interests lie in the theoretical and algorithmic foundations of data science, signal processing, machine learning and inverse problems, with applications in sensing, imaging, and societal systems, broadly defined. Among others, Dr. Chi received the Presidential Early Career Award for Scientists and Engineers (PECASE), the inaugural IEEE Signal Processing Society Early Career Technical Achievement Award for contributions to high-dimensional structured signal processing, and held the inaugural Robert E. Doherty Early Career Development Professorship. She was named a Goldsmith Lecturer by IEEE Information Theory Society and a Distinguished Lecturer by IEEE Signal Processing Society.

***Event will take place in hybrid format. The location for in-person attendance will be room 1008 EECS.   Attendance will also be available via Zoom.

Join Zoom Meeting https: https://umich.zoom.us/j/91414297851

Meeting ID: 914 1429 7851

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Michele Feldkamp ([email protected])