Gradient descent for matrix factorization: Understanding large initialization

Thanks the reviewer for the valuable suggestions and questions. In this rebuttal, we will address them point by point. Due to the limitation of characters, we separate this rebuttal into two parts. The first one addresses the weakness section. The second one addresses the remaining questions.

Weakness

• The theoretical results in this paper are presented in a somewhat isolated manner, and it seems that then result for rank-2 is not even stated as an independent theorem. I suggest that the authors can briefly summarize the main results (for rank-2 and general ranks) in the introduction, before going into technical details.
  • Thanks for the reviewer’s suggestion. In our updated version, we summarize our results in a main theorem, Theorem 6, and an intuitive theorem, Theorem 1. We put the intuitive theorem in the introduction. We also move the visualization results and the intuitive ideas to the introduction. We move the analysis of rank-2 results to a later section called sketch of proof.
• The organization of Sec. 3 can probably be improved: although the title of this section is "challenges in examine general rank solutions", Sec. 3.1 is about local convergence and the remaining two subsections seem to discuss the challenges for large initialization, rather than for general ranks
  • Thanks for the reviewer’s suggestion. We have changed the structure for that section. We have made the local linear convergence a single section, emphasizing the usage of SNR in this application. Then we discuss the random initialization. We both review small random initialization and present the main theorem for large initialization. Explanations and comparisons are given in corresponding places. After this, we give a detailed sketch of proof.
• The "signal-noise-ratio" argument in this work looks different from existing works that also decompose the GD trajectory in the signal and noise term (e.g. [1,2] ), but the decomposition seems to be the same. I suggest that the authors can add more discussions about this difference to highlight the contribution of this paper.
  • Thanks for the reviewer’s suggestion. We have added more discussions in our updated version. Specifically, to employ the SNR analysis, we need a lower bound of the signal and an upper bound on the noise, both in terms of their previous iterations. These two bounds need to be related so that the ratio of SNR$_{t+1}$ by SNR$_t$ can be analyzed. The challenging part is to obtain two related upper and lower bounds. Previous literature does not provide SNR considerations so their upper and lower bounds are not applicable for our purpose. In addition, for the large initialization setting, our SNR analysis is even more novel, because we introduce new signal and noise terms.

Hope this addresses the reviewer's concerns regarding the weaknesses.

We would like to thank the reviewer for the valuable suggestions and questions again. In this part, we will address the remaining issues, including experiments, formulations, reference and typos.

• Experiment

• In the experimental example, how do we know if 0.5 N(0, 1/d) is a large initialization? Since d does not vary, what can we say? It would be better to have the experiment for several values of d and $\varpi$

  • We appreciate your attention to the details of our matrix factorization experiment. Theoretically, by the concentration results, the norm of $X_t$ is around 0.5. This is comparable to the largest eigenvalue 1 of $\Sigma$. Consequently, the higher order term $X_tX_t^\top X_t$ cannot be disregarded in the GD iterations. In this context, the theory of small initialization fails to account for the convergence behavior observed in GD.
  • Additionally, we add new experiments with varying d and $\varpi$ in the appendix. In particular, we choose d from 1000, 2000, 4000, and we take $\varpi$ from 0.001, 0.5, 2, and 10. Our findings show that if $\varpi$ is as large as 10 in this setting, the GD sequence will diverge. For the remaining three choices of $\varpi$, we can observe similar convergence behaviors of GD.

• The experimental example considers rank 2 matrix factorization which, though by nature different as the authors have explained, does not seem to far from rank 1 factorization (especially compared to the dimension 2000). It would highlight the goal of the paper better to use something like rank 10 matrix factorization here.

  • We appreciate your attention to the details of our matrix factorization experiment. Our experiment is designed to demonstrate our core ideas in an intuitive and visually interpretable manner. By using rank-two matrix factorization setting, selecting five noteworthy points, and comparing their heat plots, we could succinctly illustrate the intuitions of our analysis.
  • Additionally, we add new experiments to address the reviewer’s question. In the second experiment in our appendix, we examine the setting of fixed dimension d with varying rank r and $\varpi$. We let d=1000 and choose r from {2,6,10} and $\varpi$ from {0.001, 0.5, 2}. The error curves of GD are plotted for these different settings. We find that these results are consistent with the results we have presented before.

• Please provide more than one experiment in dimension 2. The analysis is incomplete without more proof that the results hold for varying r and d, fixed $\varpi$.

  • Thanks for the reviewer’s suggestion. In our updated version, we have provided additional experiments in the appendix. For rank-two matrix approximation, we vary both dimension d and the initial magnitude $\varpi$. Our results are consistent with the results we have presented.

