Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization

Summary

In this work, the authors proved the global convergence of the gradient descent algorithm with a small initialization for the rank-1 matrix completion problem.

Strengths

The results in this work is novel and should be interesting to audiences in optimization and machine learning fields. This work shows that the incoherence regularizer may be unnecessary for the matrix completion problem.

Weaknesses

A more detailed comparison with Chen, J., Liu, D., & Li, X. (2020). Nonconvex Rectangular Matrix Completion via Gradient Descent Without ℓ₂,∞ Regularization. IEEE Transactions on Information Theory, 66(9), 5806-5841. should be included. In addition, the importance of analyzing the rank-1 case should be discussed in more detail.

Questions

(1) Line 55: I would suggest the authors to be more specific on what parameters the convergence time has a logarithmic dependence on. (2) Line 78: it would be better to be consistent in using "GD" as the abbreviation of "gradient descent". (3) Line 86: it would be better to explicitly mention that u^* is a vector. (4) Line 102: I think the squared norm of x^0 is expected to be \beta_0^2. But I am not sure if the norm of x^0 is expected to be \beta_0. (5) Line 128: I think it may be better to include the global convergence result in a formal theorem (instead of a remark). (6) Line 143: besides the relation between T^* and \beta_0, I wonder if there is a reason why \beta_0 is lower bounded. It seems that the initialization size is not necessarily lower bounded in [17, 23]. It may be better to explain the reason why a lower bound is necessary. (7) Line 154: the remark on the estimation error could also be formalized as a theorem. (8) in Line 88, the authors mentioned that the incoherence at be at most poly(log n). But this condition is not included in Theorem 3.1. I wonder if this condition is necessary for the results. (9) Line 170: please be more specific on the meaning of "incoherent up to a logarithmic factor". (10) In my opinion, the discussion of proof ideas in Sections 4-5 is a little too long. It would be ideal if the length can be reduced by ~2 pages. With that said, I am okay with the current structure. (11) Line 319: "an optimal number of samples" is confusing. Please consider using a different word. (12) Another interesting open problem will be whether the results can be extended to the over-parameterized case, where a small initialization is also required. (13) Besides the aforementioned problem, it would also be interesting to consider the asymmetric matrix completion problem; see the follow-up work: Soltanolkotabi, M., Stöger, D., & Xie, C. (2023). Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. arXiv preprint arXiv:2303.14244.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See my comments in the previous section.

Summary

The paper studies global convergence of GD (with a fixed step-size) for the rank-1 matrix completion problem (with symmetric and i.i.d. Bernoulli(p) observation and Gaussian noise on the entries) started from "small" random initialization. The authors prove that such vanilla GD, without any explicit regularization as commonly used in the literature, converges to the ground truth matrix in a polynomial time with near-optimal sample complexity. The result is interesting and the program is well-motivated. The analysis is mostly based on dynamical systems rather than optimization techniques, and a similar approach could be applied for related problems. The proof idea seems to be novel (although some of the ideas seems to be motivated by recent literatures on GD with small initialization & stepwise for matrix factorization and matrix sensing problem). First, the authors first show that GD for the fully observed case with small initialization converges to the ground truth matrix (Corollary 1 in the appendix). This is possible due to an explicit formula for the GD iterates (a linear combination of the initialization and the ground truth with dynamic coefficients). The analysis is not very difficult, but also not so trivial. Having established the desired convergence result for the fully observed GD dynamics, the main idea is to couple that with the partially observed GD dynamics by starting at the same initialization and use an interpolated dynamics eq. (13). The main novelty is in showing that these two trajectories remain close, and much closer than the norm of the iterates from the fully observed case. This allows one to show that the partially observed iterates converges to a local region near the ground truth after a polynomial number of iterations, and then one can use existing local convergence result [14].

Strengths

The main text is exceptionally well-written (with minor comments/suggestions) in that it gives the structure of the proof of the main result in a very clear manner (which was a pleasure to read for the most part). The argument in the main text is well-complemented with various simulation results. The general rank-r case was also discussed at the end, and the main difficulty of having the r singular values possibly growing at different rates is well-pointed out. It seems that the appendix gives a rigorous justification of most of the claims in the main text (although some references and pointers are missing). I've only read the appendix until Section C and cannot assess that the remainder (the coupling analysis, which is the most substantial part) is correct, but the sketch in the main text is convincing.

Weaknesses

Minor comments: L98: "To recover the matrix," --> "To recover the matrix $M^{\star}$," L110: "controlling the $\ell_{\infty}$-norm in [14]" --> $\ell_{\infty}$-norm of what? Notation $\lesssim$ is not defined L166: ".. linear combination of $x^{(0)}$ and $u^{\star}$, .." --> ".. linear combination of $x^{(0)}$ and $u^{\star}$ (see eq. (C.1) in the appendix)" L214: "becomes" --> "is" L233 and L234: "between" --> "of" L259: ".. parallel to $u^{\star}$." --> ".. parallel to $u^{\star}$ (see Lem. A.5 in the appendix)." L286: ".. in both $\ell_{2}$ and $\ell_{\infty}$ norms, .." --> ".. in both $\ell_{2}$ and $\ell_{\infty}$ norms (see Cor. 1 in the appendix), .."

