Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a preconditioned gradient descent (PreGD) method for low rank matrix factorization.
In practice, the true rank r* of the matrix is unknown.
To be conservative, people usually choose an over-estimated r to start with.
However, in such case, the convergence of local search algorithms falls from a linear rate (r=r*) to a sublinear rate (r>r*).
The PreGD method proposed in this paper restores the linear convergence rate for the r>r* case.
Numerically, it is also found that the PreGD method works well in restoring the linear convergence for some variants of the problem.
main_review: The major contributions of this paper are twofold:
(1) the so called PreGD method;
(2) It is shown that PreGD restores the linear convergence for an over-estimated rank.

General Comments:

(1) The PreGD method, in my opinion, is not surprising, since it is quite natural to impose a regularizer \eta to cure the ill-conditioning for the over-estimated case. In addition, in practice, after a few iterations of GD, the true rank r* can be revealed from the SVD of the current estimation of X, under the assumption that lambda_{r*}(M*) is larger than the noise. So, one may simply run GD for a few iterations with an overestimated rank at the beginning stage, then reveal the true rank r*, after that, continue to run GD with the true rank. So, the value of PreGD in practice is not significant.

(2) The major contribution of this paper is (2) -- the theoretical analysis. The major results (corollary 5, Theorems 7 and 8) are all established under the assumption that a good initial guess of X is obtained from spectral initialization such that (17) holds. Let us consider the case when lambda_{r*} is small. The smaller lambda_{r*}, the more samples are needed to ensure (17) (by proposition 6). However, when M* has a low numerical rank that is much smaller than the true rank, the condition on m in proposition 6 will be too restrictive. Note that the overestimated rank case is quite similar to the low numerical rank case, I believe the results in this paper can be generalized to deal with the low numerical case, the term lambda_{r*}(M*)  in the  lower bound for m in proposition 6 will be replaced by some other eigenvalue of M* larger than a threshold.

(3) Figure 2, why the error for PreGD stagnates? Is it because of the noise? This is unclear from the context. 


Minor comments:

Some tyros need to be fixed, e.g.,

Line 227, equation (16), a full stop is missing.

Line 233, Lemma 4 —> Theorem 4 ?

Line 237, theorem 5 —> corollary 5 ?


limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of (noisy) nonconvex matrix factorization. The authors proposed an algorithm PrecGD that accommodates to over-parameterization and ill-conditioned ground truth.
main_review: Strengths:
1. The paper proposes a novel algorithm that performs well in numerical experiments, accompanied with solid theoretical guarantees.
2. The paper provides detailed high-level ideas and intuitions of their theory, which is helpful for those interested in their proof technique.

Weakness / comments:
1. The writing of this paper is not clear. Taking Section 5-6 as an example, I think it would be better to have a Section only presenting main results (Corollary 5, Proposition 6, Theorem 8), and this section should be self-contained. The intuitions / high-level ideas and the proof outlines can be deferred to earlier / later sections. The current version makes it difficult for readers to read the main result like Corollary 5 because necessary definitions required to understand Corollary 5 is spread out across the lengthy Section 5.
2. The definition of $\sigma$ first appeared in Theorem 7, but is already used in Proposition 6 and earlier in the main text. A definition is necessary before using this quantity.
3. It seems that Theorem 7 allows the noise level $\sigma$ to be arbitrarily large. I am skeptical about this as prior literature on matrix sensing usually prohibits the noise level from being too large, which usually reads $\sigma\sqrt{n/m}<<1$ under the setting of the current paper. 
4. How to obtain an approximation of the variance in Theorem 8? What is the order of $\mathcal{E}_{var}$ in (21) under this approximation method? How does this quantity compared with two other quantities in (21)?
5. If I understand the remarks under Theorem 8 correctly, when the sample size $m$ is large, the estimation error rate becomes sub-optimal. This is quite strange as large sample size, or large SNR, ususally makes the problem easier. Could you explain more details on why you can get an optimal rate when SNR is small, but fail to do so when SNR is large?
6. I think maybe it is possible to estimate the rank precisely under the setting of Proposition 6. In that case, we no longer need to over-parameterize the model. Is that correct or not?

