On the Crucial Role of Initialization for Matrix Factorization

We thank the reviewer for recognizing the strengths of our paper. Below, we provide further discussions to address your questions.

W1. The empirical improvements over LoRA seem rather marginal but I'm not an expert on experiments.

A1. We hope to clarify our numerical results.

• Sec. 5.1 shows that the proposed approach outperforms existing initialization approaches for LoRA. We note that the compared approaches, PiSSA and OLoRA have been integrated into HuggingFace's PEFT package [1], and are actively employed in the community.

• Our results in Sec. 5.2 show that NoRA reduces the training loss of LoRA by 10%. (This is an image generation task, hence we use loss to measure efficiency.)

• For results in Sec. 5.3, note that LLaMA2 improves over LLaMA by 1.4 (in absolute accuracy). This is through significantly improved data quality and thousands of extra GPU hours. Our NoRA improves accuracy by 0.5 on LLaMA and 1.2 on LLaMA2 simply through initialization. We believe this constitutes a reasonable improvement.

• Our additional results in Table 10 (Gemma-7B on GSM8K) show that NoRA outperforms LoRA by a larger margin (78.62 vs 76.72 in test accuracy).

We remark that often even an improvement of 1% is challenging; see e.g., [2]. Given that initialization is, perhaps, the most lightweight modification to LoRA, it seems unfair to compare it with those heavily modified approaches. Moreover, initialization is orthogonal to many existing methods, and thus holds great potential to be combined with other approaches for better performance.

Q1. What is the role of Gaussian playing in your analysis? To put it in other words, do you think it's possible to replace Gaussian with something, or Gaussian is essential for the analysis?

Response to Q1. Thanks for pointing this out. The Gaussian $\mathbf{\Omega}$ is only for practical convenience. A random matrix from a Stiefel manifold can replace the Gaussian $\mathbf{\Omega}$. In fact, any $\mathbf{\Omega}$ that permits the conditions discussed a few lines before equation (3) would give the same quadratic rate. And the conditions are i) column of $\mathbf{X}_0$ is in the column space of $\mathbf{A}$, and ii) $\mathbf{X}_0$ is full rank. We have revised Sec. 2.2 accordingly.

References

[1] PEFT pacakge from HuggingFace. https://huggingface.co/docs/peft/en/index

[2] https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard

W1. is there any intuition of this weak optimality or is it just curated from technical stuff? How larger is the space of weak optimality compared to true optimality?

A1. Weak optimality indeed arises for technical reasons. It means that the top-$r$ singular values are recovered subject to some bounded error related to other singular values. The intuition is that in the under-parametrization case, the smallest singular values would always perturb the convergence of the largest singular values. Theoretically, the weak optimal solution found by ScaledGD is at most ${\cal O}(r^{3/4})$ away from some global optimum; see more details in Lemma 5.

Experimentally, our simulation in Fig. 1 (c) shows that there is indeed a regime (i.e., weak optimality) that ScaledGD slows down after reaching to it. For example, the purple curve have significantly different behaviors before and after 30 iterations.

W2. Ideally to apply Nystrom initialization to LoRA, one should learn $\Delta \mathbf{W}$, which suggests that one should know how much weight change is in order to initialize finetuning model ...

A2. For NoRA, although we do not know $\Delta \mathbf{W}$, a recent NeurIPS 2024 paper [Lingam et al. 2024] empirically shows that there exists a set of well-performed $\Delta \mathbf{W}$ whose columns space is subspace of the pretrained weight $\mathbf{W}_0$. Hence, we can employ $\mathbf{W}_0$ as an approximation for $\Delta \mathbf{W}$. We have polished Sec. 4 to make this clear.

Q1. In Figure 1b, it kind of suggests that smaller $\xi$ is preferred for quicker convergence? So does it hint that Nystrom initialization benefits from small initializaion as well, which also induces zero saddle point concerns?

