Oral
A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery
Xiao Zhang · Lingxiao Wang · Yaodong Yu · Quanquan Gu

Thu Jul 12th 11:20 -- 11:30 AM @ K11

We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verified for a broad family of loss functions. In addition, our analytic framework can directly handle the widely-used incoherence constraints through the lens of duality. We illustrate the applicability of the proposed framework to matrix completion and one-bit matrix completion, and prove that all these problems have no spurious local minima. Our results not only improve the sample complexity required for characterizing the global optimality of matrix completion, but also resolve an open problem in \citet{ge2017no} regarding one-bit matrix completion. Numerical experiments show that primal-dual based algorithm can successfully recover the global optimum for various low-rank problems.

Author Information

Xiao Zhang (University of Virginia)
Lingxiao Wang (UCLA)
Yaodong Yu (University of Virginia)
Quanquan Gu (UCLA)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors