Matrix Completion has No Spurious Local Minimum

Introduction

Matrix completion is the problem of recovering a low rank matrix from partially observed entries. It has been widely used in collaborative filtering and recommender systems , dimension reduction and multi-class learning . There has been extensive work on designing efficient algorithms for matrix completion with guarantees. One earlier line of results (see and the references therein) rely on convex relaxations. These algorithms achieve strong statistical guarantees, but are quite computationally expensive in practice.

These algorithms are much faster than the convex relaxation algorithms, which is crucial for their empirical success in large-scale collaborative filtering applications .

Most of the theoretical analysis of the nonconvex procedures require careful initialization schemes: the initial point should already be close to optimumThe work of De Sa et al. is an exception, which gives an algorithm that uses fresh samples at every iteration to solve matrix completion (and other matrix problems) approximately.. In fact, Sun and Luo showed that after this initialization the problem is effectively strongly-convex, hence many different optimization procedures can be analyzed by standard techniques from convex optimization.

However, in practice people typically use a random initialization, which still leads to robust and fast convergence. Why can these practical algorithms find the optimal solution in spite of the non-convexity? In this work we investigate this question and show that the matrix completion objective has no spurious local minima. More precisely, we show that any local minimum $X$ of objective function $f(\cdot)$ is also a global minimum with $f(X)=0$, and recovers the correct low rank matrix $M$.

Our characterization of the structure in the objective function implies that (stochastic) gradient descent from arbitrary starting point converge to a global minimum. This is because gradient descent converges to a local minimum , and every local minimum is also a global minimum.

There are two known issues with matrix completion. First, the choice of $Z$ is not unique since $M=(ZR)(ZR)^{\top}$ for any orthonormal matrix $Z$. Our goal is to find one of these equivalent solutions.

Another issue is that matrix completion is impossible when $M$ is “aligned” with standard basis. For example, when $M$ is the identity matrix in its first $r\times r$ block, we will very likely be observing only 0 entries. To address this issue, we make the following standard assumption:

Moreover, $Z$ has a bounded condition number $\sigma_{\max}(Z)/\sigma_{\min}(Z)=\kappa$.

Throughout this paper we think of $\mu$ and $\kappa$ as small constants, and the sample complexity depends polynomially on these two parameters. Also note that this assumption is independent of the choice of $Z$: all $Z$ such that $ZZ^{T}=M$ have the same row norms and Frobenius norm.

This assumption is similar to the “incoherence” assumption . Our assumption is the same as the one used in analyzing non-convex algorithms .

We enforce $X$ to also satisfy this assumption by a regularizer

where $R(X)$ is a function that penalizes $X$ when one of its rows is too large. See Section 4 and Section 5 for the precise definition. Our main result shows that in this setting, the regularized objective function has no spurious local minimum:

[Informal] All local minimum of the regularized objective (1.2) satisfy $XX^{T}=ZZ^{T}=M$ when $p\geqslant\mbox{poly}(\kappa,r,\mu,\log d)/d$.

Combined with the results in (see Theorem 2.3) Theorem 1.1, as state informally above, doesn’t guarantee that $f$ satisfies the condition in Theorem 2.3. See its technical version, Theorem 5.3, which shows that the condition of Theorem 2.3 is satisfied. , we have,

With high probability, stochastic gradient descent on the regularized objective (1.2) will converge to a solution $X$ such that $XX^{T}=ZZ^{T}=M$ in polynomial time from any starting point. Gradient descent will converge to such a point with probability 1 from a random starting point.

Our results are also robust to noise. Even if each entry is corrupted with Gaussian noise of standard deviation $\mu^{2}\|Z\|_{F}^{2}/d$ (comparable to the magnitude of the entry itself!), we can still guarantee that all the local minima satisfy $\|XX^{T}-ZZ^{T}\|_{F}\leqslant\varepsilon$ when $p$ is large enough. See the discussion in Appendix B for results on noisy matrix completion.

Our main technique is to show that every point that satisfies the first and second order necessary conditions for optimality must be a desired solution. To achieve this we use new ideas to analyze the effect of the regularizer and show how it is useful in modifying the first and second order conditions to exclude any spurious local minimum.

2 Related Work

Non-convex Optimization

Recently, a line of work analyzes non-convex optimization by separating the problem into two aspects: the geometric aspect which shows the function has no spurious local minimum and the algorithmic aspect which designs efficient algorithms can converge to local minimum that satisfy first and (relaxed versions) of second order necessary conditions.

Our result is the first that explains the geometry of the matrix completion objective. Similar geometric results are only known for a few problems: SVD/PCA phase retrieval/synchronization, orthogonal tensor decomposition, dictionary learning . The matrix completion objective requires different tools due to the sampling of the observed entries, as well as carefully managing the regularizer to restrict the geometry. Parallel to our work Bhojanapalli et al. showed similar results for matrix sensing, which is closely related to matrix completion. Loh and Wainwright showed that for many statistical settings that involve missing/noisy data and non-convex regularizers, any stationary point of the non-convex objective is close to global optima; furthermore, there is a unique stationary point that is the global minimum under stronger assumptions .

On the algorithmic side, it is known that second order algorithms like cubic regularization and trust-region algorithms converge to local minima that approximately satisfy first and second order conditions. Gradient descent is also known to converge to local minima from a random starting point. Stochastic gradient descent can converge to a local minimum in polynomial time from any starting point . All of these results can be applied to our setting, implying various heuristics used in practice are guaranteed to solve matrix completion.

Preliminaries

For $\Omega\subset[d]\times[d]$, let $P_{\Omega}$ be the linear operator that maps a matrix $A$ to $P_{\Omega}(A)$, where $P_{\Omega}(A)$ has the same values as $A$ on $\Omega$, and outside of $\Omega$.

We will use the following matrix norms: $\|\cdot\|_{F}$ the frobenius norm, $\|\cdot\|$ spectral norm, $|A|_{\infty}$ elementwise infinity norm, and $|A|_{p\rightarrow q}=\max_{\|x\|_{p}=1}\|A\|_{q}$. We use the shorthand $\|A\|_{\Omega}=\|P_{\Omega}A\|_{F}$. The trace inner product of two matrices is $\langle A,B\rangle=\operatorname{tr}(A^{\top}B)$, and $\sigma_{\min}(X)$, $\sigma_{\max}(X)$ are the smallest and largest singular values of $X$. We also use $X_{i}$ to denote the $i$-th row of a matrix $X$.

2 Necessary conditions for Optimality

A point $x$ satisfies the first order necessary condition for optimality (later abbreviated as first order optimality condition) if $\nabla f(x)=0$. A point $x$ satisfies the second order necessary condition for optimality (later abbreviated as second order optimality condition)if $\nabla^{2}f(x)\succeq 0$.

These conditions are necessary for a local minimum because otherwise it is easy to find a direction where the function value decreases. We will also consider a relaxed second order necessary condition, where we only require the smallest eigenvalue of the Hessian $\nabla^{2}f(x)$ to be not very negative:

For $\tau\geqslant 0$, a point $x$ satisfies the $\tau$-relaxed second order optimality condition, if $\nabla^{2}f(x)\succeq-\tau\cdot I$.

This relaxation to the second order condition makes the conditions more robust, and allows for efficient algorithms.

Proof Strategy: “simple” proofs are more generalizable

In this section, we demonstrate the key ideas behind our analysis using the rank $r=1$ case. In particular, we first give a “simple” proof for the fully observed case. Then we show this simple proof can be easily generalized to the random observation case. We believe that this proof strategy is applicable to other statistical problems involving partial/noisy observations. The proof sketches in this section are only meant to be illustrative and may not be fully rigorous in various places. We refer the readers to Section 4 and Section 5 for the complete proofs.

In the rank $r=1$ case, we assume $M=zz^{\top}$, where $\|z\|=1$, and $\|z\|_{\infty}\leqslant\frac{\mu}{\sqrt{d}}$. Let $\varepsilon\ll 1$ be the target accuracy that we aim to achieve in this section and let $p=\mbox{poly}(\mu,\log d)/(d\varepsilon)$.

For simplicity, we focus on the following domain $\mathcal{B}$ of incoherent vectors where the regularizer $R(x)$ vanishes,

Inside this domain $\mathcal{B}$, we can restrict our attention to the objective function without the regularizer, defined as,

It turns out to be insightful to consider the full observation case when $\Omega=[d]\times[d]$. The corresponding objective is

Under the setting of this section, in the domain $\mathcal{B}$, the function $g(\cdot)$ has only two local minima $\{\pm z\}$ .

Before introducing the “simple” proof, let us first look at a delicate proof that does not generalize well.

We compute the gradient and Hessian of $g(x)$,

Therefore, a critical point $x$ satisfies $\nabla g(x)=Mx-\|x\|^{2}x=0$, and thus it must be an eigenvector of $M$ and $\|x\|^{2}$ is the corresponding eigenvalue. Next, we prove that the hessian is only positive definite at the top eigenvector . Let $x$ be an eigenvector with eigenvalue $\lambda=\|x\|^{2}$, and $\lambda$ is strictly less than the top eigenvalue $\lambda^{*}$. Let $z$ be the top eigenvector. We have that $\langle z,\nabla^{2}g(x)z\rangle=-\langle z,Mz\rangle+\|x\|^{2}=-\lambda^{*}+\lambda<0$, which shows that $x$ is not a local minimum. Thus only $z$ can be a local minimizer, and it is easily verified that $\nabla^{2}g(z)$ is indeed positive definite.

“Simple” and Generalizable proof

The lessons from the subsection above suggest us find an alternative proof for the full observation case which is generalizable. The alternative proof will be simple in the sense that it doesn’t use the notion of eigenvectors and eigenvalues. Concretely, the key observation behind most of the analysis in this paper is the following,

Proofs that consist of inequalities that are linear in $\mathbf{1}_{\Omega}$ are often easily generalizable to partial observation case.

Here statements that are linear in $\mathbf{1}_{\Omega}$ mean the statements of the form $\sum_{ij}1_{(i,j)\in\Omega}T_{ij}\leqslant a$. We will call these kinds of proofs “simple” proofs in this section. Roughly speaking, the observation follows from the law of large numbers — Suppose $T_{ij},(i,j)\in[d]\times[d]$ is a sequence of bounded real numbers, then the sampled sum $\sum_{(i,j)\in\Omega}T_{ij}=\sum_{i,j}\mathbf{1}_{(i,j)\in\Omega}T_{ij}$ is an accurate estimate of the sum $p\sum_{i,j}T_{ij}$, when the sampling probability $p$ is relatively large. Then, the mathematical implications of $p\sum T_{ij}\leqslant a$ are expected to be similar to the implications of $\sum_{(i,j)\in\Omega}T_{ij}\leqslant a$, up to some small error introduced by the approximation. To make this concrete, we give below informal proofs for Lemma 3.2 and Lemma 3.1 that only consists of statements that are linear in $\mathbf{1}_{\Omega}$. Readers will see that due to the linearity, the proof for the partial observation case (shown on the right column) is a direct generalization of the proof for the full observation case (shown on the left column) via concentration inequalities (which will be discussed more at the end of the section).

Suppose $x\in\mathcal{B}$ satisfies $\nabla g(x)=0$, then $\langle x,z\rangle^{2}=\|x\|^{4}$.

Intuitively, this proof says that the norm of a critical point $x$ is controlled by its correlation with $z$. Here at the lasa sampling version of the f aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ∎

The last step uses the fact that equation (3.5) and (3.6) are approximately equal up to scaling factor $p$ for any $x\in\mathcal{B}$, since (3.6) is a sampled version of (3.5). ∎

Subtleties regarding uniform convergence

In the proof sketches above, our key idea is to use concentration inequalities to link the full observation objective $g(x)$ with the partial observation counterpart. However, we require a uniform convergence result. For example, we need a statement like “w.h.p over the choice of $\Omega$, equation (3.5) and (3.6) are similar to each other up to scaling”. This type of statement is often only true for $x$ inside the incoherent ball $\mathcal{B}$. The fix to this is the regularizer. For non-incoherent $x$, we will use a different argument that uses the property of the regularizer. This is besides the main proof strategy of this section and will be discussed in subsequent sections.

Warm-up: Rank-1 Case

In this section, using the general proof strategy described in previous section, we provide a formal proof for the rank-1 case. In subsection 4.1, we formally work out the proof sketches of Section 3. In subsection 4.2, we prove that due to the effect of the regularizer, outside incoherent ball $\mathcal{B}$, the objective function doesn’t have any local minimum.

In the rank-1 case, the objective function simplifies to,