Response to Q1. Thanks for pointing this out. The reason for different convergence speed arises from large $f(\mathbf{X}_0) - f^*$. In other words, large $\xi$ with $\xi > 1$ coincidentally means large $f(\mathbf{X}_0) - f^*$ for the numerical example in Fig. 1(b).

We have updated Fig. 1(b) for avoiding confusion. Small initialization gives more complicated behaviors for saddle escaping, hence it does not necessarily lead to faster convergence; see the comparison between $\xi=1$ and the newly added red curve with $\xi=0.1$.

Q2. In NoRA, say we have two pretrained weights of pretty different magnitudes, does it indicate corresponding NoRA initialization also scales with such magnitudes since? Probably adding certain weight normalization would make the finetuning more stable?

Response to Q2. We thank the reviewer for this suggestion. We agree with this intuition that weight normalization could be helpful when the weight is significantly imbalanced. We are working on this for a systematic comparison.

Q3. minor writing issues: line 340: "modified ScaledGD in (6) have" should be "has".

Response to Q3. Thank you for pointing this out. We have corrected it and will double-check to ensure the manuscript is free of typos.

W1. The matrix factorization problem is not a practical problem to be solved ... any procedure using the target matrix itself, in the reviewer's opinion, is not allowed ... the original purpose of studying the MF problem: to understand how GD minimizes non-convex objectives even with random initialization. Disclaimer: This point only pertains to MF problems ...

A1. We thank the reviewer for the comment; however, we respectfully disagree with reviewer.

1. Matrix factorization remains a legitimate problem to study, and significant progress is still to be made. For example, the Lanczos method, which is commonly used in practice, achieves only a super-linear convergence rate under benign conditions. This is slower than the quadratic rate we achieve with our approach. Moreover, matrix factorization is the population loss for matrix sensing, and is also closely related with matrix completion and tensor decomposition. Our work provides new insights that can be possibly extended to these settings. Even though MF may not be directly practical, its theoretical analysis still provides valuable insights that are highly relevant for understanding optimization dynamics. We have updated Apdx. A.5 for further discussions.

2. Our initialization is still valid even without direct access to $\mathbf{A}$. It can be extracted from the gradients, where using $\mathbf{A}$ in gradient computation is the minimum requirement, as agreed by the reviewer. Taking the asymmetric setting as an example, the gradient of $\mathbf{X}$ is given by $(\mathbf{X} \mathbf{Y}^\top - \mathbf{A}) \mathbf{Y}$. It is straightforward that our initialization is the negative gradient of $\mathbf{X} = 0$ and $\mathbf{Y} = \bf{\Omega}$. This discussion is added in Apdx. A.4. Moreover, a recent NeurIPS publication [Ward and Kolda, 2023] also uses $\mathbf{A}$ for initialization. The result is well-received in the community.

3. It is important to note that $\mathbb{R}^{m \times n}$ is a large space, and random small initialization is often used due to technical reasons [Du et al., 2018]. The study of optimization methods should not be restricted solely to small random initializations. The flexibility to use different initialization strategies, such as ours, could lead to better convergence behavior.

4. We believe many of our contributions are novel and have not appeared in prior literature. For example, initialization-dependent quadratic rate is not known, to the best of our knowledge. The quadratic rate of quasi-Newton methods (such as ScaledGD) is also not common even in smooth and strongly convex setting, and we have established it for a nonconvex and non-smooth problem. Under-parametrization is less studied in matrix factorization, while we give several results upon this topic.

W2. as the reviewer already pointed out in 1., if we know the target matrix ...

A2. We respectfully disagree with the reviewer for the same reasons stated in the previous response.

We also hope to point out several design factors and implications that the reviewer possibly overlooked.

1. It is not clear from the first sight that whether one should initialize with $\mathbf{Y}_0=0$, or $\mathbf{Y}_0=1$.

2. The role of learning rate is also important. If a different one is chosen, ScaledGD does not share the same behavior; see Corollary 1.

3. Previous works often tackle the regime with $||\mathbf{X}_0 ||_F \approx || \mathbf{Y}_0||_F$, while our results provide new evidence that asymmetry helps asymmetric matrix factorization.