Questions

eq. (8): Is it intentional to not to cancel out $n^{1/4}$ factor in the upper bound? L216: Shouldn't $\tilde{x}^{(1)}$ here be $x^{(0)}$? Lemma 5.5: $u^{(l)}$ is not defined. Same as $u^{\star}$ but 0 at the $\ell$th coordinate?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

The authors study a random initialization scheme for gradient descent applied to the problem of rank-one matrices, assuming a known ground truth. Their results concern global convergence properties of the with respect to a particular random model of partially observed matrices. Specifically, starting from a $n\times n$ symmetric positive definite, fully-revealed ground truth matrix $\bf{M}^\star = \lambda^\star \bf{u}^\star (\bf{u}^\star)^T= \bf{x}^\star (\bf{x}^\star)^T$, entries above or on the diagonal are perturbed by noise drawn i.i.d. from a zero-mean Gaussian, and revealed independently with probability $p.$ The main result, Theorem 3.1, requires a coherence assumption: namely, for $\lVert \mathbf{u}^\star \rVert = \sqrt{\frac{\mu}{n}},$ the quantity $\mu$ is polynomially-bounded in $n.$ With this assumption, the main result claims that, if the Gaussian noise is sufficiently small and an initial iterate $\mathbf{x}_0$ is provided whose magnitude is not too large or small according to quantities depending on $n, \mu , \lambda^\star ,$ and $p,$ that gradient descent will converge to the given ground truth with probability tending to $1$ as $n\to \infty .$ In addition to giving proofs, the authors explain the qualitative behavior of convergence as determined by several phases, which appear in both the analysis and a simulation study.

Strengths

It seems that the combination of leave-one-out sequences developed in [14] and the random initialization used in areas like phase retrieval are a novel aspect of this work, although as mentioned in Sec. 6 there is difficulty in extending this combination to the case of arbitrary rank. Theorems and definitions are, for the most part, stated unambiguously, and I was unable to find any errors. The topic is clearly a good fit for NeuRIPS.

Weaknesses

One issue I have with this paper is that rank-1 symmetric matrix completion (as well as rank-1 general matrix completion) is simply a much easier problem than general matrix completion. Indeed, I would like to point out the reference "Uniqueness of Low-Rank Matrix Completion by Rigidity theory", by Singer and Cucuringu, which is not cited in this work. Section 5 of this paper shows that the existence of an exact completion is guaranteed (with "probability one") based purely on combinatorial conditions of the graph of revealed entries. By contrast, the authors make high-probability statements about matrices whose entries are drawn and hidden according to specific distributional assumptions as the sample size goes to infinity, which seem to be much stronger. In general, the bibliography could be more extensive. Additionally, equation (8) shows that there are _lower_ bounds in addition to upper bounds on the magnitude of the initialization that is needed. Thus, merely a "small" initialization is not enough to ensure convergence, contrary to the title. Finally, there is a nontrivial coherence assumption. This may be standard in compressed sensing, but it is still a nontrivial assumption. In summary, the assumptions are overly restrictive, and, unlike the arbitrarily matrix completion problem, rank-1 matrix completion is a fairly simple problem. So, I think the paper's claimed results are not very interesting overall.

Questions

line 3: Do you mean "simplest yet _most_ efficient?" line 121: It would helpful to clarify that asymptotic notation like $o(1)$ refers to the regime $n\to \infty ,$ as opposed to other parameters tending towards infinity or zero. Theorem 3.1: It seems that a corollary of this theorem would be that $\pm \bf{x}^\star$ are the only ground-truth solutions to the matrix completion problem. Is that something that is already assumed in the proof of your result? I don't see anywhere an explanation of why the cases with multiple ground truth solutions would be asymptotically rare.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

n/a

Summary

This paper studies the global convergence of vanilla GD for the rank-1 matrix completion problem. It is shown that with small random initialization and after a logarithmic number of steps, GD enters a region around the global minimizers in which linear convergence happens. The paper provides sufficient conditions on the initialization scale to ensure this phenomenon happens and shows a tradeoff between the initialization scale and the number of available samples. Illustrative simulations are provided.

Strengths

The paper studies a topic of interest for the Neurips community, which it presents in a clear manner and for which it provides results of both practical and theoretical importance. The derivations in the main paper are cleanly carried out, and the reasoning behind them is well-presented.

Weaknesses

- The sample complexity seems to be quite large (for example, compared to that in [1]). In this light, can the authors elaborate further on this aspect (my question is despite the further commentary in section 6)? [1] C. Ma, K. Wang, Y. Chi, and Y. Chen, “Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution,” Foundations of Computational Mathematics, vol. 20, no. 3, pp. 451–632, 2020.

Questions

