Common Response (Repeated in all responses)

First of all, we thank the reviewers for their positive and constructive feedback. We are excited to see that the reviewers are appreciative of our theoretical contributions. Below, we address each of the reviewers' comments individually.

Individual Response

We are happy to hear that the reviewer found our results sound and illuminating. Below, we address the reviewer’s main concern regarding the scenario with near-low-rank updates.

Q) Theorem 1 and Corollary 1 … spurious local minimizes of higher rank far from the global one, it doesn't eliminate possibility of spurious local minima with numerical low-rank

We thank the reviewer for the thoughtful question. We clarify the claims of Theorem 1 and Corollary 1 as follows.

Corollary 1 states that if $X_\square$ is a spurious local minima, then $\sigma_r (X_\square) \ge \frac{2\alpha}{\beta} \sigma_{r*} (X_\square)$. This provides a substantive lower bound on the $r$th singular value, making $X_\square$ not numerically low rank. (Recall that $r> r_\star$ in Corollary 1 and “low-rank” refers to rank $r_\star$.) Moreover, this lower bound on $\sigma_r (X_\square)$ means that $X_\square$ and the global minimum $X_\star$ cannot be close, since $\sigma_r(X_\star)=0$. Therefore, Corollary 1 does eliminate the possibility that a spurious local minimum is low-rank or is close to $X_\star$.

Common Response (Repeated in all responses)

First of all, we thank the reviewers for their positive and constructive feedback. We are excited to see that the reviewers are appreciative of our theoretical contributions. Below, we address each of the reviewers' comments individually.

Individual Response

We are excited to hear that the reviewer found our main theoretical results interesting. We are also grateful for the detailed feedback provided by the reviewer, and we respond to them individually in the following.

Regarding the relation with other LoRA variants

Yes, as the reviewer points out, our theory is indeed applicable to the more modern enhanced LoRA variants. We discuss a few popular LoRA variants, including the ones pointed out by the reviewer.

LoRA+ (Hayou et.al., 2024) and rsLoRA (Kalajdzievski, 2023) share LoRA's objective and initialization while modifying hyperparameters like the learning rate and scaling factors to accelerate and stabilize training. Therefore, our theory assures these variants can also successfully find the global minimum, hopefully, faster and more stable.

PiSSA (Meng et.al., 2024) and MiLoRA (Wang et.al., 2024) modify the training objective by decomposing the pretrained weight matrix into the sum of a principal ($A_pB_p$) and minor($A_mB_m$) component. PiSSA optimizes the objective $f(A_{lora}B_{lora} +A_mB_m)$, initializing $A_{lora}B_{lora}$ with $A_pB_p$. In contrast, MiLoRA optimizes $f(A_pB_p+A_{lora}B_{lora})$, initializing with $A_mB_m$. While appearing very similar, our theory introduces a contrasting view for the two methods.

PiSSA initializes the fine-tuning weights with $A_pB_p$, which inherently contains 'principal' pretrained model information. In this setting, applying weight decay to $A_p$ and $B_p$ is counterintuitive; rather than regularizing the fine-tuned model to remain close to the pretrained model, weight decay here would bias the model toward losing essential pretrained characteristics. Thus a low-rank solution isn't naturally expected, and the model would be required to be very well-conditioned (i.e., within the special regime) to guarantee convergence to the global minimum under our framework.

Conversely, the use of weight decay in MiLoRA is more sensible as $A_mB_m$ inherently represents a minor component. Therefore, we can more naturally apply our results to MiLoRA to guarantee convergence to a global minimum, in contrast with PiSSA. Investigating the practical implications of this theoretical insight is an interesting direction of future work.

We note that variants like LoRA-GA (Wang et.al., 2024), which significantly alter training dynamics, do fall outside our current scope and offer promising directions for future work.

Q) Why the restricted smoothness …

Our definitions of restricted convexity and smoothness are motivated by the proofs requiring only a "directional form" of strong convexity and smoothness. In contrast, the conventional definitions require strong convexity and smoothness for all possible directions. While our definitions may feel more complicated, they are weaker and more realistic assumptions compared to standard strong convexity and smoothness. In particular, instead of requiring the standard smoothness $\nabla^2 f(X) [A, A] \le \beta ||A||_F^2$ for all $A \in \mathbb{R}^{m\times n}$, we only require it for the directions$A$ in the space $\\{UX+XV | rank(U)=rank(V)=1 \\}$, a much smaller, restricted space.

Q) Why X_box can be full rank