Here we use the the regularization $R(x)$

The parameters $\lambda$ and $\alpha$ will be chosen later as in Theorem 4.2. We will choose $\alpha>10\mu/\sqrt{d}$ so that $R(x)=0$ for incoherent $x$, and thus it only penalizes coherent $x$. Moreover, we note $R(x)$ has Lipschitz second order derivative. This is the main reason for us to choose $4$-th power instead of $2$-nd power.

We first state the optimality conditions, whose proof is deferred to Appendix A.

The first order optimality condition of objective (4.1) is,

and the second order optimality condition requires:

Moreover, The $\tau$-relaxed second order optimality condition requires

We give the precise version of Theorem 1.1 for the rank-$1$ case.

In the rest of this section, we will first prove that when $x$ is constrained to be incoherent (and hence the regularizer is 0 and concentration is straightforward) and satisfies the optimality conditions, then $x$ has to be $z$ or $-z$. Then we go on to explain how the regularizer helps us to change the geometry of those points that are far away from $z$ so that we can rule out them from being local minimum. For simplicity, we will focus on the part that shows a local minimum $x$ must be close enough to $z$.

In the setting of Theorem 4.2, suppose $x$ satisfies the first-order and second-order optimality condition (4.2) and (4.3). Then when $p$ is defined as in Theorem 4.2,

This turns out to be the main challenge. Once we proved $x$ is close, we can apply the result of Sun and Luo (see Lemma C.1), and obtain Theorem 4.2.

Note that the desired solution $z$ is in $\mathcal{B}$, and the regularization $R(x)$ vanishes inside $\mathcal{B}$.

The following lemmas assume $x$ satisfies the first and second order optimality conditions, and deduce a sequence of properties that $x$ must satisfy.

Under the setting of Theorem 4.2 , with high probability over the choice of $\Omega$, for any $x\in\mathcal{B}$ that satisfies second-order optimality condition (4.3) we have,

The same is true if $x\in\mathcal{B}$ only satisfies $\tau$-relaxed second order optimality condition for $\tau\leqslant 0.1p$.

We plug in $v=z$ in the second-order optimality condition (4.3), and obtain that

Intuitively, when restricted to $\Omega$, the squared Frobenius on the LHS and the quadratic form on the RHS should both be approximately a $p$ fraction of the unrestricted case. In fact, both LHS and RHS can be written as the sum of terms of the form $\langle P_{\Omega}(uv^{T}),P_{\Omega}(st^{T})\rangle$, because

Therefore we can use concentration inequalities (Theorem D.1), and simplify the equation

where $\varepsilon=O(\mu^{2}\sqrt{\frac{\log d}{pd}})$. Similarly, by Theorem D.1 again, we have

(Note that even we use the $\tau$-relaxed second order optimality condition, the RHS only becomes $1.99p\|z\|^{4}-2p\langle x,z\rangle^{2}\pm O(p\varepsilon)$ which does not effect the later proofs.)

Therefore plugging in estimates above back into equation (4.6), we have that

which implies that $6p\|x\|^{2}\|z\|^{2}\geqslant 2p\|x\|^{2}\|z\|^{2}+4p\langle x,z\rangle^{2}\geqslant 2p\|z\|^{4}-O(p\varepsilon)$. Using $\|z\|^{2}=1$, and $\varepsilon$ being sufficiently small, we complete the proof. ∎

Next we use first order optimality condition to pin down another property of $x$ – it has to be close to $z$ after scaling. Note that this doesn’t mean directly that $x$ has to be close to $z$ since $x=0$ also satisfies first order optimality condition (and therefore the conclusion (4.7) below).

With high probability over the randomness of $\Omega$, for any $x\in\mathcal{B}$ that satisfies first-order optimality condition (4.2), we have that $x$ also satisfies

Note that since $x\in\mathcal{B}$, we have $R(x)=0$. Therefore first-order optimality condition says that

Again, intuitively we hope $P_{\Omega}(zz^{T})\approx pzz^{T}$ and $P_{\Omega}(xx^{T})x\approx p\|x\|^{2}x$. These are made precise by the concentration inequalities Lemma D.4 and Theorem D.2 respectively.

By Theorem D.2, we have that with high probability over the choice of $\Omega$, for every $x\in\mathcal{B}$,

Plugging in estimates (4.10) and (4.9) into equation (4.8), we complete the proof. ∎

Finally we combine the two optimality conditions and show equation (4.7) implies $xx^{T}$ must be close to $zz^{T}$.

Suppose vector $x$ satisfies that $\|x\|^{2}\geqslant 1/4$, and that $\left\lVert\langle z,x\rangle z-\|x\|^{2}x\right\rVert\leqslant\delta\,.$ Then for $\delta\in(0,0.1)$,

In particular, we know $|1-u^{2}|\leqslant 4\delta$ and $u\|v\|\leqslant 4\delta$. This means $|u|\in 1\pm 3\delta$ and $\|v\|\leqslant 8\delta$. Now we expand $xx^{T}-zz^{T}$:

It is clear that all the terms have norm bounded by $O(\delta)$, therefore $\left\lVert xx^{\top}-zz^{\top}\right\rVert_{F}^{2}\leqslant O(\delta)$. ∎

2 Extension to general x𝑥x

We have shown when $x$ is incoherent and satisfies first and second order optimality conditions, then it must be close to $z$ or $-z$. Now we need to consider more general cases when $x$ may have some very large coordinates. Here the main intuition is that the first order optimality condition with a proper regularizer is enough to guarantee that $x$ cannot have a entry that is too much bigger than $\mu/\sqrt{d}$.

With high probability over the choice of $\Omega$, for any $x$ that satisfies first-order order optimality condition (4.2), we have

Here we recall that $\alpha$ was chosen to be $10\mu/\sqrt{d}$ and $\lambda$ is chosen to be large so that the $\alpha$ dominates the second term $\mu\sqrt{p/\lambda}$ in the setting of Theorem 4.2.

Suppose $i^{\star}=\max_{j}|x_{j}|$. Without loss of generality, suppose $x_{i^{\star}}\geqslant 0$. Suppose $i^{\star}$-th row of $\Omega$ consists of entries with index $[i]\times S_{i^{\star}}$. If $|x_{i^{\star}}|\leqslant 2\alpha$, we are done. Therefore in the rest of the proof we assume $|x_{i^{\star}}|>2\alpha$. Note that when $p\geqslant c(\log d)/d$ for sufficiently large constant $c$, with high probability over the choice of $\Omega$, we have $|S_{i^{\star}}|\leqslant 2pd$. In the rest of argument we are working with such an $\Omega$ with $|S_{i^{\star}}|\leqslant 2pd$.

