On the Convergence Rate of LoRA Gradient Descent

Technical Summary: On the Convergence Rate of LoRA Gradient Descent

Problem Statement
Low-Rank Adaptation (LoRA) has become a standard method for fine-tuning large language models due to its efficiency, updating only low-rank adapter matrices $A$ and $B$ such that the final weights are $W_0 + BA$. However, the theoretical understanding of its convergence is limited. While the original loss function $\ell(W)$ is typically assumed to be Lipschitz smooth, the reparametrized loss function $L(BA)$ is not Lipschitz smooth with respect to the adapter matrices $A$ and $B$. This lack of smoothness prevents the direct application of classic convergence analysis techniques. Existing theoretical works fall into three categories: (1) asymptotic analyses in infinite regimes (e.g., Neural Tangent Kernel or infinite width), which do not provide non-asymptotic rates for finite models; (2) analyses of modified algorithms (e.g., GaLore, LoRA-One) that do not strictly address the original LoRA formulation; and (3) analyses of the original LoRA algorithm that rely on strong, artificial assumptions, such as uniformly bounded adapter matrices, to enforce Lipschitz smoothness. Consequently, the non-asymptotic convergence rate of the original LoRA gradient descent algorithm without boundedness assumptions remains an open question.

Methodology
The authors provide the first non-asymptotic convergence analysis of the original LoRA gradient descent algorithm under minimal assumptions: the original loss function is Lipschitz smooth and lower-bounded. The proof proceeds in three key steps:

1. Reformulation via Stacked Matrices: The problem is reformulated by stacking the adapter matrices $B \in \mathbb{R}^{m \times r}$ and $A^T \in \mathbb{R}^{r \times n}$ into a single variable $V \in \mathbb{R}^{(m+n) \times r}$. The original update $BA$ is recovered as a specific block of the outer product $VV^T$. This allows the optimization to be viewed as gradient descent on a new function $J(V) = L(E_1 V V^T E_2)$, where $E_1$ and $E_2$ are extractor matrices.
2. Modified Descent Lemma: Since $J(V)$ is not Lipschitz smooth (due to the multiplicative factor of $V$ in the gradient), the authors derive a modified descent lemma. This lemma bounds the function decrease $J(V_{t+1}) - J(V_t)$ using higher-order terms involving the norms of the parameters $\|V_t\|$ and the gradient.
3. Learning Rate Control: To ensure descent at each step, the learning rate $\eta_t$ is dynamically controlled based on the current parameter norm and gradient norm. Specifically, $\eta_t$ is set inversely proportional to $\|V_t\|^2 + \|\nabla L(E_1 V_t V_t^T E_2)\|$. The authors prove that even if the parameter norm $\|V_t\|$ grows unbounded (which forces $\eta_t$ to decrease), the sum of learning rates $\sum \eta_t$ diverges sufficiently slowly (as a harmonic series) to guarantee convergence, albeit at a slower rate than standard gradient descent.

Key Contributions

• Non-Asymptotic Convergence Rate: The paper proves that the minimum gradient norm under LoRA gradient descent converges to zero at a rate of $O(1/\log T)$, where $T$ is the number of iterations. This result holds without assuming bounded adapter matrices or Lipschitz smoothness of the reparametrized loss.
• Recovery of Standard Rates: The authors show that if the adapter norms are bounded (a condition often assumed in prior work), the convergence rate improves to the standard $O(1/T)$, matching the rate for Lipschitz smooth functions.
• Position Dependency: The analysis reveals a "position dependency" in LoRA dynamics: convergence is slowed if iterates move away from the origin (increasing $\|V_t\|$) and accelerated if they move toward the origin. This is attributed to the geometric restructuring of the loss landscape by the LoRA parametrization, which creates a stationary point at the origin regardless of the original loss structure.
• Practical Learning Rate Schemes: Motivated by the theoretical requirement to control $\eta_t$ based on parameter and gradient norms, the authors propose and validate practical adaptive learning rate schedules ($\eta_{adapt}$, $\eta_{adapt2}$, and $\eta_{norm}$) that adjust based on the norm of the stacked adapters or the loss value.

Results

• Theoretical: Theorem 3.5 establishes the $O(1/\log T)$ convergence rate for the general case and $O(1/T)$ for the bounded case. The proof demonstrates that the recursive relationship between the learning rate, parameter norm, and gradient norm introduces a slowdown in convergence compared to standard gradient descent.
• Empirical: Experiments were conducted on logistic regression with CIFAR-10 embeddings and ResNet-18 trained on CIFAR-10.
  • Adaptive and normalized learning rates derived from the theory demonstrated faster and more stable convergence compared to constant learning rates.
  • In logistic regression experiments, the parameter norm $\|V_t\|$ was observed to grow unbounded over 1000 epochs, confirming the theoretical scenario where convergence slows to $O(1/\log T)$.
  • In ResNet-18 experiments, $\|V_t\|$ converged to a bounded set, resulting in faster convergence.
  • In Large Language Model (LLM) fine-tuning (TinyLlama-1.1B), adaptive rates showed significant benefits when parameters were initialized with small norms, but behaved similarly to constant rates when initialized with large norms (where $\|V_t\|$ is large and grows slowly relative to its size).

Significance
The paper claims to close a significant gap in the theoretical understanding of LoRA by providing the first non-asymptotic convergence analysis for the original algorithm without artificial boundedness assumptions. It clarifies that the convergence rate of LoRA is not dependent on the chosen rank $r$ but is governed by the interaction between the learning rate and the norm of the iterates. The work highlights that LoRA's reparametrization fundamentally alters the optimization geometry, potentially leading to different solutions compared to full-rank fine-tuning. Furthermore, the proposed learning rate strategies offer a practical method to stabilize and accelerate LoRA training by accounting for the unique structure induced by low-rank reparametrization.