Matrix Completion has No Spurious Local Minimum
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 positive semidefinite 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 positive semidefinite matrix completion with arbitrary initialization in polynomial time. The result can be generalized to the setting when the observed entries contain noise. We believe that our main proof strategy can be useful for understanding geometric properties of other statistical problems involving partial or noisy observations.
This paper discusses the geometrical properties of a nonconvex objective for completing a PSD matrix.  The main theorem (Thm 2.3) says all data points x s.t  grad(x) = 0 && hessian(x) >= -tau I is global minimum, this means  i)  All such x is a local minimum and globally optimal ii) All saddle points will have hessian(x) < -tau I (Later analysis shows tau <= 0.1p -- this implies the larger sampling probability, the large negative curvature the saddles have)  This coincides with the characterization of functions with only strictly ridable saddle points in previous work, hence we know some optimization algorithms e.g. cubic regularization, trust region algorithms and SGD can converge to global optima. 
To prove the main theorem, the authors focus on excluding critical points with (1) large coherence with standard base (e.g Lemma 3.7) and (2) large negative curvature (e.g. Lemma 3.8) from local minima. Then they show (3) the other critical points can just be the global optimums (e.g. Lemma 3.10), this boils down to showing such points satisfies Lemma 3.3 and finally C.1, where Lemma 3.3 is reached by Lemma 3.6.  * part 2)  I think what the authors mean in Lemma 3.8 is data points satisfying 1st and 2nd order optimality conditions will have l2 norm at least ⅛, which cannot be achieved for data points whose hessian < -0.1p I. If this is true, I would suggest that the authors rephrase Lemma 3.8 for the sake of easier reading. If not, please clarify how you exclude those points.  * part 3)  I think the chain in (3) is a bit long. For better presentation, I would suggest the authors use compact this part a bit.  Besides, one needs to use Lemma C.1 to conclude that x satisfying Lemma 3.3 can only be equivalent solutions (e.g. z and -z for the rank 1 case). I think it’s better to include Lemma C.1 into main text as (a) this is an important step (b) Lemma C.1 requires an upper bound of epsilon -- a function of p in Lemma 3.3, the reader can see how p scales more clearly.   Other small details:  1) In Thm 3.2,  the authors write "tau < - 0.1p" but tau is claimed to be positive in Def 2.2. From later context (Lemma 3.4), I think the authors mean tau <= 0.1p. 2) Figure 1, the bound for l_infty norm should be 40 u / sqrt(d).  This figure is also a bit confusing. The l2 ball is actually the whole ellipsoid, not a single circle.   To summarize, I think this is a good paper, but the presentation could be improved. The proof idea could be outlined more clearly; how the technical definitions and intuitions are related to previous work could be included for readers not familiar with this area.