We will compare the $i^{\star}$-th coordinate of LHS and RHS of first-order optimality condition (4.2). For preparation, we have

where the last step we used the fact that $|S_{i^{\star}}|\leqslant 2pd$. Moreover, we have that

Now plugging in the bounds above into the $i^{\star}$-th coordinate of equation (4.2), we obtain

which implies that $|x_{i^{\star}}|\leqslant 4\sqrt{p\mu^{2}/\lambda}$. ∎

Setting $\lambda\geqslant\mu^{2}p/\alpha^{2}$ and $\alpha=10\mu\sqrt{1/d}$, Lemma 4.7 ensures that any $x$ that satisfies first-order optimality condition is the following ball,

Then we would like to continue to use arguments similar to Lemma 4.4 and 4.5. However, things have become more complicated as now we need to consider the contribution of the regularizer.

In the setting of Theorem 4.2, with high probability over the choice of $\Omega$, suppose $x\in\mathcal{B}^{\prime}$ satisfies second-order optimality condition (4.3) or $\tau$-relaxed condition for $\tau\leqslant 0.1p$, we have $\|x\|^{2}\geqslant 1/8$.

The guarantees and proofs are very similar to Lemma 4.4. The main intuition is that we can restrict our attentions to coordinates whose regularizer is equal to 0. See Section A for details.

We will now deal with first order optimality condition. We first write out the basic extension of Lemma 4.5, which follows from the same proof except we now include the regularizer term.

With high probability over the randomness of $\Omega$, for any $x\in\mathcal{B}^{\prime}$ that satisfies first-order optimality condition (4.2), we have that $x$ also satisfies

Next we will show that we can remove the regularizer term, the main observation here is nonzero entries $\nabla R(x)$ all have the same sign as the corresponding entries in $x$. See Section A for details.

Suppose $x\in\mathcal{B}^{\prime}$ satisfies that $\|x\|^{2}\geqslant 1/8$, under the same assumption as Lemma 4.9. we have,

Rank-r case

In this section we show how to extend the results in Section 4 to recover matrices of rank $r$. Here we still use the same proof strategy of Section 3. Though for simplicity we only write down the proof for the partial observation case, while the analysis for the full observation case (which was our starting point) can be obtained by substituting $[d]\times[d]$ for $\Omega$ everywhere.

Without loss of generality, we assume that $\|Z\|_{F}^{2}=r$ in this section. This implies that $\sigma_{\max}(Z)\geqslant 1\geqslant\sigma_{\min}(Z)$. Now we shall state the first and second order optimality conditions:

If $X$ is a local optimum of objective function (5.1), its first order optimality condition is,

and the second order optimality condition is equivalent to

Note that the regularizer now is more complicated than the one dimensional case, but luckily we still have the following nice property.

Now we are ready to state the precise version of Theorem 1.1:

Suppose $p\geqslant C\max\{\mu^{6}\kappa^{16}r^{4},\mu^{4}\kappa^{4}r^{6}\}d^{-1}\log^{2}d$ where $C$ is a large enough constant. Let $\alpha=32\mu\kappa r/\sqrt{d},\lambda\geqslant\mu^{2}rp/\alpha^{2}$. Then with high probability over the randomness of $\Omega$, any local minimum $X$ of $f(\cdot)$ satisfies that $f(X)=0$, and in particular, $ZZ^{\top}=XX^{\top}$.

Moreover, If $X$ satisfies that $\|\nabla f(X)\|_{F}\leqslant\delta\leqslant p\sigma^{3}(Z)/C$ and $\nabla^{2}f(X)\succeq-1/C\cdot\mu^{2}\kappa r^{2}p^{1/2}d^{-1/2}I$, then $X$ is an approximate global minimum in the sense that $\|XX^{\top}-M\|_{F}^{2}\leqslant O(\delta/p).$

The proof of this Theorem follows from a similar path as Theorem 4.2. We first notice that because of the regularizer, any matrix $X$ that satisfies first order optimality condition must be somewhat incoherent (this is analogues to Lemma 4.7):

Suppose $|S_{i}|\leqslant 2pd$. Then for any $X$ satisfies 1st order optimality (5.2), we have

Assume $i^{\star}=\operatorname{argmax}_{i}\|X_{i}\|$. Suppose the $i$th row of $\Omega$ consists of entries with index $[i]\times S_{i}$. If $\|X_{i^{\star}}\|\leqslant 2\alpha$, then we are done. Therefore in the rest of the proof we assume $\|X_{i^{\star}}\|\geqslant 2\alpha$.

We will compare the $i$-th row of LHS and RHS of (5.2). For preparation, we have

Next we lowerbound the norm of the RHS of equation (5.2). We have that

Therefore plugging in equation above and equation (5.6) into 1st order optimality condition (5.2). We obtain that $\|X_{i^{\star}}\|\leqslant\sqrt{8\mu^{2}rp/\lambda}$ which completes the proof. ∎

Next, we prove a property implied by first order optimality condition, which is similar to Lemma 4.9.

In the setting of Theorem 5.3, with high probability over the choice of $\Omega$, for any $X$ that satisfies 1st order optimality condition (5.2), we have

where $\delta=O(\mu^{3}\kappa^{3}r^{2}\log^{0.75}(d)\sigma_{\max}(Z)^{-3}(dp)^{-1/2})$ and $\gamma=\lambda/(2p)\geqslant 0$.

If $\|X\|_{F}\leqslant\sqrt{r\sigma_{\max}(Z)^{2}}$ we are done. When $\|X\|_{F}\geqslant\sqrt{r\sigma_{\max}(Z)^{2}}$, by Lemma 5.4, we have that $\max\|X_{i}\|\leqslant 4\alpha=O(\mu\kappa r/\sqrt{d})$, and therefore $\max\|X_{i}\|\leqslant\nu\|X\|_{F}$ with $\nu=O(\mu\kappa\sqrt{r}/\sigma_{\max}(Z))$. Then by Theorem D.2, we have that

