Speaker: Ruoyu Sun, FAIR (Facebook Artificial Intelligence Research)
Abstract: Matrix completion is a fundamental problem that aims to recover a low-rank matrix from partial observations. As a basic model of recommendation systems, matrix completion is often solved by machine learning practitioners using a non-convex matrix factorization formulation. A natural theoretical question is whether such a non-convex formulation can be easily solved to global optima. We provide an affirmative answer to this question by showing that under mild conditions, many standard optimization algorithms converge to the global optima, and recover the true low-rank matrix. The key step is to establish a local geometrical property of a properly regularized objective function. We first study the geometry of a basic matrix factorization formulation in linear algebra, then show that with missing entries how to properly regularize the problem so that a similar geometrical property still holds.