Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the nonconvex approach to the positive semidefinite (PSD)
matrix sensing problem, a much-studied model problem for tractable nonconvex
optimization in the literature. Specifically, they consider the
"overparameterized" version of this problem: there is an unknown ground truth
factor matrix $X \in \mathbb{R}^{n \times r_{\star}}$ which one observes through
linear measurements $\mathcal{A}(X X^T) \in \mathbb{R}^m$; one seeks to find
$X$ by minimizing the nonconvex objective $U \mapsto (1/4) \\| \mathcal{A} (
UU^T - XX^T) \\|^2$ ($\ell^2$ norm) using randomly-initialized gradient descent
from initialization $\alpha U \in \mathbb{R}^{n \times r}$ with $r \geq
r_{\star}$,  where $\alpha > 0$ is a small scale parameter (e.g. inverse
polynomial in $n$) and $U$ is an i.i.d. gaussian matrix with entries of
suitable variance. The authors analyze this problem in the setting where the
measurement operator $\mathcal{A}$ has the RIP (e.g. enough gaussian
measurements) and the general setting of $r \geq r_{\star}$; they prove that
gradient descent recovers the true factor matrix $X$ up to symmetry to any
desired accuracy (measured in frobenius norm), where the precision is improved
by decreasing the magnitude of $\alpha$ (at the cost of a logarithmic gain in
the number of gradient descent iterations required) and with constants that
depend on the condition number of $X$ (Theorem 3.3). The approach to the proof
is claimed as novel, with a connection made between overparameterization in
this model and the common spectral initialization schemes in use, and synthetic
experiments are presented that support the authors' separation of their
approach to the convergence proof into distinct phases, and the predictions of
their main theorem. 


main_review: ## Summary wrt rating

The paper provides new results on nonconvex gradient descent for PSD matrix
sensing under an RIP property in the setting where the problem is
overparameterized, and the proof techniques seem to reveal novel qualitative
insights into the behavior of the gradient descent algorithm in this
overparameterized setting. Here, I found the simple experiments in Figures 4
and 5 to be quite helpful illustrations. In a similar way, these results also
seem to constitute a valuable contribution to the literature on provable
guarantees for generic optimization methods (randomly initialized gradient
descent) on nonconvex problems. My rating reflects some issues with the paper,
mostly around context wrt the literature and organization. Specifically,
the authors have submitted the "full version" of the paper as the supplementary
material -- I don't see anything wrong with this from a policy perspective, but
they seem to have not prepared the "9 page" version of this work very
carefully, to the extent that there are a number of omissions of highly related
work in both the introduction/motivation and in the presentation of the results
on overparameterized matrix sensing. This has the effect of making it seem like
the authors are unaware of these works, and seems to make it near-impossible to
understand the precise contributions of the authors (wrt generality of their
result; sharpness of the rates; and insights in the proofs) relative to prior
art as someone not actively working on matrix sensing/matrix completion problems. I will discuss these issues in detail below; I would expect to be able to
raise my rating given their satisfactory resolution.

## Context and contributions

It seems to me that the concrete contributions of the authors are: new results
for overparameterized PSD matrix sensing with RIP (global convergence; large
$r$ allowed; possibly new rates); new qualitative insights into the behavior of
randomly-initialized gradient descent on this problem (with small
initialization); a novel contribution to the literature on guarantees for
randomly-initialized gradient methods (i.e. saddle-avoidance-free) on
nonconvex problems. I find it somewhat unclear how most of the motivation in
the introduction connects to these contributions. I also find it challenging to
appreciate these contributions from the current version of the submission due
to omissions of comparisons to relevant prior works. I will give more details
below.

- The paper seems to be motivated from the idea that in *general ML theory
  settings* with overparameterized models, there is a need to understand the
  issues of "small random initialization" and generalization. I find this claim
  incompletely justified here -- for example, there are a number of inverse
  problems in the nonconvex optimization literature in which it is natural to
  formulate the problem with a compact constraint set, where there is no natural
  notion of "small initialization" (e.g. [2-5] below), and one instead uses a
  random initialization or a data-driven initialization; similarly in practical
  deep learning settings it seems like the standard initialization strategies
  (e.g. "He initialization", etc.) lead to matrices with $\Theta(1)$
  operator norms, so it is not clear to me how these are "small". If the
  authors want to motivate their work in this way (e.g. sentence at line 39),
  it would seem appropriate to provide additional justification here.
- The dichotomy outlined in the paragraph from lines 42-61 omits a significant
  body of work on understanding structures in practical problems that enable
  randomly-initialized gradient descent to succeed: for example, [1, 6-8] below
  are relevant here. One could also argue that NTK analyses of deep learning
  problems where generalization is established fall into this category, e.g.
  [9-10] below, although these approaches do not proceed by a geometric
  analysis. 