where $\delta=O(\mu^{3}\kappa^{3}r^{2}\log^{0.75}(d)\sigma_{\max}(Z)^{-3}(dp)^{-1/2})$. These two imply equation (5.11). Moreover, we have

Suppose $X$ has singular value $\sigma_{1}\geqslant\dots\geqslant\sigma_{r}$. Then we have $\left\lVert ZZ^{\top}X\right\rVert_{F}^{2}\leqslant\|ZZ^{\top}\|^{2}\|X\|_{F}^{2}\leqslant\sigma_{\max}(Z)^{4}\|X\|_{F}^{2}=\sigma_{\max}(Z)^{4}(\sigma_{1}^{2}+\dots+\sigma_{r}^{2})$. On the other hand, $\left\lVert XX^{\top}X\right\rVert_{F}^{2}=\sigma_{1}^{6}+\dots+\sigma_{r}^{6}$. Therefore, equation (5.12) implies that

Then we have (by Proposition E.2) we complete the proof.

Now we look at the second order optimality condition, this condition implies the smallest singular value of $X$ is large (similar to Lemma 4.8). Note that this lemma is also true even if $x$ only satisfies relaxed second order optimality condition with $\tau=0.01p\sigma_{\min}(Z)$.

In the setting of Theorem 5.3. With high probability over the choice of $\Omega$, suppose $X$ satisfies equation (5.9), (5.4) the 2nd order optimality condition (5.3). Then,

We claim that $\sigma_{\min}(Z_{J})\geqslant\frac{1}{2}\sigma_{\min}(Z)$. Let $L=[d]-J$. Since for any $i\in L$ it holds that $\|X_{i}\|\geqslant\alpha$, we have $|L|\alpha^{2}\leqslant\|X\|_{F}^{2}\leqslant 2r\sigma_{\max}(Z)^{2}$ (by equation (5.9)), and it follows that $|L|\leqslant 2r\sigma_{\max}(Z)^{2}/\alpha^{2}$. Therefore,

Therefore, $Z_{J}$ has column rank exactly $r$. By variational characterization of singular values, we have that for there exists unit vector $z_{J}\in\textup{col-span}(Z_{J})$ such that $\|X^{\top}z_{J}\|\leqslant\sigma_{\min}(X)$. Since $z_{J}\in\textup{col-span}(Z_{J})$ is a unit vector, we have that $z_{J}$ can be written as $z_{J}=Z_{J}\beta$ where $\|\beta\|\leqslant\frac{1}{\sigma_{\min}(Z_{J})}\leqslant O(1/\sigma_{\min}(Z)).$ Therefore this in turn implies that $\|z_{J}\|_{\infty}\leqslant\|Z_{J}\|_{2\rightarrow\infty}\|\beta\|\leqslant O(\mu\sqrt{r/d}/\sigma_{\min}(Z))\leqslant O(\mu\kappa\sqrt{r/d})$.

We will plug in $V=z_{J}v^{T}$ in the 2nd order optimality condition (5.3). Note that since $z_{J}\in\textup{col-span}(Z_{J})$, it is supported on subset $J$, and therefore $\nabla^{2}R(X)V=0$. Therefore the term about regularization in (5.3) will vanish. For simplicity, let $y=X^{\top}z_{J}$, $w=Xv$ We obtain that taking $V=z_{J}v^{\top}$ in equation (5.3) will result in

Note that we have that $\|w\|_{\infty}\leqslant\|X\|_{2\rightarrow\infty}\|v\|\leqslant\mu\sqrt{r/d}$. Recalling that $\|z_{J}\|_{\infty}\leqslant O(\mu\kappa\sqrt{r/d})$, by Theorem D.1, we have that

where $\delta=O(\mu^{2}\kappa r^{2}(pd)^{-1/2})$. Then simple algebraic manipulation gives that

Note that $\langle w,z_{J}\rangle=\langle v,X^{\top}z_{J}\rangle=\langle y,v\rangle$. Recall that $\|z_{J}\|=1$ and $z\in\textup{col-span}(Z_{J})$, and therefore $\|Z^{\top}z_{J}\|=\|Z_{J}^{\top}z_{J}\|\geqslant\sigma_{\min}^{2}(Z_{J})$. Moreover, recall that $\|y\|=\|X^{\top}z_{J}\|\leqslant\sigma_{\min}(X)$. Using these with equation (5.14) we obtain that

Therefore together with equation (5.14) and $\|Z^{\top}z_{J}\|\geqslant\sigma_{\min}^{2}(Z_{J})$ we obtain that

Therefore combining equation (5.15) and the lower bound on $\sigma_{\min}(Z_{J})$ we complete the proof. ∎

Similar as before, we show it is possible to remove the regularizer term here, again the intuition is that the regularizer is always in the same direction as $X$.

Suppose $X$ satisfies equation (5.4) and (5.13) and (5.10), then for any $\gamma\geqslant 0$,

Let $L=\{i:\|X_{i}\|\geqslant\alpha\}$. For $i\not\in L$, we have that $(\nabla R(X))_{i}=0$. Therefore it suffices to prove that for every $i\in L$,

By proposition 5.2, we have $\nabla R(X))_{i}=\Gamma_{ii}X_{i}$ for $\Gamma_{ii}\geqslant 0$. Then

Therefore combining two equations above we obtain equation (5.17) which completes the proof. ∎

Finally we show the form in Equation (5.16) implies $ZZ^{T}$ is close to $XX^{T}$ (this is similar to Lemma 4.6).

Suppose $X$ and $Z$ satisfies that $\sigma_{\min}(X)\geqslant 1/4\cdot\sigma_{\min}(Z)$ and that

where $\delta\leqslant\sigma_{min}^{3}(Z)/C$ for a large enough constant $C$, then

The proof is similar to the one-dimensional case, we will separate $Z$ into the directions that are in column span of $X$ and its orthogonal subspace. We will then show the projection of $Z$ in the column span is close to $X$, and the projection on the orthogonal subspace must be small.

Let $Z=U+V$ where $U=\mbox{Proj}_{span(X)}Z$ is the projection of $Z$ to the column span of $X$, and $V$ is the projection to the orthogonal subspace. Then since $V^{T}X=0$ we know

Here columns of the first term $UU^{T}X$ are in the column span of $X$, and the columns second term $VU^{T}X$ are in the orthogonal subspace. Therefore,