Typos:
Theorem 4 is sometimes cited as "Lemma 4".
limitations_and_societal_impact: This is a theoretical work and I think there is no potential societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors consider low-rank matrix recovery problems, where the $n\times n$ matrix variable $M$ is factorized as $M=XX^T$, for some $X$ of size $n\times r$, with $r\ll n$. It is known from previous work that, although they are typically non-convex, these problems can oftentimes be solved through simple gradient descent over $X$, applied to a suitable loss function.

However, gradient descent tends to converge very slowly when either the ground true matrix is ill-conditioned, or the problem is overparameterized (that is, $r$ is strictly larger than the rank of the ground true matrix). In Reference [11], Tong, Ma and Chi have proposed a gradient preconditioner which solves the slow convergence issue when it is due to ill-conditioning. However, the method does not work when the problem is overparameterized.

In this article, the authors propose a refined preconditioner, which accommodates both ill-conditioning and overparameterization. In the particular setting of RIP matrix sensing with least-squares cost, they show that, with this preconditioner, gradient descent converges linearly in a neighborhood of the solution, up to the unavoidable statistical error.
main_review: I liked this article.
* It is well-written and pleasant to read.
* I did unfortunately not find the time to read all proofs, but I read everything related to the noiseless case (until page 22 of the supplementary material), and found no issue.
* The subject of the article is important: slow convergence of gradient descent in overparameterized settings is a significant obstacle for successfully using Burer-Monteiro methods in practice. Proposing an algorithm which is capable of overcoming this issue is therefore, in my opinion, a very valuable contribution, although its significance is limited by the fact that it is unclear to me whether the algorithm applies to other problems than RIP matrix sensing (see Remark 1 below).
* The principle of the algorithm looks quite simple (the main idea is to add a very classical regularizer to the ScaledGD preconditioner), but proving that it works is rather involved.

I have the following points of criticism.
1. The fact that the damping parameter must satisfy Equation (1) looks like a rather strong constraint. The article explains how to find $\eta_k$ satisfying this equation in the case of RIP matrix sensing, but RIP matrix sensing is a rather particular problem. I think it would be important to discuss whether this constraint prevents the algorithm from being applicable to other problems (which would significantly reduce its interest), or whether (and how) it can be overcome.
2. Some clarifications in the setting would be welcome. In particular, the assumptions on the noise $\epsilon$ should be explicitely stated at the beginning (otherwise, it is difficult to understand Proposition 6, for instance). I also did not find in the article the assumption $||A_i|| \lesssim \sqrt{n}$ used in the proof of Lemma 17.
3. It seems to me that the proof of Lemma 14 can be significantly simplified (see the end of the review for a proposition of a simpler proof).
4. I find Section 7 (Numerical experiments) a bit too short and confusing.
   * Why did the authors choose the setting of their experiment as in Example 12 of reference [13]? The corresponding data matrices are very peculiar.
   * A single example (although three different cost functions are considered, the underlying sensing operator is the same in each case), moreover in very small dimension, is not enough to establish that PrecGD works better than GD and ScaledGD.
   * It seems that PrecGD stagnates: the error does not go to zero. This is especially visible on the figures of the first column. What happens?
   * The experiment entangles three sources of difficulty: the ill-conditioning of the ground truth, the over-parameterization and the non-smoothness of the objective function. As a consequence, it is difficult to tell what exactly makes GD and ScaledGD fail or converge slowly. The fact that the figures in the first and second row of Figure 2 are quite similar gives the impression that the issues encountered by ScaledGD are not caused by overparameterization. Therefore, it does not illustrate the main message of the article (which is that PrecGD works better than ScaledGD when the problem is overparameterized).
   * If PrecGD is able to successfully handle non-smooth objectives whereas GD and ScaledGD fail, this is very interesting, but also a bit mysterious. Would it be possible to provide at least an intuitive explanation?