- In a similar vein, I do not understand why the authors have neglected to
  discuss prior art on overparameterized PSD matrix sensing (including [1, 6,
  8] below) in the introduction and related work, given its importance in
  establishing the novelty of the authors' contributions. Footnote 1 seems
  dubious to me in this connection.
- The paragraph from lines 62-71 seems to be only tenuously related to the
  paper's PSD matrix sensing setting. In particular, I had the impression that
  "beyond-NTK" analyses of neural network training in the teacher-student setting were
  more similar to high-order tensor decomposition problems than matrix sensing
  under RIP (e.g. [11]), in particular requiring a specialized initialization
  to work with sharp rates; and in general, these approaches seem to be
  unsuitable for extension to non-shallow neural networks of the kind used in
  practice (relevant to a "guiding principle for practitioners" in line 71). 
- In section 3, outside of a discussion of the sample complexity, the authors compare their result only to the cited reference
  [20], which applies to a completely different initialization scheme. The
  authors should compare here to relevant prior works in order to demonstrate
  the novelty of their contributions: i.e. [1] below (this work seems extremely
  relevant, and even offers a precedent for the authors' ideas about "small
  random initialization" with $\alpha$) and [6] below, plus other relevant
  results. I would also think it appropriate, where possible, to compare to the
  proof techniques employed in these works and point out any novelties of the
  authors' approach in this context (e.g. specifically with regards to the
  "small initialization is akin to spectral learning" claim, to demonstrate its
  novelty in the authors' work -- naively, it seems to me that an idea similar to this is employed in [6], and boils down to gradient descent bringing the iterates into the 'basin of attraction' of good solutions without the need for targeted initialization. The same principle is at play in [5, 7] below).

Because of the amount of omitted discussion of relevant works in the PSD matrix
sensing / nonconvex optimization literature, and the lack of convincing
connections between the overparameterized PSD matrix sensing problem and
general ML theory problems (e.g. deep learning theory, "small random
initialization" ubiquity), it would seem to me to be most appropriate to
replace the discussion of these latter issues in the intro with a more detailed
discussion of the former. I also note that there seems to be a lot of
additional space available by reducing figures later in the paper to fit all
panels onto one line, instead of two.  


## References mentioned above

[1] https://arxiv.org/abs/1712.09203

[2] http://arxiv.org/abs/1206.5882

[3] https://arxiv.org/abs/1511.03607

[4] https://arxiv.org/abs/1906.02435

[5] https://arxiv.org/abs/1901.00256

[6] https://link.springer.com/article/10.1007/s10107-019-01363-6

[7] https://arxiv.org/abs/1809.10313

[8] https://arxiv.org/abs/2012.15467

[9] https://openreview.net/forum?id=O-6Pm_d_Q-

[10] https://openreview.net/forum?id=fgd7we_uZa6

[11] https://arxiv.org/abs/2102.02410

[12] https://arxiv.org/abs/2006.08857

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies both the optimization and the generalization of the non-convex overparameterized low-rank matrix reconstruction problem, showing that the small (random) initialization plays an important role. In detail, they divided the dynamic into three phases, in the first phase the eigenspace gradually aligns with the ground truth; the second phase is the saddle avoidance/refinement phase; and the last phase is the local convergence period.
main_review: This paper is very solid, extending previous Li et al. [1]'s result in the case that the overparameterized model U is $d*r'$ instead of $d*d$. However, this result is not interesting now. The small initialization has been well studied in different areas (e.g. low rank matrix recovery, tensor decomposition, linear neural network and so on). Also, compared to Li et al. [1]'s result, their result seems to be only a marginal improvement. The detailed comments are provided as following:
1. Why we need to have the first two phases? Is it because some technical reason? For me there is only one phase: the eigenspace aligns to the ground truth and the minimum eigenvalue converges to the ground truth. Also, it is quite confusing for me that why the second phase named "saddle avoidance/refinement phase". I cannot see any intuition why and how GD avoid this from the main body.
2. From Figure 2, the distance measure between the two eigenspaces will decrease first and then increase again. This is very strange to me. My guess is that this comes from the "ground truth" you chosen, $A^*A(XX')$ instead of $XX'$. Will this re-increasing phenomenon effect the proof? Or what if directly measure the distance compared to $XX'$.
3. As you mentioned in line 236-237, the behavior of the plots do not change. Do you running different initialization or choose different Gaussian (symmetric) measurement matrices? For me, it is quite strange that the behaviors with different random seed are exactly the same.
4. It seems this result also needs early stopping. Is there any way to show that the generalization won't blow up again like in [2]?

[1] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2–47. PMLR, 2018.
[2] Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of over-parameterized matrix sensing. arXiv preprint arXiv:2102.02756, 2021.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper takes an initial step to explain why small random initialization followed by a few iterations gradient descent on non-convex optimization can often converge to a global minimum point with also good generalization ability. Specifically, this paper focuses on low-rank matrix recovery, a highly non-convex optimization problem with spurious local optimal points, and shows that: (1) This method has similar behavior to the popular spectral methods with three phases—a spectral or alignment phase, a saddle avoidance/refinement phase, and a local refinement phase. (2) Larger parameter space tends to have a larger spectral bias which helps convergence to a global optimal point with also smaller generalization error. 
main_review: Originality: This work is original as it explains a phenomenon that is not explained well before. 

Quality: The submission is technically sound. The claims are well supported by theoretical analysis and experimental results. Appropriate methods are used. This is a complete work. Both the strengths and weaknesses of their work are explained.

Clarity: The submission is generally clear and well organized, but some points need explanation as pointed out in advice and questions below. 

Significance: This paper takes an initial and important step to explain why small random initialization followed by a few iterations gradient descent on non-convex optimization can often converge to a global minimum point with also good generalization ability. This work only focuses on the low-rank matrix reconstruction problem and an important future direction is to extend to other non-convex optimization problems, so I think this work will perhaps be cited. 

Advice and questions: 
(1) What is the power method? You may give more explanation or citations. 

(2) Typo in the last paragraph of Section 1: Use “as long as” in “This holds as long the measurement operator obeys a popular restricted isometry property”. 

(3) In Section 2, you might add application examples of (1) and explain the meanings of $y_i$, $A_i$, $XX^{\top}$ in the examples. You may also list some applications in the introduction. 

(4) What does $\mathcal{A}^*$ mean in the gradient descent equation below eq. (2)? Also, since $X$ is unknown while $y_i$ is known, why not using $y_i$ instead of $X$ in the update rule? 

(5) You put the case of $r\ge 2r_*$ to the main text and $r\ge r_*$ including two special cases into the appendix. Why is the former more important? 

(6) In Theorem 3.3, can the probability $1-Ce^{-\widetilde{c}r}$ get arbitrarily close to 1? Does it rely on $\alpha$? 

(7) How does eq. (6) relate to the equation between eqs. (4) and (5)? For example, does eq. (6) imply that equation? You might well explain that around eq. (6). 

(8) In Phase II, the $r_*$-th eigenvalues will align. How does that relate to saddle avoidance? Also, $\alpha\propto \sigma_{r_*}(U_0) \ll \mathcal{O}[\sigma_{\min}(X)]$ yes? If so, I did not see something like $\alpha\le \mathcal{O}[\sigma_{\min}(X)]$ in eq. (4). Could you explain? 

(9) What’s the value of r for Figure 2? 

(10) You said “We note that while all experimental depictions are based on a single trial, in line with the NeuRIPS guidelines we have drawn these curves multiple times (not depicted) and the behavior of the plots do not change. ” Have you tried multiple initializations of U? Do they have almost overlapping curves? 

(11) In your paragraph beginning with “Evolution of the test error and the refinement phase”, eq. (6) might also be used to explain the result. 

(12) In Figure 3, you might also add the plot of computation complexity (iteration number $\times$ number of flops or involved entries per iteration) VS r. This may help us select proper r in practice I think.  

(13) In Figure 4, you may also add the plot of the number of iterations/computation complexity VS alpha. Hopefully the iteration number is proportional to $\ln(1/\alpha)$. Also, there is a typo in the caption—“relative”. 

(14) You could add a sentence like “We depict the results in Figure 5.” to the final paragraph.

(15) For Figure 5b, is the initial point already close to a local minimum point? (computing gradient norm might be helpful) How about trying more initial points with alpha=1? 
limitations_and_societal_impact: This work points out its limitation that the sample complexity has sub-optimal dependence on $r_*$. Also, I think this work could be generalized into more non-convex optimization problems in the future. This work simply points out that “As with other technologies such insights may potentially also be used nefariously. ”
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the role of small random initialization followed by gradient descent in the setting of low-rank matrix sensing. Authors show that the trajectory of the gradient descent from small random initialization behaves similarly as spectral initialization in the initial stage, and then moves from degenerate saddle points and converges to the ground truth. Numerical experiments are provided to validate the theory.
main_review: The paper is well-written and easy to read. It considers a basic problem, and shows interesting results about the role of random initialization followed by gradient descent. The literature review is comprehensive. Therefore, I'd like to see it accepted.

Below are some minor suggestions/questions:
1. It would be better to provide more detailed informal high-level sketches for the last two stages in Section 4.
2. For the over-parameterized case, it seems that the iterate need to be singular in order for the matrix estimator to be close to the ground truth. Does this affect the convergence rate of vanilla gradient descent? It might be better to add a few discussions.

Typo:
A transpose seems to be missing in equation (1)
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper provides and analyzes a setting where small random initialization has a certain implicit spectral bias.  Reviewers are positive and I recommend acceptance.  That said, the reviewers had many detailed concerns, which led to extensive feedback discussions as below; I request the authors address these points carefully in their revisions.
Decision: Accept (Poster)