In particular, both terms should be bounded by $\delta^{2}$. Therefore $\|UU^{T}-XX^{T}\|_{F}^{2}\leqslant\delta^{2}/\sigma_{min}^{2}(X)\leqslant 16\delta^{2}/\sigma_{min}^{2}(Z)$.

Also, we know $\sigma_{min}(UU^{T}X)\geqslant\sigma_{min}(XX^{T}X)-\delta\geqslant\sigma_{min}(Z)^{3}/128$ if $\delta\leqslant\sigma_{min}(Z)^{3}/128$. Therefore $\sigma_{min}(U^{T}X)$ is at least $\sigma_{min}(Z)^{3}/\|Z\|128$. Now $\|V\|_{F}^{2}\leqslant\delta^{2}/\sigma_{min}(U^{T}X)^{2}\leqslant O(\delta^{2}\|Z\|^{2}/\sigma_{min}(Z)^{6})$.

Finally, we can bound $\|UV^{T}\|_{F}$ by $\|U\|\|V\|_{F}\leqslant\|Z\|\|V\|_{F}$ (last inequality is because $U$ is a projection of $Z$), which at least $\Omega(\|V\|_{F}^{2})$ when $\delta\leqslant\sigma_{min}(Z)^{3}/128$, therefore

Last thing we need to prove the main theorem is a result from Sun and Luo, which shows whenever $XX^{T}$ is close to $ZZ^{T}$, the function is essentially strongly convex, and the only points that have gradient are points where $XX^{T}=ZZ^{T}$, this is explained in Lemma C.1. Now we are ready to prove Theorem 5.3:

Suppose $X$ satisfies 1st and 2nd order optimality condition. Then by Lemma 5.5 and Lemma 5.4, we have that $X$ satisfies equation (5.4), (5.9), (5.10) and (5.11). Then by Lemma 5.6, we obtain that $\sigma_{\min}(X)\geqslant 1/6\cdot\sigma_{\min}(Z)$. Now by Lemma 5.7 and equation (5.11), we have that $\left\lVert ZZ^{T}X-XX^{T}X\right\rVert_{F}\leqslant\delta$ for $\delta\leqslant c\sigma_{\min}(Z)^{3}/\kappa^{2}$ for sufficiently small constant $c$. Then by Lemma 5.8 we obtain that $\|ZZ^{\top}-XX^{\top}\|_{F}\leqslant c\sigma_{\min}(Z)^{2}$ for sufficiently small constant $c$. By Lemma C.1, in this region the only points that satisfy the first order optimality condition must satisfy $XX^{T}=ZZ^{T}$. ∎

To handle noise, notice that we can only hope to get an approximate solution in presence of noise, and to get that our Lemmas only depend on concentration bounds which still apply in the noisy setting. See Section B for details.

Conclusions

Although the matrix completion objective is non-convex, we showed the objective function has very nice properties that ensures the local minima are also global. This property gives guarantees for many basic optimization algorithms. An important open problem is the robustness of this property under different model assumptions: Can we extend the result to handle asymmetric matrix completion? Is it possible to add weights to different entries (similar to the settings studied in )? Can we replace the objective function with a different distance measure rather than Frobenius norm (which is related to works on 1-bit matrix sensing )? We hope this framework of analyzing the geometry of objective function can be applied to other problems.

References

Appendix A Omitted Proofs in Section 4

We first prove the equivalent form of the first and second order optimality conditions:

The first order optimality condition of objective (4.1) is,

and the second order optimality condition requires:

Moreover, The $\tau$-relaxed second order optimality condition requires

We take the Taylor’s expansion around point $x$. Let $\delta$ be an infinitesimal vector, we have

By symmetry $\langle P_{\Omega}(M-xx^{\top}),x\delta^{\top}\rangle=\langle P_{\Omega}(M-xx^{\top}),\delta x^{\top}\rangle=\langle P_{\Omega}(M-xx^{\top})x,\delta\rangle$, so the first order optimality condition is $\forall\delta,\langle-2P_{\Omega}(M-xx^{\top})x+\lambda\nabla R(x),\delta\rangle=0$, which is equivalent to that $2P_{\Omega}(M-xx^{\top})x=\lambda\nabla R(x)$.

The second order optimality condition says $-\langle P_{\Omega}(M-xx^{\top}),\delta\delta^{\top}\rangle+\frac{1}{2}\|x\delta^{\top}+\delta x^{\top}\|_{F}^{2}+\frac{1}{2}\lambda\delta^{\top}\nabla^{2}R(x)\delta\geqslant 0$ for every $\delta$, which is exactly equivalent to Equation (4.3). ∎

Next we show the full proof for the second order optimality condition:

In the setting of Theorem 4.2, with high probability over the choice of $\Omega$, suppose $x\in\mathcal{B}^{\prime}$ satisfies second-order optimality condition (4.3) or $\tau$-relaxed condition for $\tau\leqslant 0.1p$, we have $\|x\|^{2}\geqslant 1/8$.

If $\|x\|\geqslant 1$, then we are done. Therefore in the rest of the proof we assume $\|x\|\leqslant 1$. The proof is very similar to Lemma 4.4. We plug in $v=z_{J}$ instead into equation (4.3), where $J=\{i:|x_{i}|\leqslant\alpha\}$. Note that $z_{J}^{\top}\nabla^{2}R(z_{J})z_{J}$ vanishes. We plug in $v=z_{J}$ in the equation (4.3) and obtain that $x$ satisfies that

(Again notice that using $\tau$-relaxed second order optimality condition does not effect the RHS by too much, so it does not change later steps.) Therefore plugging the estimates above back into equation (A.1), we have that

Using Cauchy-Schwarz, we have $\|x\|^{2}\|z_{J}\|^{2}\geqslant\langle x,z_{J}\rangle^{2}$, and therefore we obtain that $\|z_{J}\|^{2}\|x\|^{2}\geqslant\frac{1}{3}\|z_{J}\|^{4}-O(\varepsilon)$.

Finally, we claim that $\|z_{J}\|^{2}\geqslant 1/2$, which completes the proof since $\|x\|^{2}\geqslant\frac{1}{3}\|z_{J}\|^{2}-O(\varepsilon)\geqslant 1/8$.

Suppose $\alpha\geqslant\frac{4\mu}{\sqrt{d}}$ and $x$ satisfies $\|x\|_{\infty}\leqslant 4\alpha$ and $\|x\|\leqslant 2$. Let $J=\{i:|x_{i}|\leqslant\alpha\}$. Then we have that $\|z_{J}\|\geqslant 1/2$.

The claim can be simply proved as follows: Since $\|x\|^{2}\leqslant 2$ we have that $|J^{c}|\leqslant 2/\alpha^{2}$ and therefore $\|z_{J^{c}}\|^{2}\leqslant 2\mu^{2}/(d\alpha^{2})$. This further implies that $\|z_{J}\|^{2}=\|z\|^{2}-\|z_{L}\|^{2}\geqslant(1-2\mu^{2}/(d\alpha^{2}))\geqslant\frac{1}{2}$ because $\alpha\geqslant\frac{2\mu}{\sqrt{d}}$. ∎

Suppose $x\in\mathcal{B}^{\prime}$ satisfies that $\|x\|^{2}\geqslant 1/8$, under the same assumption as Lemma 4.9. we have,

Let $L=\{i:\|x_{i}\|\geqslant\alpha\}$. For $i\not\in L$, we have that $(\nabla R(x))_{i}=0$. Therefore it suffices to prove that for every $i\in L$,

Since we have $\nabla R(x)_{i}=\gamma_{i}x_{i}$ for some $\gamma_{i}\geqslant 0$, we have

Therefore combining two equations above we obtain equation (A.2) which completes the proof. ∎

Appendix B Handling Noise

Suppose instead of observing the matrix $ZZ^{T}$, we actually observe a noisy version $M=ZZ^{T}+N$, where $N$ is a Gaussian matrix with independent $N(0,\sigma^{2})$ entries. In this case we should not hope to exactly recover $ZZ^{T}$ (as two close $Z$’s may generate the same observation). In this Section we show even with fairly large noise our arguments can still hold.

Let $\hat{\mu}=\max\{\mu,\sqrt{\frac{4\sigma d\sqrt{\log d}}{r}}\}$. Suppose $p\geqslant C\hat{\mu}^{6}\kappa^{12}r^{4}d^{-1}\varepsilon^{-2}\log^{1.5}d$ where $C$ is a large enough constant. Let $\alpha=2\hat{\mu}\kappa r/\sqrt{d},\lambda\geqslant\hat{\mu}^{2}rp/\alpha^{2}$. Then with high probability over the randomness of $\Omega$, any local minimum $X$ of $f(\cdot)$ satisfies

In fact, a noise level $\sigma\sqrt{\log d}\leqslant\mu^{2}r/d$ (when the noise is almost as large as the maximum possible entry) does not change the conclusions of Lemmas in this Section.

There are only three places in the proof where the noise will make a difference. These are: 1. The infinity norm bound of $M$, used in Lemma 5.4. 2. The LHS of first order optimality condition (Equation (5.2)). 3. The RHS of second order optimality condition (Equation (5.3)).

What we require in these three steps are: 1. $|M|_{\infty}$ should be smaller than $\mu^{2}r/d$. 2. $\langle P_{\Omega}(N),W\rangle$ should be smaller than $|\langle P_{\Omega}(N),P_{\Omega}(W)\rangle|\leqslant O(\sigma|Z|_{\infty}dr\log d+\sqrt{pd^{2}r\sigma^{2}|W|_{\infty}\|W\|_{F}\log d})$. 3. $\|P_{\Omega}(N)\|\leqslant\varepsilon p\|ZZ^{T}\|_{F}$. When we define the $\hat{\mu}=\max\{\mu,\sqrt{\frac{4\sigma d\sqrt{\log d}}{r}}\}$, all of these are satisfied (by Lemma D.5 and D.6).

Now we can follow the proof and see $\delta\leqslant c\varepsilon\sigma_{\min}(Z)/\kappa^{2}$ for small enough constant $c$, and By Lemma 5.8 we know $\|XX^{T}-ZZ^{T}\|_{F}\leqslant\varepsilon$. ∎

Appendix C Finding the Exact Factorization

In Section 5, we showed that any point that satisfies the first and second order necessary condition must satisfy $\|XX^{T}-ZZ^{T}\|_{F}\leqslant c$ for a small enough constant $c$. In this section we will show that in fact $XX^{T}$ must be exactly equal to $ZZ^{T}$. The proof technique here is mostly based on the work of Sun and Luo. However we have to modify their proof because we use slightly different regularizers, and we work in the symmetric case. The main Lemma in can be rephrased as follows in our setting:

Suppose $p\geqslant C\mu^{4}r^{6}\kappa^{4}d^{-1}\log d$ for large enough absolute constant $C$, and $\varepsilon=\sigma_{min}(Z)^{2}/100$. with high probability over the randomness of $\Omega$, we have that for any point $X$ in the set

there exists a matrix $U$ such that $UU^{T}=ZZ^{T}$ and

As a consequence, any point $X$ in the set $\mathcal{B}$ that satisfies first order optimality condition must be a global optimum (or, equivalently, satisfy $XX^{T}=ZZ^{T}$).

Recall $f(X)=\frac{1}{2}\|P_{\Omega}(M-XX^{T})\|_{F}^{2}+\lambda R(X)$. The proof of Lemma C.1 consists of three steps:

1. The regularizer has nonnegative correlation with $(X-U)$: for any $U$ such that $UU^{T}=ZZ^{T}$, we have $\langle\nabla R(X),X-U\rangle\geqslant 0$. (Claim C.3).

2. There exists a matrix $U$ such that $UU^{T}=ZZ^{T}$, and $U$ is close to $X$. (Claim C.4)

3. Argue that $\langle\nabla f(x),X-U\rangle\geqslant\frac{p}{4}\|P_{\Omega}(M-XX^{T})\|_{F}^{2}$ when $U$ is close to $X$. (See proof of Lemma C.1).

Before going into details, the first useful observation is that all matrices $U$ with $UU^{T}=ZZ^{T}$ have the same row norm.

Suppose $UU^{\top}=ZZ^{\top}$, then we have $U=ZR$ where $R$ is an orthonormal matrix. In particular, the $i$-th row of $U$ is equal to

Note that this simple observation is only true in the symmetric case. This Claims serves as the same role of the bounds on row norms of $U,V$ in the asymmetric case (Propositions 4.1 and 4.2 of ).

Next we are ready to argue that the regularizer is always positively correlated with $X-U$.

For any $U$ such that $UU^{T}=ZZ^{T}$, we have,