• Formulation

• Incremental learning has many possible meanings, it would be nice to clarify it here.

  • Thank you for the suggestions. We have explained that in our context, incremental learning refers to the process where eigenvectors associated with larger eigenvalues are learned first.

• Same for "spectral method", I think the amount of details given in section 3.2 should be slightly increased.

  • We have explained the spectral method. It also means the power method. For these kinds of methods, the eigenvectors related to larger eigenvalues are learned first. Notably, $\sigma_r(U)$ increases faster than $\sigma_1(J)$.
  • We have extended the content of that section. We add more details on two aspects: the theoretical intuition and their assumptions on small initialization.

• P3 "because at the global minima"/"the set R contains all the global minima": it seems to me that there is a single global minima, the rank-truncated SVD of $\Sigma$. can the authors clarify?

  • The global minima refer to all $X$ such that $XX^\top=\Sigma_r.$ While $\Sigma_r$ is unique, there are multiple $X$ satisfying the equality. Since R is a set of X, it is more accurate to say that the set R contains all the global minima.

• First sentence of Section 3.3 is a repetition from above. Paragraph 4.1 consider replacing rank- by rank-2 for clarity (and all instances of  in that paragraph)

  • Yes, we have made all the modifications.

• Legend of Figure 1: "top three rows" are the first three rows?

  • Yes.

• Reference and Typos

  • We added the mentioned reference and revised the typos in our updated version.

If the reviewer has additional concerns, please feel free to let us know.

We thank the reviewer for the valuable suggestions and questions. In this rebuttal, we will address them point by point. Due to the limitation of characters, we separate this rebuttal into two parts. This part responds to the mathematics.

• Mathematics
• The paper claims to study large initialization, and that the first result with initialization in the region of Eq 10 is not satisfying…. However, the proof of the main result states "This is achievable if we use random initialization X0 = αN0 with a reasonably small constant α", which is not "large initialization".  must be small enough such that , so  depends on , and it's not so wild to think that  is a fraction of . Remark 4 seems to contradict that, highlighting that the theorem does not require , but the exposition is very confusing here (eg, Lemma 5 assumes that )
  • Sorry for the confusion here. In our updated version, we have removed all the confusion part. Specifically, for every results we display, we only require $\sigma_1(X_0)\leq1/\sqrt{3\eta}$ and correspondingly $\varpi\lesssim 1/\sqrt{\eta}$. All the subsequent results are then proved, rather than assumed. In addition, we emphasize that this requirement is rate-optimal because if $\sigma_1(X_0)$ is too large, then the GD sequence can simply diverge. A simple counterexample is when $\Sigma=0$ and $\sigma_1^2(X_0)\geq 3/\eta$. An inductive argument implies that $\sigma_1(X_{t+1})\geq 2\sigma_1(X_t)$ for all t, and thus $X_t$ diverges. We have added this example and explanation below Theorem 6 in our updated version.
  • We would also like to emphasize the difference between large initialization and small initialization. Large initialization means the norm of $X_0$ converges to a positive constant while small initialization means the norm of $X_0$ converges to zero. By concentration results, the norm of $X_0=\varpi N_0$ is O($\varpi$). Therefore, taking a positive constant $\varpi$ means the large initialization. In contrast, in previous literature that assumes small initialization, they require $\varpi$ to be as small as $\min(d^{-1/2},d^{-3\kappa^2})$, where $\kappa>1$ is the condition number. Therefore, there should be a significant difference between two settings.
• It is clear that Sigma can be assumed diagonal in problem 1 up to an orthogonal change of variable in  (because GD is equivariant to such a change of variable), but this deserves to be stated explicitly the first time this assumption is made (P2).
  • Yes. In our revised version, we have mentioned that such assumption is made without loss of generality, and explained the reason.
• $\sigma_1(u_{1,t})$ is just its norm, right? Same for $u_{k,t}K_{k,t}^\top$.
  • Yes. Both the norm notation and the singular value notation can be used. We chose the singular value notation for its consistency with other results in the paper.

Hi Reviewer BGNj, We are writing again in hopes that you will respond to our rebuttal and let us know your current concerns so that we could address them. For now, we believe we have addressed all the weaknesses you has mentioned. Specially,

• unclear dependency on initialization: $\varpi$ needs to be small;
  • we have demonstrated that our initialization condition is dimension-independent and rate-optimal; in particular, we only require $\varpi\lesssim 1/\sqrt{\eta}$, which is in sharp contrast to the previous 'small' requirements $\varpi\lesssim \min(d^{-1/2},d^{-3\kappa^2})$.
