On the Optimization Landscape of Low Rank Adaptation Methods for Large Language Models

Authors: Xu-Hui Liu, Yali Du, Jun Wang, Yang Yu
Primary area: foundation or frontier models, including LLMs
Keywords: large language model, LoRA, optimization

Abstract:
Training Large Language Models (LLMs) poses significant memory challenges, making low-rank adaptation methods an attractive solution. Previously, Low-Rank Adaptation (LoRA) addressed this by adding a trainable low-rank matrix to the frozen pre-trained weights in each layer, reducing the number of trainable parameters and optimizer states. GaLore, which compresses the gradient matrix instead of the weight matrix, has demonstrated superior performance to LoRA with faster convergence and reduced memory consumption. Despite their empirical success, the performance of these methods has not been fully understood or explained theoretically. In this paper, we analyze the optimization landscapes of LoRA, GaLore, and full-rank methods, revealing that GaLore benefits from fewer spurious local minima and a larger region that satisfies the \pl, a variant of Polyak-Łojasiewicz (PL) condition, leading to faster convergence. Our analysis leads to a novel method, GaRare, which further improves GaLore by using gradient random projection to reduce computational overhead. Practically, GaRare achieves strong performance in both pre-training and fine-tuning tasks, offering a more efficient approach to large-scale model adaptation.

Decision: accept (poster)
Reviewer scores: 6, 8, 8, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1730684219836

thread_type:
official_review

<thread_object>
creator: reviewer_cy2c

<content>
summary:
This paper provides theoretical analysis of the optimization landscapes for different low-rank adaptation methods used in training large language models (LLMs), specifically comparing LoRA, GaLore, and full-rank methods. The authors prove that GaLore benefits from fewer spurious local minima and a larger region satisfying the PL* condition compared to LoRA. Then, they propose GaRare, a method using random projection matrices instead of SVD-based ones, achieving similar benefits as GaLore, in terms of the optimization landscape, but with reduced computational overhead.

strengths:
1. Important focus on understanding optimization landscapes of fine-tuning techniques
2. Practical algorithm (GaRare) that improves efficiency
3. Comprehensive experimental validation
4. Clear mathematical formulation and complete proofs
5. Good connection between theory and practice

weaknesses:
1. Theoretical analysis limited to MLP architectures, making conclusions about LLMs less direct.
2. Incomplete empirical comparisons:
   - Limited LoRA experiments (mainly rank 2). It would be better to experiment with different LoRA ranks (r = 4, 8, 16, 32) for a more reliable validation of the results. 
   - Missing comparisons with recent methods (e.g. AdaLoRA, SoRA) that yields better performance than full rank fine-tuning (on GLUE), while promoting sparse low rank matrices. Could you explain why these methods, even though they promote sparsity, yield better results than full rank tuning? And how do they integrate within your theoretical framework?
   - No standard deviations reported. Could you please report these for a more reliable assessment of the performance of your proposed algorithm compared to baselines across all experiments (CIFAR / GLUE).
3. Some claims about LoRA’s performance relative to full-rank fine-tuning are oversimplified.
   - Contradicts findings from AdaLoRA paper with higher ranks.
   - Doesn’t account for sparse adaptation methods’ success.
4. Ambiguous definition of projected spurious local minima.
   - Unclear relationship between projected minima and full-rank space:  how these minima relate back to the full-rank landscape?
5. Limited novelty in theoretical results: some of the theoretical results appear to be direct extensions of established theorems.
6. Memory analysis could be more detailed.

questions:
1. How sensitive is GaRare’s performance to the choice of random seed and projection frequency? Could you perform an ablation study to probe the stability of your proposed method and report the results?
2. Could the theoretical framework be extended to transformer architectures?
3. How do the projected minima relate to the full-rank optimization landscape?
4. Why weren’t comparisons with higher-rank LoRA (r=8) and other recent low rank adaptation techniques included?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730754010533

thread_type:
official_review

<thread_object>
creator: reviewer_yr66