We apologize for this confusion. By “full rank” meant rank $r$, since the low-rank update $X_{box}=AB^T$ can have rank at most $r$. However, we now see that this was not the correct language, so we will update it to say rank $r$ instead of full rank.

Q) In Proof 1, the authors used kappa …

As in line 253, $\kappa$ is defined as $\frac{\sigma_{r*}}{\beta \sigma_r}$. Thus, the case $2\kappa \alpha >1$ in the last line of the proof corresponds to the special regime and case (i) of the generic regime, while the converse corresponds to the case (ii) of the generic regime. Thank you for pointing this out, we will make this distinction clearer in our revision.

Q) ||X||_\star, is this the nuclear norm? but … Q) equivalence between the unconstrained…

We apologize for the confusion. The L2 regularization applies to the LoRA fine-tuning objective, while the nuclear norm regularization applies to the rank-constrained full fine-tuning objective. As we note in Section 1.3, these two objectives are equivalent, as shown in Recht et.al., 2010, Lemma 5.1.

Q) Ge et al. 2015 is somewhat different from the standard SGD … Adam.

We appreciate the reviewer’s precision on this point. While we believe that the qualitative point we derive through this reference remains valid, we agree with the reviewer that, strictly speaking, Ge et al.’s result does not imply global convergence for all optimizers. We will clarify this point explicitly in our revised paper.

Common Response (Repeated in all responses)

First of all, we thank the reviewers for their positive and constructive feedback. We are excited to see that the reviewers are appreciative of our theoretical contributions. Below, we address each of the reviewers' comments individually.

Individual Response

We are happy to hear that the reviewer found our claims to be well supported by theory and experiments and the contribution distinct from prior works. We agree with the reviewer's view that “this paper could be useful to identify/design better low-rank adaptation algorithms,” and we outline how our theory can be applied to several LoRA variants in our response to Reviewer 9M1X.

Regarding the question of whether multiple experiments share the same global minimum

We thank the reviewer for the insightful observation and suggestion. Yes, our theorem indeed implies that multiple experiments should converge to the same global minimum (the same product $X=AB^\intercal$, but the low rank factors $A$ and $B$ are determined only up to rotations). To demonstrate this empirically, we extended the experiments originally presented in Figure 5 of the appendix to directly test whether training trajectories with multiple random seeds converge to the same limit. See the figure of the link below:

https://drive.google.com/file/d/1vU2oZT2qAHxcY2gnIjA5CIBUwevxNJhs/view?usp=sharing

In the figure, we plot the ‘total variation' of the training trajectories with multiple random seeds, defined as: $\sum_{1\le i<j\le N} \|| \Theta_i^{(t)} - \Theta_j^{(t)} ||$ where $\Theta_i^{(t)}$ is the parameters of the $i$ th model at the end of the $t$th epoch. We see that the total variation converges to 0, indicating that multiple experiments share the same global minimum. (The total variation starts at 0 because the $B$ matrix is always initialized to be 0, so the product $X=AB^\intercal$ starts out at the same value of 0, even though $A$ is initialized differently.)

Common Response (Repeated in all responses)

First of all, we thank the reviewers for their positive and constructive feedback. We are excited to see that the reviewers are appreciative of our theoretical contributions. Below, we address each of the reviewers' comments individually.

Individual Response

We thank the reviewer for their meticulous and constructive comments, and we are pleased to hear that the reviewer recognizes the novelty of our theoretical contributions.

Discussion with Table 2

We appreciate the reviewer’s encouraging remarks on the results of Table 2 and its contrast with over-parameterization. We agree this point is interesting enough to merit further emphasis, so, following the reviewer’s suggestion, we will highlight this discussion more prominently in our revised paper.

Correction of typos

We have corrected all typos pointed out by the reviewer. Once again, we sincerely thank the reviewer for their thorough reading of our manuscript and their detailed feedback.

Question on alternative reasons for the failure case

We thank the reviewer for raising a thoughtful point. Indeed, bad (large) initializations can lead to poor performance due to issues such as activation function saturation (for tanh activation functions) or exploding gradients. In our setup, this phenomenon indeed occurs if the initialization variance is further increased to \mathcal{N}(0, \frac{1}{2]), as demonstrated in the figure in the link below.

https://drive.google.com/file/d/14ui2E-hmg7E7LvaUp2X0hBPx9Zb6AQZp/view?usp=sharing

However, it is unlikely that the behavior observed in Figure 2 of our main text is caused by these issues, as the gradient norm remains stable and nonzero throughout training, as demonstrated in the figure in the link below.

https://drive.google.com/file/d/1w7k0dGcjFvBebFtw8OCqaKZb3BP-1180/view?usp=sharing