Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of decomposing an m x n matrix of rank r into the product of an m x r matrix and an r x n matrix. While various methods exits for solving this problem, the goal of the paper is to provide theoretical guarantees for gradient descent with random initialization and fixed learning rate. The main result gives sufficient conditions, in terms of the dimensions (m,n), the rank r, and the condition number of the underlying matrix, under which the gradient descent method converges to a global optimum with a polynomial rate. 

This work improves upon prior work which either: focused only the symmetric setting, does not give convergence results, or considered different initializations. The analysis and the conditions are based on two different stages. In the first stages,  the iterates converge slowly to get to a point `````near to an optimal solution. In the second stage, the iterate convergence quickly. 

No numerical results are provided. 
main_review: The authors do a good job of describing their problem and the contribution of the results in the view of prior work. The main results is clearly explained and the high level idea behind the proof a conveyed. The more technical parts are a bit more difficult for me to follow, in part because the transition from continuous time to discrete was not clear to me, and also the convention of removing the time indices from the expressions made things more difficult for me to parse.

I agree with the authors that the main contribution of this paper is the analysis of the method. Indeed, other efficient solutions exist and similar results have been proven for the symmetric setting. Unfortunately, it is difficult for me to describe that precisely the new ideas in the analysis are. This is partly because I am not super familiar with the immediate prior work I do not know which of the steps are novel and which are standard. The authors could do a better job of making this distinction for readers such as myself.

While there is certainly a great deal of work in the literature focusing on variations of this low-rank factorization problem (both in the symmetric and non symmetric settings) it seems to me that it would be much more practically interesting to consider the setting where the matrix is only approximately low rank. I wonder to what extent the insights and analysis from the current line of work extend to this setting. 

 more comments: 

- The distinction between sigma(.) as a function (applied to a matrix) as opposed to the singular values of a specific matrix (namely Sigma) was confusing, especially with respect to the statement of Lemma 3.2.

- The wording in footnote 5 could be made more precise. 

- The matrices and A and B and sort-of-but-not-really defined before they are used, and then they are defined later.





limitations_and_societal_impact: The assumptions for the theoretical results are clearly stated. Given the theoretical nature of this work I do not see the need for any more discussion on societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper shows the global convergence of the matrix factorization problem with geometric convergence speed.
main_review: I think it is a well-written paper. In prior work, while we know the landscape of matrix factorization problem is nice, all proofs (that I know of) for showing global convergences require some artificial modifications on the algorithm, e.g. additional regularizer. It is nice to have proof that does not need those artificial changes. Furthermore, the paper also reveals that while the eigenvalue of U and V may not behave well, the eigenvalues of A=(U+V)/2 and B=(U-V)/2 do behave well. Hence, this paper not only gives a cleaner proof but also adds some insights to the matrix factorization problem. 
Looking at the submission history, I think proving geometric convergence is important to the problem (otherwise it still does not fully explain the good performance of the standard grandient descent in practice) and I am glad that the authors have proved it in this new submission.
limitations_and_societal_impact: The paper confirms the well-known observation with theoretical proof that the standard gradient descent algorithm finds the global optimum for the matrix factorization problem. I do not think there is any negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the performance of the gradient descent (GD) algorithm for a prototypical instance of the asymmetric matrix factorization (AMF) problem. The main result of the paper is establishing the polynomial convergence of GD for an ideal and noiseless, but unregularized instance of the asymmetric matrix factorization. To the best of my knowledge, the technical contributions of the paper are sound and correct.
main_review: While I believe that the technical contribution of the paper is novel and clear, I do have several comments:

1. My major comment is that the proposed analysis of this work seem to only work for an idealized objective function. Indeed, the practical instances of the MF problems mostly rely on linear measurements of the form $y_i = trace(A_i’ X)$. Indeed, the considered loss function in this paper corresponds to the ideal population loss function, where the number of available samples approach infinity (or equivalently, the so-called RIP condition holds with constant zero). This would not pose any issue if the authors had clearly explained how their proposed technique can be extended beyond this synthetic variant of the problem. Based on my understanding, and unlike the authors’ claim, I don’t think their provided technique can be directly used in more general instances of AMF because these problems are not diagonalizable via a change of basis (i.e., Eq. 4 and 5) when the measurements are of the form $y_i = trace(A_i’ X)$. The authors should support their claim by explaining how their proposed technique can be extended to other practical instances of AMF, as well as “other related non-convex problems” (as claimed in the abstract).

2. While I think relaxing the requirement for regularization is one of the main contributions of this work, I’d like to point out that another reason for such regularization is to remove optimal solutions at infinity. Indeed, without a regularizer that balances the norm of the components, globally optimal solutions exist at infinity. On the other hand, Theorem 1.1 and Corollary 1.2 only guarantee the convergence of the objective function, and do not provide any bound on the values of the obtained solution. Is it possible to show that $U_t$ and $V_t$ do not diverge if we run the algorithm for a longer time?

3. Finally, it appears to me that the paper is not polished, and it suffers from numerous grammatical and notational mistakes. While these mistakes are mostly minor and can be fixed, they severely undermine the readability of the paper. For instance, some notations are used before their formal definitions (e.g. A and B in page 4). 


===================================================
After rebuttal, the reviewers have successfully addressed my comments. I strongly encourage the authors to include their suggested method for handling the general linear measurements to the revised paper.  

limitations_and_societal_impact: The authors are encouraged to address the above-mentioned comments.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper provides a proof of polynomial convergence rate whp of randomly initialized gradient descent on the non-convex problem of matrix factorization with the Frobenius norm. Notably, this problem was considered in previous works and only weaker results have been shown, e.g. no convergence rate, or polynomial convergence rate with the addition of noise and regularization. 
main_review: The related work section provides appropriate context for understanding the problem and the paper's contribution.
Overall, the paper is very well structured for guiding the reader through the verification of the proof. The authors did a great job with how cleanly and clearly they broke down such a technically heavy proof into individual parts. I was able to follow most of the proof, and did not find any errors. (I assume in line 459, in the supplementary material, the \sqrt{d^3} in the denominator is meant to be \sqrt{d}, as this matches the original definition of epsilon and still works in the following lines)

There are some minor typos/grammatical errors but they do not detract from understanding.

In terms of the proof itself, I do not feel like I have a good intuitive understanding of what the proof is doing, more specifically what exactly is the main idea behind it, if there is one. I don't mean to say it is technically lacking, rather it is much the opposite as I alluded to above; there is a lot of careful balancing of terms and algebraic manipulation that leverages the specific choices of the noise variance and learning rate in multiple ways, which seems extremely nontrivial to come up with. Suffice it to say, I am not surprised why there were several works on this problem before and apparently none of them were able to solve it without weakening the result in some way. I was not able to see how the PL inequality the authors mentioned is relevant to this specific problem, though maybe that is due to a lack of experience in optimization literature on my part. It just seems like the authors wait for certain quantities to reach certain values, and then once that point is reached a decay factor can be upper bounded and a bunch of perturbation terms can be absorbed/canceled. Again, finding the right terms to pay attention to like the authors did seems extremely nontrivial.  On a more high level aspect of the proof, I found the reduction to the diagonal case and the splitting of the U,V matrices into U/J, V/K very nice. 

Perhaps the intuition of the proof machinery could be better conveyed, but because of the significance and difficulty of the problem the authors solved, as of now I rate this paper between an 8 and a 9. To me it clearly deserves to be published at a NeuRIPs-tier conference, but the problem it solves maybe seems like a bit of a toy problem, despite the clear interest in it by the theoretical community demonstrated by previous work. It was not clear whether the result of the paper has any bearing on or could have its proof be extended to something outside of this specific matrix factorization problem.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: We thank the authors for this submission. Overall, the paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate.

The paper well-motivates the approach. The authors have provided extensive responses to the concerns raised (matrix sensing connection, convergence of Ut, Vt, better presentation of results, etc) and the AC + reviewers really thank them for their effort. Overall, the new results obtained during the rebuttal definitely improve the quality of the paper. We all believe that the inclusion of these results during the rebuttal period is something that does not heavily change the message of this paper. 

There was discussion and consensus that this work is interesting. Having in mind issues/concerns raised by the reviewers, the main points of reviewers during further discussion were that this paper deserves publication, given the promised fixes by the authors during the discussion period. 
Decision: Accept (Poster)