Q1. the quadratic convergence with the Nystrom initialization is significant ... Since the scaled GD algorithm is basically a Newton update, shouldn't the quadratic convergence happen asymptotically, regardless of the initialization? Is it that the Nystrom initialization allows the algorithm to reach the quadratically convergent phase more quickly?

A1. The quadratic convergence is determined by initialization. Existing works of ScaledGD such as [Jia et al., 2023; Tong et al., 2021] only report a linear rate, and a quadratic rate is not observed in the experiments in these papers. It is the Nystrom initialization that leads to the quadratic rate of ScaledGD. This is corroborated in experiments in our Fig. 1(b), where it is observed that slightly perturbed Nystrom initialization slows down to linear convergence.

We clarify that ScaledGD is not a Newton method, rather it can be viewed as a quasi-Newton approach, as discussed in [Tong et al., 2021]. To see this, notice that the Hessian of problems (1) and (4) is a tensor whose size does not match with the $r \times r$ precondition matrix $\mathbf{X}_t^\top\mathbf{X}_t$ used in ScaledGD. For quasi-Newton methods, quadratic rate is not known yet even in the strongly convex and smooth setting, and only non-asymptotic analyses for local rates are established recently; see e.g., [3, 4]. To provide further context, we have now added a paragraph in Appendix A.1 to summarize the recent developments on quasi-Newton methods. This further highlights the significance of our results in achieving quadratic convergence for nonconvex and local-smooth problems.

Q2. ... the matrix completion result and NoRA are strongly connected. The theory doesn't apply to the NoRA setting, but I do see that the Nyström initialization is a nice conceptual motivation for a potentially better LoRA initialization. However, now with the flood of empirical LoRA papers, I think the community has a very high bar for recognizing work that purports to improve LoRA in a practical sense. I am not sure if the experimental validations of this work really clear that bar.

A2. Thanks for recognizing the strong connection between our matrix completion result and the NoRA setting. Our theories hold for applying LoRA on least squares, as discussed in Apdx A.2. Given the similarity in the bilinear structure between matrix factorization and LoRA, we consider matrix factorization a reasonable prototype problem for understanding the optimization dynamics of LoRA.

Performance. We hope to clarify our numerical results.

• Sec. 5.1 shows that the proposed approach outperforms existing initialization approaches for LoRA. We note that the compared approaches, PiSSA and OLoRA have been integrated into HuggingFace's PEFT package [1], and are actively employed in the community.

• Our results in Sec. 5.2 show that NoRA reduces the training loss of LoRA by 10%. (This is an image generation task, hence we use loss to measure efficiency.)

• For results in Sec. 5.3, note that LLaMA2 improves over LLaMA by 1.4 (in absolute accuracy). This is through significantly improved data quality and thousands of extra GPU hours. Our NoRA improves accuracy by 0.5 on LLaMA and 1.2 on LLaMA2 simply through initialization. We believe this constitutes a reasonable improvement.

• Our additional results in Table 10 (Gemma-7B on GSM8K) show that NoRA outperforms LoRA by a larger margin (78.62 vs 76.72 in test accuracy).

We remark that often even an improvement of 1% is challenging; see e.g., [2]. Given that initialization is, perhaps, the most lightweight modification to LoRA, it seems unfair to compare it with those heavily modified approaches. Moreover, initialization is orthogonal to many existing methods, and thus holds great potential to be combined with other approaches for better performance.

References

[1] PEFT pacakge from HuggingFace. https://huggingface.co/docs/peft/en/index

[2] https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard

[3] Rodomanov, Anton, and Yurii Nesterov. "Greedy quasi-Newton methods with explicit superlinear convergence." SIAM Journal on Optimization 31, 2021.

[4] Jiang, Ruichen, Qiujiang Jin, and Aryan Mokhtari. "Online learning guided curvature approximation: A quasi-Newton method with global non-asymptotic superlinear convergence." In COLT, 2023.