5. There are many typos in Appendix D.1. I recommend proofreading this subsection.

In addition, I have the following minor remarks.
* Line 27: "exists" $\to$ "exist"?
* Line 59: "suggests" $\to$ "suggest"
* Line 89: "logarithimic" $\to$ "logarithmic"
* Line 90: space missing before "$\lambda_1$"
* Line 110: $\sigma$ has not been previously defined.
* The assertion at lines 118-119 is not correct. From my understanding of [31], the strict saddle property also holds in the over-parameterized regime. Indeed, Theorem 1.2 of [31] shows that, even in the over-parameterized regime, if the RIP constant is smaller than some threshold, then for any non globally optimal $X$, either $\nabla f(X)\ne 0$ or $\nabla^2 f(X)\not\succeq 0$, which is to say that all non-optimal points have a descent direction.
* Equation (4): "$f^*=\min f(X)$" $\to$ "$f^*=\min f$" or "$f^*=\min_X f(X)$".
* Equation after line 164: I think there should be a factor "$2$" before "$\alpha$".
* Line 165: the value of $f(X_{k+1})$ is not correct.
* Line 184: "forces" $\to$ "force".
* Line 188: "$\nabla f(X)(X^TX+\eta I)$" $\to$ "$\nabla f(X)(X^TX+\eta I)^{-1}$"
* Lines 196 and 531, and Equation (32): "$\eta$" $\to$ "$\eta I$".
* Equation (25): there should be no point at the end.
* Line 208: "the the" $\to$ "the".
* Line 265: "Candes" $\to$ "Candès"; "any other estimator" $\to$ "any estimator"?
* Line 289: "$f(X)$" $\to$ "$f(X_k)$".
* Equation (35): I think there should be no sum over $i$.
* Between Lemmas 12 and 13: in my opinion, it should be explicitely said at the beginning that this is a high-level description of the proof, not a rigorous proof. In addition, this high-level description presents several issues because of which I could not understand it:
  * Equation after line 583: I think the right-hand side is not correct (a scalar product is missing).
  * Equation (37): the inequality is not correct. First, there is no reason why $\sum_{i=k+1}^r \lambda_i^2(X^TX)$ should be smaller than $\lambda_{k+1}^2(X^TX)$. Second, Lemma 13 does not prove that $||Z^T(I-U_kU_k^T)Z||_F \lesssim ||E||_F^2$: it proves that $||Z^T(I-U_kU_k^T)Z||_F \lesssim ||E||_F$ (without the square).
  * If $||E||\_F^2 \geq 1 $, then Equation (37) does not imply that $\lambda_{k+1}(X^TX)$ is large whenever $\sin(\theta_k)$ is large.
  * Line 593: what is $T_1$?
* Equations (44) and (45): "$\lambda_{k+1}^2(X^TX)$" should be "$\lambda_{k+1}(X^TX)$".
* I found it a bit difficult to understand the induction in the proof of Theorem 4; I recommend stating the inductive assumption explicitely.
* Line 625: "where we prove" $\to$ "that is, we prove"?
* Second line of Equation (46): there is a factor $2$ missing.
* Lines 641-642: what does "the rank can be verified" mean?
* Line 645: the definition of $d$ is not correct (there is a mismatch between the dimensions of $\Sigma_k^{-1}$ and the size of $e$); it should be $d=V_k\Sigma_k^{-1}U_k^T$.
* Problem after line 673, first line: there should be parentheses around $(1+\delta)\mathop{Tr}(V)-(1-\delta)\mathop{Tr}(U)$.
* Line 674: I think that there should be a division by $||w||$ in the equality which defines $M(w)$.
* Problem after line 674, first line: there should be no "$(1+\delta)$".
* Line 679: there are traces missing.
* Line 691: if we assume that $k=r^*$, then $X_1,Z_1$ belong to $\mathbb{R}^{r\_* \times r\_* }$.
* Equation after line 724: in the second line, I think the "$||Z||\_F$" should be replaced with "$||Z_2|\|_F$" (without this replacement the second inequality has no chance to hold when $Z_2=0$).