Since the regularizer is applied independently to individual rows, we can rewrite $\langle\nabla R(X),X-U\rangle=\sum_{i=1}^{n}\langle\nabla R(X_{i}),X_{i}-U_{i}\rangle$, and focus on $i$-th row.

For each row $X_{i}$, $\nabla R(X_{i})$ is 0 when $\|X_{i}\|\leqslant 2\mu\sqrt{r}/\sqrt{d}$. In that case $\langle\nabla R(X_{i}),X_{i}-U_{i}\rangle=0$.

When $\|X_{i}\|$ is larger than $2\mu/\sqrt{d}$, we know $\nabla R(X_{i})$ is always in the same direction as $X_{i}$. In this case $\lambda\nabla R(X_{i})=\gamma X_{i}$ for some $\gamma>0$ and $\|X_{i}\|\geqslant 2\mu\sqrt{r}/\sqrt{d}\geqslant 2\|Z_{i}\|=2\|U_{i}\|$ (where last equality is by Claim C.2). Therefore by triangle inequality

This then implies $\langle\lambda\nabla R(X_{i}),X_{i}-U_{i}\rangle=\gamma\langle X_{i},X_{i}-U_{i}\rangle>0$.

Next we will prove the gradient of $\frac{1}{2}\|P_{\Omega}(M-XX^{T})\|_{F}^{2}$ has a large correlation with $X-U$. This is analogous to Proposition 4.2 in .

Suppose $\|XX^{T}-M\|_{F}=\varepsilon\leqslant\sigma_{min}(Z)^{2}/100$, there exists a matrix $U$ such that $UU^{T}=M$ and $\|X-U\|_{F}\leqslant 5\varepsilon\sqrt{r}/\sigma_{min}(Z)^{2}$.

Without loss of generality we assume $M$ is a diagonal matrix with first $r$ diagonal terms being $\sigma_{1}(Z)^{2},\sigma_{2}(Z)^{2},...,\sigma_{r}(Z)^{2}$ (this can be done by a change of basis). That is, we assume $M=\mathop{\mathbf{diag}}(\sigma_{1}(Z)^{2},\dots,\sigma_{r}(Z)^{2}),0,\dots,0)$. We use $M^{\prime}$ to denote the first $r\times r$ principle submatrix of $M$.

In order to construct $U$, we first notice that $Q$ must be constructed as a zero matrix since $M$ has non-zero diagonal only on the top-left corner. A natural guess of $P$ then becomes a “normalized” version of $V$.

Concretely, we construct $P:=VS=V(V^{T}(M^{\prime})^{-1}V)^{-1/2}$ (where $S:=(V^{T}(M^{\prime})^{-1}V)^{-1/2}$). Thus, the difference between $U$ and $X$ is equal to $\|U-X\|_{F}\leqslant\|P-V\|_{F}+\|W\|_{F}$.

Since $\|XX^{T}-M\|_{F}\leqslant\varepsilon$, we know $\|M^{\prime}-VV^{T}\|_{F}^{2}+2\|VW^{T}\|_{F}^{2}\leqslant\varepsilon^{2}$. In particular both terms are smaller than $\varepsilon^{2}$.

First, we bound $\|W\|_{F}$. Note that since $\|M^{\prime}-VV^{T}\|_{F}\leqslant\varepsilon\leqslant\sigma_{min}(Z)^{2}/100$, we know $\sigma_{min}(V)^{2}\geqslant 0.99\sigma_{min}(Z)^{2}$. Therefore $\sigma_{min}(V)\geqslant 0.9\sigma_{min}(Z)$. Now we know $\|W\|_{F}\leqslant\|VW^{T}\|_{F}/\sigma_{min}(V)\leqslant 2\varepsilon/\sigma_{min}(Z)$.

Next we bound $\|P-V\|_{F}^{2}$. Since $\|M^{\prime}-VV^{T}\|_{F}\leqslant\varepsilon\leqslant\sigma_{min}(Z)^{2}/100$, we know $(1-2\varepsilon/\sigma_{min}(Z)^{2})VV^{T}\preceq M^{\prime}\preceq(1+2\varepsilon^{2}/\sigma_{min}(Z)^{2})VV^{T}$. This implies $\|V\|_{F}\leqslant 1.1\|Z\|_{F}$, and $(1-2\varepsilon/\sigma_{min}(Z)^{2})I\preceq V^{T}M^{-1}V\preceq(1+2\varepsilon/\sigma_{min}(Z)^{2})I$. Therefore the matrix $S$ is also very close to identity, in particular, $\|S-I\|\leqslant 2\varepsilon/\sigma_{min}(Z)^{2}$. Now we know $\|P-V\|_{F}=\|V\|_{F}\|S-I\|\leqslant 3\varepsilon\|Z\|_{F}/\sigma_{min}(Z)^{2}$. Using the fact that $\|Z\|_{F}=1$ we know $\|U-X\|_{F}\leqslant\|P-V\|_{F}+\|W\|_{F}\leqslant 5\varepsilon\sqrt{r}/\sigma_{min}(Z)^{2}$.

We can now combine this Claim with a sampling lemma to show $\|P_{\Omega}((X-U)(X-U)^{T})\|_{F}^{2}$ is small:

Under the same setting of Lemma C.1, with probability at least $1-1/(2n)^{4}$ over the choice of $\Omega$, if $U$ satisfies conclusion of Claim C.4, then,

Intuitively, this Lemma is true because $\|(X-U)(X-U)^{T}\|_{F}\leqslant 25\|M-XX^{T}\|_{F}^{2}r/\sigma_{min}(Z)^{4}$, which is much smaller than $\|M-XX^{T}\|_{F}$ when $\|M-XX^{T}\|_{F}$ is small. By concentration inequalities we expect $\|P_{\Omega}((X-U)(X-U)^{T})\|_{F}^{2}$ to be roughly equal to $p\|(X-U)(X-U)^{T}\|_{F}$, therefore it must be much smaller than $p\|M-XX^{T}\|_{F}^{2}$. The proof of this Lemma is exactly the same as Proposition 4.3 in (in fact, it is directly implied by Proposition 4.3), so we omit the proof here. We also need a different concentration bound for the projection of the norm of the matrix $a=U(X-U)^{T}+(X-U)U^{T}$. Unlike the previous lemma, here we want $\|P_{\Omega}(a)\|_{F}$ to be large.