Timezone: »

 
Poster
Matrix Completion has No Spurious Local Minimum
Rong Ge · Jason Lee · Tengyu Ma

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #185
in Tuesday Posters »

Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for matrix completion has no spurious local minima --- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve matrix completion with \textit{arbitrary} initialization in polynomial time.

Keywords: Learning Theory · Matrix Factorization
[ PDF] 

Author Information

Rong Ge (Princeton University)
Jason Lee (UC Berkeley)
Tengyu Ma (Princeton University)

More from the Same Authors