Rank Overparameterization: Embracing Nonconvexity in Low-rank Optimization

Abstract

Low-rank structures permeate a vast array of real-world applications, from machine learning models to robot navigation to scheduling and operating electricity grids. Their power lies in their natural ability to encode high-dimensional phenomena through low-dimensional latent representations, and their expressiveness in modeling a wide range of nonlinear physical phenomena. However, the inherent nonconvexity of low-rank optimization has long been seen as a prohibitive barrier: direct nonconvex methods risk getting trapped in spurious local minima, while convex relaxations often result in intractable computations at scale. In this talk, we challenge this conventional view by embracing nonconvexity and mitigating its drawbacks. We show that overparameterizing the low-rank factorization systematically reduces the occurrence of spurious local minima through a stepwise process, where higher ranks progressively “smooth out” the landscape until every local minimum becomes global and every saddle point is escapable. We also present posteriori certification methods based on rank deficiency to verify global optimality post-optimization, and introduce an inexpensive preconditioner that restores the linear convergence of gradient descent in overparameterized regimes. Finally, we discuss how these advances lay the groundwork for developing low-rank optimization into a distinct and impactful discipline within mathematical optimization?one that bridges theory, computation, and real-world applications in safety-critical domains.

Bio

Richard Y. Zhang is an Assistant Professor in the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. He received the B.E. (hons) degree with first class honors in Electrical Engineering from the University of Canterbury, Christchurch, New Zealand, and the S.M. and Ph.D. degrees in Electrical Engineering and Computer Science from MIT. Before joining the University of Illinois, he was a Postdoctoral Scholar at the University of California, Berkeley. His research interests are in optimization and machine learning, and applications in power and energy systems. He is particularly interested in theoretical foundations and practical algorithms for nonconvex low-rank matrix optimization and convex semidefinite programming. He is a recipient of the NSF CAREER Award in 2021.