Simpler proof of Lemma 14: Let $Y$ maximize the right-hand side of Equation (47). Let $W$ be the matrix corresponding to the orthogonal projection onto $\mathrm{Range}(X)+\mathrm{Range}(Z)$. If we set $\tilde Y=W Y$, it holds that
$$\langle X\tilde Y^T + \tilde Y X^T, E\rangle
 = \langle X Y^T, E W\rangle + \langle Y X^T, W E\rangle
 = \langle X Y^T + Y X^T, E\rangle$$.
On the other hand,
$$ ||X\tilde Y^T+\tilde Y X^T||_F = ||W (XY^T+YX^T) W||_F \leq ||XY^T+YX^T||_F$$
and $||\tilde Y||_P = ||WYP||_F \leq ||YP||_F = ||Y||_P\leq 1$.
This allows to show that $\tilde Y$ also maximizes the right-hand side of Equation (47).

Since $\mathrm{Range}(\tilde Y)\subset \mathrm{Range}(X)+\mathrm{Range}(Z)$, the $(2r,\delta)$-RIP implies
$$
|\langle \mathcal{A}(X\tilde Y^T+\tilde Y X^T),\mathcal{A}(E)\rangle -
\langle X\tilde Y^T+\tilde Y X^T,E\rangle| \leq
\delta ||X \tilde Y^T + \tilde Y X^T||\\,||E||.
$$
As a consequence,
$$ \begin{align*}
||\nabla f(X)||_{P^*}
& = \underset{||Y||\_P \leq 1}{\max} \langle \mathcal{A}(XY^T+YX^T),\mathcal{A}(E)\rangle \\\\
& \geq \langle \mathcal{A}(X\tilde Y^T+\tilde Y X^T),\mathcal{A}(E)\rangle \\\\
& \geq \langle X\tilde Y^T+\tilde Y X^T,E\rangle - \delta ||X \tilde Y^T + \tilde Y X^T||\\,||E|| \\\\
& = \underset{||Y||_P \leq 1}{\max} \langle X Y^T+ Y X^T,E\rangle - \delta ||X Y^T + Y X^T||\\,||E||.
\end{align*}$$

**Added after author feedback**

I thank the authors for adequately addressing my concerns, as well as for the discussion we had during the discussion period. I have increased my grade and hope the article will be accepted.
limitations_and_societal_impact: Not applicable to this article.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the problem of matrix sensing in the over-parameterized setting where the rank of the estimator is larger than that of the ground truth. A new algorithm called preconditioned gradient descent is proposed, and its performance is discussed both theoretically and numerically.
main_review: Overall, this paper is well-written and easy to read. The literature review is comprehensive, and the discussion about the limitation of prior art as well as the intuition of the proposed algorithm is very helpful.

My main concern is about the theoretical guarantee in the noisy setting (Theorem 8). The current error bound is not minimax optimal. It seems quite crude because authors simply adds up the three error terms that appear in the proof, and the sub-optimality might be attributed to the theoretical analysis.  It would improve the quality if authors can improve the error bound.

Typo:
Theorem 5 in Line 237 should be Corollary 5.


limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper proposes regularized scaled gradient descent for low-rank matrix factorization. Particularly, it considers the scenarios where the model parameter r is an overestimation of the true rank r*. This is quite a common scenario. Though the scaling (and its regularized variant) is well-known (see papers from 2013 onwards based on numerical analysis or Riemannian metric selection), a deeper convergence analysis was missing that the paper presents. Though experiments are adequate for showing the good performance, some comparisons on real data would have been nice. Nevertheless, the reviewers agree that the paper has useful insights for NeurIPS community. 


Decision: Accept (Poster)