• unclear it it is required in the proof that $X_0\in S$
  • we have made it clear that we do not need this condition; if this is the point that you are concerned, then we have demonstrated that such condition can be completely removed; hope this could address the reviewer's concern.
• only one experiment, on rank 2 matrix approximation
  • we have added more experiments in the appendix; due to the limitation of pages, we remain a single experiment in the main text for illustrating our ideas.

Please let us know if you have any concerns so that we could further address them. We are looking forward to your reply!

We thank the reviewer for the valuable suggestions and questions. In this rebuttal, we will address them point by point.

• The presentation could be further improved
  • In our updated version, we have significantly improved our presentation by taking all reviewers’ suggestions into account. Specifically, we summarize our results into a main theorem and an intuitive one. We move visualization and intuitive ideas to the introduction. Also, we delay detailed analysis to a section called sketch of proof. Finally, we add more comparisons to existing literature to emphasize our contributions.
• The authors claim that they aim to understand the convergence of GD with large random initialization on simple matrix factorization problems, but as a reader, I could not find a main theorem or corollary that clearly states that with large random initialization, GD converges with certain rates under appropriate parameter settings and assumptions.
  • In our revised version, we present an improved version of the main theorem, Theorem 6, in Section 4.2. We also provide an intuitive version of the theorem in the introduction. Our theorem is deterministic and applicable to large random initialization. In our theorem, we prove that all the quantities beyond $t^*_k$ are bounded by either a constant or a logarithmic term. Hence, we claim that we provide a detailed trajectory analysis of GD. If we assume $t_k^*=O(\log(d))$, then GD achieves $\epsilon$-accuracy in $O(\log(d)+\log(1/\epsilon))$ iterations. This is probably the desired result the reviewer want to see. However, due to the challenges posed by large initialization, we are currently unable to verify such assumption. This is one of the limitation of the paper. In some sense, this also reflects the difficulty of the problem we are studying. On the other hand, even without this assumption, our results still reveal the incremental learning behavior of GD and many other characteristics of GD. We hope the reviewer could appreciate our attempts to tackle the challenging and meaningful problem.