<content>
summary:
This paper proposes a new algorithm GaRare, which implements gradient low-rank projection through random matrices and improves the memory and computational efficiency of GaLore. Through optimization landscape analysis, it is proved that GaRare retains the advantages of GaLore, satisfies the PL condition, and avoids spurious local minima. Experiments verify the superiority of GaRare in performance and efficiency.

strengths:
1. By analyzing the PL conditions and spurious local minima, this paper systematically reveals GaLore's advantages in optimizing the landscape and LoRA's shortcomings.

2. This paper proposes the GaRare algorithm and provides rigorous theoretical proof that it can maintain GaLore's optimization advantages.

weaknesses:
1. The GaRare algorithm proposed in this paper is mainly based on combining and improving existing methods, especially gradient low-rank projection through random matrices instead of SVD. Although this method is more efficient, it is technically more of an optimization of the existing GaLore and low-rank adaptation methods rather than proposing a new theoretical framework or algorithm.

2. Although the paper theoretically analyzes the optimization advantages of GaRare, the experimental results do not fully demonstrate the improvement of this method compared to existing methods. In some experiments, its effect is not better than the full-rank method or LoRA.

questions:
1. GaRare uses Gaussian distribution to generate random projection matrices, but how about other distributions or generation methods? Does the choice of different distributions have an impact on the convergence speed and performance of the model?

2. Can the author add more experiments on practical tasks, such as fine-tuning end-to-end generation challenges or diffusion models, to further verify the results of GaRare?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730774761951

thread_type:
official_review

<thread_object>
creator: reviewer_eja2

<content>
summary:
This paper investigates the optimization landscape of LoRA and GaLore from a theoretical standpoint, focusing on conditions like the PL* region and the prevalence of spurious local minima. This analysis seeks to clarify GaLore's fast convergence and strong empirical performance. Building on these insights, a streamlined variant called GaRare is introduced, leveraging gradient random projection for efficiency. Experiments validate GaRare's effectiveness, supporting its advantages with reduced computational demands and comparable performance to GaLore.

strengths:
1. The paper applies theoretical insights from Lederer (2020) and Liu et al. (2022) to analyze LoRA and GaLore, offering an inspiring and interesting theoretical explanation of their behavior.
2. The paper introduces a streamlined variant of GaLore, named GaRare, and provides experimental results that effectively validate its performance and efficiency.

weaknesses:
1. The paper does not explicitly link the quality of the optimization landscape to convergence speed or generalization performance, which undermines its stated goal of theoretically explaining the performance of LoRA and GaLore. Many claims also lack this connection (e.g., lines 60-61, 289-291, and 301-304), making them appear weaker and less convincing.
2. The theoretical results in this paper are derived from analyses of MLPs, whereas LLMs, with their attention mechanisms, layer normalization, etc., are more complex. Since there is a gap between MLPs and LLMs, and the paper does not directly validate its theoretical results on LLMs (instead of relying only on the convergence and performance outcomes), the theoretical conclusions are less convincing.
3. The paper does not clearly motivate GaRare; it lacks evidence or justification for GaRare's advantages over GaLore based on theoretical analysis. Additionally, a more detailed algorithmic presentation is needed, particularly to clarify the process of recovering updated parameters from projected gradients, which would enhance understanding.

questions:
1. Is the formulation in Lederer (2020) fully compatible with that in Liu et al. (2022), allowing the results to be applied here without conflicting with prior findings?
2. Is it fair to compare the occurrence of spurious local minima between LoRA and GaLore when different definitions are used (i.e., standard vs. projected)?
3. How do the computational costs of these methods compare in Table 1? Does GaRare introduce any additional slowdown?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730918167893

thread_type:
official_review

<thread_object>
creator: reviewer_c5w7

<content>
summary:
The paper has two main contributions:
Firstly the authors conduct analysis on the theoretical properties of GaLore from the PL* condition perspective, which suggests that GaLore, compared with LoRA, has a larger region that satisfies the PL* condition, which provides faster convergence. Additionally, compared with full model training, the projected optimization approach suffers less from spurious minima issue, making it easier for optimization. These two arguments provide theoretical insights on the advantages of GaLore.
Then, the authors proposed a new method: GaRare, which uses random projection rather than SVD to find the low dimensional space, which improves memory efficiency in that the projection matrix no longer needs to be stored during training. GaRare, with lower memory cost, has the same theoretical properties of GaLore, as argued by the authors, and indeed shows performance comparable to GaLore on several empirical evaluation tasks, ranging from small-scale MLP-CIFAR10 experiments to LLM pre-training experiments.

Overall I find the paper well written, technically sound, and emprical results sufficiently supporting the claims.

strengths:
- Parameter efficient learning / fine-tuning is a heated topic, lots of new methods are proposed but it is unclear why some methods are better / worse. The submission studies the advantages of GaLore and drawbacks of LoRA from an optimization perspective, providing useful insights and theoretical framework for understanding the PEFT methods.

- Learning rate swipe is conducted, making the emprical results more convincing!

- Low-bit training setting is considered, and the proposed method still shows performance competitive with GaLore, demonstrating the practical usefulness of the method.

weaknesses:
- There exists couples of gap between the theoretical analysis's setting and the actual experiments: 1. The theory suggests a squared loss should be used but all experiments used cross entropy loss; 2. The theoretical analysis is limited to MLP.

- Same color is used to represent different ranks and optimization methods (Figure 1. and Figure 2.), which could be confusing. The authors could consider using different colormaps for these two figures.

- It is true that the random projection matrix does not need to be stored, but I think they still need to be materialized during forward propagation and would still cost O(mr) memory overhead if I understand correctly.

- (Minor) The proposed method uses random projection, which could introduce additional sensitivity to random seed in experiments.

questions:
- The theoretical analysis focuses on train-from-scratch setting, is there any difference between training from scratch v.s. fine-tuning setting? 

- How much extra runtime overhead would the random matrix generation cost in practice?

- How much difference would the "mr" term make in practice (Table 1, memory overhead of GaRare v.s. GaLore)? Since m is the output size, which would be pretty small in practice, e.g. 10 for cifar-10, and is much smaller than n, the input size, it would be nice if the authors could provide some example values of "m" and "r" in the caption of the table to better illustrate the differences.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731116680362

thread_type:
official_review

<thread_object>
creator: reviewer_9dct

<content>
summary:
The paper provides a theoretical analysis of low-rank adaptation methods for large language models (LLMs), focusing on LoRA and GaLore. The authors demonstrate that GaLore benefits from a more favorable optimization landscape than LoRA and full-rank methods, characterized by fewer spurious local minima and a larger region satisfying the PL* condition. Building on these insights, they introduce GaRare, a novel method that improves upon GaLore by employing gradient random projection to reduce computational overhead. Empirical results show that GaRare performs strongly in pre-training and fine-tuning tasks, offering an efficient approach to large-scale model adaptation.

strengths:
+ I believe the paper is a great application of the PL* condition to fine-tuning LLMS which is of significant interest. 
+ The theoretical analysis is rigorous and well-founded.
+ The paper contributes a valuable tool by introducing GaRare and demonstrating its practical efficiency.

weaknesses:
- Some sections of the paper, especially those detailing the theoretical results could be more accessible--understandable given the page limit.

questions:
N/A.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731117515728

thread_type:
official_review

<thread_object>
creator: reviewer_nysi

<content>
summary:
This paper builds on previous work (LoRA and GaLore) that uses low-rank adaptation to reduce the memory footprint of LLM training. This paper provides an analysis of GaLore, which compresses the gradient matrix, showing it has fewer problematic local minima and better convergence properties. Based on this analysis, they propose a new method called GaRare that improves GaLore further by using random projections to reduce computational overhead. GaRare achieves reasonable better performance on both pre-training LLMs and fine-tuning them for specific tasks.

strengths:
This paper provides a sound theoretical analysis that reveals the optimization landscapes of different adaptation methods for training Large Language Models (LLMs). A key strength of this paper is the in-depth examination of the parameter spaces where the PL∗ condition is satisfied, revealing that GaLore and full-rank methods have larger favorable regions compared to LoRA. This theoretical foundation explains the superior convergence rates and performance of GaLore by demonstrating its lower occurrence of spurious local minima, which often hinder optimization in training processes. Such insights into the conditions that facilitate faster and more reliable convergence are invaluable for developing more efficient LLM training techniques.

weaknesses:
Limited Experiment Setup: The experimental validation of the proposed methods is confined to modifications of the MLP layer, whereas practical applications of LoRA predominantly target the attention layers within LLMs. This discrepancy raises concerns about the generalizability and practical relevance of the findings.

Marginal Performance Improvements: The performance improvements reported on the GLUE benchmark for GaRare, compared to the LoRA baseline and GaLore, are marginal. This minimal gain questions the practical value and impact of the proposed method in real-world application. Such incremental improvements might not justify the complexity or the computational costs associated with implementing GaRare.

questions:
1) why we switch to RoBERTa for fine-tuning experiment? while the pretraining is performed on LLaMa? It would be more convincing and interesting to see FT results on LLaMa, which is the widely applied in practice. 

2) Another benefit of LoRA is its application in low data regime, I wonder what is the results of the proposed methods at different training dataset size.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732361880998

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all the reviewers for their valuable feedback and constructive comments on our manuscript. Your insights have greatly helped us improve the quality and clarity of the paper. Below, we address the general questions raised by the reviewers:

1. **The computational cost of GaRare.**

**Answer**: GaRare does not increase computational complexity compared to GaLore. Although GaRare requires continuously generating random matrices, this overhead is minimal. Moreover, it reduces the need for SVD computations compared to GaLore. Overall, it may even result in reduced training time. The specific training times are reported in the table below.

|                | 60M (1gpu) | 130M (2gpu) | 350M (2gpu) | 1B (4gpu) |
|----------------|------------|-------------|-------------|-----------|
| Full-Rank      | 1.98h      | 6.30h       | 26.47h      | 133.54h   |
| LoRA           | 1.93h      | 5.73h       | 24.87h      | 127.14h   |
| FLoRA          | 1.97h      | 6.00h       | 26.44h      | 129.88h   |
| GaLore         | 1.92h      | 6.07h       | 26.98h      | 131.55h   |
| GaRare         | 1.97h      | 5.96h       | 26.50h      | 130.00h   |
| $r / d_{\text{model}}$ | 128 / 256  | 256 / 768   | 256 / 1024  | 512 / 2048|
| Training Tokens| 1.1B       | 2.2B        | 6.4B        | 13.1B     |

2. **The randomness of GaRare.**

**Answer**: According to our theoretical analysis, as established in Lemma 5.1 and Corollary 5.2, the performance of GaRare is highly robust to the randomness of the random projection matrix, particularly when it is sampled from Gaussian distributions. These results suggest that the randomness of the random matrix has minimal impact on the algorithm’s overall performance.

In the original submission, we did not report results across multiple random seeds due to this theoretical robustness. To further validate this claim, we have now included results averaged over three random seeds. For experiments on LLMs, the mean and standard deviation are provided directly in the tables below. For the CIFAR datasets, these results are detailed in Section 6.1 of the revised manuscript. Across all cases, the results demonstrate small standard deviations, confirming our theoretical predictions and showing that GaRare's performance is stable and consistent across different random seeds.

We hope the additional analysis addresses the reviewer’s concern and strengthens the evidence for the robustness of GaRare.

### Pretraining LLaMA on C4 dataset.
|                | 60M  | 130M | 350M | 1B   |
|----------------|------|------|------|------|
| Full-Rank      | 34.06| 25.08| 18.80| 15.56|
| LoRA           | 34.99| 33.92| 25.58| 19.21|
| FLoRA          | 36.97| 30.22| 22.67| 20.22|
| GaLore         | 34.88| **25.36**| **18.95**| **15.64**|
| GaRare         | **34.33±0.09**| **25.49±0.20**| 19.24±0.07| **15.69±0.14**|
| $r / d_{\text{model}}$ | 128 / 256 | 256 / 768 | 256 / 1024 | 512 / 2048 |
| Training Tokens| 1.1B | 2.2B | 6.4B | 13.1B |

### Finetuning RoBERTa-Base and RoBERTa-Large on GLUE benchmark.

RoBERTa-Base
|                | Full-Rank | GaRare    | GaLore    | FLoRA     | LoRA      |
|----------------|-----------|-----------|-----------|-----------|-----------|
| CoLA           | 62.2      | 61.0±0.1  | 60.4      | 59.0      | **61.4**      |
| STS-B          | 90.9      | 90.3±0.0  | **90.7**      | 89.9      | 90.6      |
| MRPC           | 91.3      | 91.4±0.2  | **92.3**      | 88.5      | 91.1      |
| RTE            | 79.4      | **79.2±0.3**  | **79.4**      | 76.5      | 78.7      |
| SST2           | 94.6      | **94.2±0.2**  | **94.0**      | 93.8      | 92.9      |
| MNLI           | 87.2      | **87.0±0.2**  | **87.0**      | 86.6      | 86.8      |
| QNLI           | 92.3      | **92.1±0.2**  | **92.2**      | 91.9      | **92.2**      |
| QQP            | 92.3      | 90.9±0.3  | 91.1      | 90.9      | **91.3**      |
| Avg            | 86.3      | 85.8      | **85.9**      | 84.6      | 85.6      |

RoBERTa-Large
|                | Full-Rank | GaRare    | GaLore    | FLoRA     | LoRA      |
|----------------|-----------|-----------|-----------|-----------|-----------|
| CoLA           | 68.0      | 67.6±0.4  | **68.3**      | 65.5      | 68.2      |
| STS-B          | 91.5      | 92.3±0.0  | 92.5      | 92.5      | **92.6**      |
| MRPC           | 90.9      | **91.7±0.1**  | **91.7**      | 89.3      | 90.9      |
| RTE            | 86.6      | **87.2±0.3**  | 87.0      | 83.0      | **87.4**      |
| SST2           | 96.4      | **96.0±0.3**  | 96.1      | 96.0      | **96.2**      |
| MNLI           | 90.2      | **91.2±0.4**  | 90.8      | 90.4      | 90.6      |
| QNLI           | 94.7      | 94.5±0.1  | **95.7**      | 94.0      | 94.9      |
| QQP            | 92.2      | **91.9±0.2**  | **91.9**      | 91.5      | 91.5      |
| Avg            | 88.8      | 89.1      | **89.3**      | 87.8      | 89.0      |
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary of Paper’s Contributions:
This paper provides a theoretical analysis of low-rank adaptation techniques (LoRA and GaLore) for large language model (LLM) training from an optimization landscape perspective. It shows that GaLore exhibits fewer spurious local minima and a larger region satisfying the Polyak-Łojasiewicz (PL*) condition, providing theoretical grounding for its empirical advantages. Building on these insights, the authors introduce GaRare, which replaces SVD-based projection matrices with randomly generated matrices, thereby improving memory efficiency without sacrificing performance. The theoretical analysis, albeit done on MLPs with MSE loss, offers intuition that appears to carry over to larger transformer-based models and cross-entropy loss scenarios, as evidenced by additional experiments on LLaMA and RoBERTa.

Key Strengths:
	1.	Novel Theoretical Insight: The paper moves beyond expressivity arguments and provides a complementary perspective focusing on the optimization landscape. This fills a critical gap in understanding parameter-efficient fine-tuning methods.
	2.	Practical Algorithm (GaRare): The proposed GaRare method reduces memory usage while maintaining the favorable optimization properties of GaLore. In large-scale scenarios, memory constraints are increasingly important, making GaRare particularly appealing.
	3.	Empirical Validation: The authors support their theoretical claims with experiments on both smaller MLP-based tasks and large-scale LLM training. They demonstrate that GaRare can achieve comparable performance to GaLore and LoRA while offering better memory efficiency.
	4.	Robustness and Stability: The authors provide standard deviation results and analyze the effect of randomness in GaRare, showing that performance is stable across different random seeds.