- The nature of the presented proofs lies very much in the detail. While the authors did a good job providing a higher-level view of the proof strategy, and the writing is clear, the text is still difficult to follow at times. A possible improvement would be to include some pictorial description of the phases -- similar to the one in section 4, for the analysis carried out in sections 5, 6. This can significantly aid understanding, in my opinion. - Figure 2 a: the green line is labelled as $\\| x^{(t)} - x^{\star} \\|$, but in the figure commentary it is written $\\|x^{(t)} \pm x^{\star}\\|$. Which one is the correct one? - Figure 2 c: Perhaps instead the label "Distance" can be replaced with $\\|x^{(t)} \pm x^{\star}\\|$ for clarity.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitations are adequately discussed.

Summary

This paper shows some convergence properties of gradient descent with small random initialization for rank-1 noisy matrix completion.

Strengths

This paper uses a new approach (gradient descent with small random initialization) to solve the nonconvex formulation for rank-1 noisy matrix completion. It is shown that the GD trajectory will arrive at a local neighborhood (in both $\ell_2$ and $\ell_{\infty$ norm) of the ground truth within a number of iteration.

Weaknesses

1. My major concern of this paper is a lack of theoretical novelty. After looking at the results and quickly go through the proof, I believe the proof idea of this paper is similar to that in [1], which focus on a general low-rank matrix sensing problem (we know that the low-rank matrix sensing problem with certain RIP condition has the same population-level loss function as the noisy matrix completion problem). For example, the analysis idea that the GD dynamic is close to a simplified linear evolution system in the initial phase thanks to the small initialization already appeared in [1]. Compared with [1] which works for general low-rank setting, this paper only works for the rank-1 case, which is more restricted. On the other hand, matrix completion problems are known to be more difficult than the matrix sensing problem in the sense that it requires incoherence and $\ell_{2,\infty}$ error analysis to show that the empirical loss concentrates around the population counterpart. This difficulty was not encountered in [1]. This paper uses leave-one-out analysis that has been widely used in low-rank estimation literature like [2,3] to track the $\ell_{\infty}$ error of the GD trajectory. The analysis does not seems to be challenging, if one is familiar with the above-mentioned literature. If I underestimate the technical novelty of the paper, I hope the authors could clarify and please highlight their technical novelty. 2. I am not satisfied with the convergence guarantees. The estimation error provided by Theorem 3.1 only shows that the output of the proposed algorithm is consistent, namely is $o(1)$. However state-of-the-art results for matrix completion already shows that GD with spectral initialization (which I believe is equivalent to small random initialization in some sense, since the initial phase of the latter algorithm is similar to some form of power method) achieves minimax-optimal estimation error [2]. Could the authors please explain why their analysis leads to looser error bound? 3. In addition, the noise condition in Theorem 3.1 is $\sqrt{np}$ times more stringent than that in [2]. Could the authors please explain why their analysis requires stronger noise conditions? [1] Li, Yuanzhi, Tengyu Ma, and Hongyang Zhang. "Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations." Conference On Learning Theory. PMLR, 2018. [2] Ma, Cong, et al. "Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution." Foundations of Computational Mathematics 20 (2020): 451-632. [3] Chen, Yuxin, et al. "Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval." Mathematical Programming 176 (2019): 5-37.

Questions

I have no question at this moment.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

This paper does not have potential negative social impact.

Summary

This work considers the convergence analyses of gradient descent method for rank-one matrix completion problem. In particular, this work assumes small random initialization, which is relatively relaxed condition compared to existing work. With such assumption, the logarithmic convergence of the gradient descent method has been proved in this work. Also, the impact of the regularization for gradient descent method has been analyzed.

Strengths

The motivation of this work is clear and valid, also this work is well-organized. Meanwhile, this work is technically sound, where the proof and related analyses are provided, also some simulations are provided to further support the major results.

Weaknesses

- I have concern for the novelty or the contribution of this work. Rank-one matrix completion problem is the simplest problem for matrix completion problems. Also there have constraints for the noise assumption of the revealed entries in this paper. For such cases, there are many efficient methods to deal with, like alternating minimization or projected gradient descent method. For gradient descent method, there also have existing works which have proved its convergence. Though this work provided with relaxed conditions, such contribution may be limited for the optimization and machine learning community, let alone the real problems in industry. - The presentation for the proof of the major results can be further improved. For instance, the proof of Lemma 5.1 is separated into two parts at different places, it may be better to combine them together after finishing other proofs.

Questions

- Can you compare the major results about the rank-one matrix completion problem with the following works? https://arxiv.org/pdf/2008.04988.pdf https://proceedings.neurips.cc/paper/2020/file/f86890095c957e9b949d11d15f0d0cd5-Paper.pdf

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Please see comments above.

Thank you for your response

I thank the reviewers for their responses, which I read along with the other reviews and their respective responses. I maintain my score -- I think this paper makes a solid contribution, supported by well-carried-out proofs and a clear presentation, though having the downside of being restricted to rank one matrices.