• The 'large initialization' is in fact the `large random initialization'. The authors consider GD with large random initialization, but the variance still depends on the dimension of the problem under consideration. Therefore, when the dimension d is relatively large, it reduces to the ``small" random initialization setting.
  • To clarify for the reviewer, our perspective on large initialization refers to the scenario where the norm of $X_0$ remains a positive constant, even as the dimension approaches infinity. By statistical concentration results, the norm of $N_0$ approaches to a finite positive constant when dimension d tends to infinity. Therefore, if $X_0=\varpi N_0$ with a positive constant $\varpi$ independent of d, then it belongs to the large initialization regime. On the other hand, if $\varpi$ tends to zero as d increases, then it belongs to the small initialization regime.
  • In previous literature, $\varpi$ is as small as $\min(d^{-1/2},d^{-3\kappa^2})$, where $\kappa>1$ is the conditional number. In our case, $\varpi$ is a constant independent of d. As we discussed on page 6 below Theorem 6, we only require $\varpi=O(1/\sqrt{\eta})$ where $\eta$ is the step size. We also demonstrate that this is rate optimal. If we further increase it, the GD algorithm will simply diverge.
• Even in the simple matrix factorization problems, the comparisons with state-of-the-art results in this exact setting are not clear to me.
  • As we explained, there is a significant difference between large initialization and small initialization. Except the rank-one case, our work is the first one to study large initialization setting. This already makes the comparison clear. In addition, small initialization is in fact a special case of large initialization. All of our results hold for small initialization, too. Finally, large initialization is the one people are using in practice. Therefore, we hope the reviewer could appreciate our efforts to narrow the gap between theory and practice.
• The authors consider a simple matrix factorization problem, but as claimed in the main text, the motivation of this paper is to better understand GD with large random initialization in training neural networks.
  • Yes. Even for matrix factorization, the understanding of large initialization is rather limited. We hope our paper could bring people to notice this gap between theory and practice. We also hope our technique and results can inspire future research in related fields, including deep learning theory.

If the reviewer has additional questions, please feel free to discuss with us.

Hi Reviewer yiZg, we still hope to hear from you! In our understanding, you have two major concerns, and we have addressed them as follows.

• First, the reviewer holds the point that we are considering small random initialization setting because the variance of each entry tends to zero as dimension $d$ increases.
  • We would like to kindly point out that this argument is not correct. Suppose $N_0\in\mathbb{R}^{d\times r}$ with i.i.d. $N(0,1/d)$ entries. Then by standard concentration results, the spectral norm of $N_0$ will converge to a finite positive constant as dimension $d$ increases. If we do not require the variance of each entry tends to zero, such as taking $N_0$ as a matrix of $N(0,1)$ entries, then the norm of $N_0$ will explode and the GD algorithm will diverge when initialized with $N_0$. For the above reason, it is suitable to fix $N_0$ and define large or small initialization based only on the initial scale $\varpi$.
  • There is a significant difference between our work and previous works. Prior works require $\varpi\lesssim\min(d^{-1/2},d^{-3\kappa^2})$ while we only need $\varpi\lesssim 1/\sqrt{\eta}$, which is dimension-independent. In addition, our condition is rate-optimal, meaning that a further increase of $\varpi$ would lead to divergence of the GD algorithm. Furthermore, one may review small initialization settings as special cases of our settings. As a result, the setting in our paper is much more challenging than previous results, and we provide a nontrivial extension of previous results.
• Second, the reviewer suggests us to present a more concise and clear theorem.
  • Thanks for the suggestion! We have carefully addressed this point. We have presented a clearer theorem that emphasizes our assumptions and results. Specifically, when using random initialization, our trajectory analysis holds almost surely. Moreover, if an additional assumption is made, we may obtain the $O(\log(d)+\log(1/\epsilon))$ convergence rate of GD. We have also included detailed discussions in the paper. Hope this revision can address the reviewer's concern.

Please let us know if you have additional concerns. We are looking forward to your reply!

We thank the reviewer for the valuable suggestions and questions. In this rebuttal, we will address them point by point.

• Fig. 1 and the first paragraph of 4.2 form a really nice motivation! I'd recommend moving them to the introduction.
  • Thanks for the suggestion. We have moved them to the introduction in our updated version.
• My main concern regarding the submission its intended audience might be limited to the people looking to build upon those results to get towards a better understanding of symmetric matrix factorization. But my perspective is likely limited and there might be a wider applicability to the presented results
  • Symmetric matrix factorization intersects with a diverse array of problems such as compressed sensing, phase retrieval, matrix completion, PCA, quadratic regression, and neural networks, among others. It serves as a fundamental model that facilitates theoretical analysis. In addition, our work is the first one (except for the rank one case) to study large initialization. Such initialization is commonly used in practice, including neural networks or simply phase retrieval and PCA. Therefore, we expect our theoretical investigation will spark further research across these related fields.
• The introduction states that the focus of the submission is on the implicit bias of gradient descent, but I do not see how studying the dynamics of Fig. 1 connects to the implicit bias (which, in my understanding, refers to the limit point the optimizer converges to)?
  • We would like to offer two perspectives on the implicit bias of the gradient descent algorithm. Firstly, from the viewpoint of the limit point, the algorithm almost surely converges to the global minimum. Although this is an optimization result, one may also view it as certain implicit bias, because the optimization problem is non-convex. Secondly, our trajectory analysis reveals incremental learning behaviors of GD during the training process. This second viewpoint, focusing on the training process, is typically useful when early stopping is utilized.
• Remark 2 states the the results hold for PSD , but the results seem to also assume that  is diagonal. Is this assumption necessary, or is it presented for the diagonal case wlog? What is the key difficulty in generalizing it to non-diagonal matrices?
  • There is no loss of generality to assume that $\Sigma$ is diagonal, because the analysis of GD is invariant to the orthogonal transformation. In our updated version, we have mentioned this point when we make the assumption. Moreover, our research can be easily extended to general symmetric (not necessarily positive semi-definite) cases.
• Explanation of incremental learning.
  • Thank you for the suggestions. In our revised version, we have explained that in our context, incremental learning refers to the process where eigenvectors associated with larger eigenvalues are learned first.
• The introduction describes matrix factorization as "mirroring the training of a two-layer linear network", but this doesn't hold for the symmetric matrix factorization studied here, which seems more similar to quadratic regression
  • The training of a two-layer linear network can be interpreted as asymmetric matrix factorization (MF). See Section 2.2 in Sun et al. (2019). While there are distinctions between asymmetric and symmetric MF, the study of symmetric MF can be seen as a vital preliminary step towards analyzing asymmetric MF. Moreover, we would like to mention that asymmetric MF with a suitable regularizer $\min_{X,Y}|\Sigma-XY^T|_F^2+\frac{1}{4}|X^T X-Y^T Y|_F^2$ can be directly analyzed using the symmetric results.
• Other minor points.
  • We have updated our draft incorporating your valuable suggestions.