On the Optimization Landscape of Low Rank Adaptation Methods for Large Language Models
Authors: Xu-Hui Liu
Yali Du
Jun Wang
Yang Yu
Venue: ICLR 2025 Poster (2025)
Keywords: large language model
LoRA
optimization
Primary area: foundation or frontier models, including LLMs

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.

Published as a conference paper at ICLR 2025
ON THE OPTIMIZATION LANDSCAPE OF Low RANK ADAPTATION METHODS FOR LARGE LANGUAGE MODELS
Xu-Hui Liu'1 Yali Du Jun Wang' Yang Yu!
National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing. China
2 Cooperative AI Lab, Department of Informaties, King's College London, London, UK 3 AI Centre, Department of Computer Science, University College London, London, UK 1iuxh@ Landa. nju. edu. en, yali. dučkel. ac. uk, jun, wangêcs wwl.ac. yuyēnju. wdw.jueedd..com
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 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 empir- ical 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 condition, a variant of Polyak-Lojj Lojji--wjaiiwiizz (PL) condition, leading to faster convergence. Our analysis leads to a novel method, GaRare, which further improves GaLore by using gra- dient random projection to reduce computational overhead. Practically, GaRare achieves strong performance in both pre-training and fine-tuning tasks, offering more efficient approach to large-scale model adaptation. Code is available htttps://githui com cow com/Lluxhymm/Gaaareeee
INTRODUCTION
Large Language Models (LLMs) have demonstrated impressive performance across various do- mains, including natural language processing (Brown et al. 20200), computer vision (Saharia et al.) 2022), and reinforcement learning (Reed 2022). However, due their large scale, pre-training and fine-tuning LLMs demand significant memory usage. Parameter-efficient fine-tuning (PEFT) techniques provide solution by enabling the adaptation of pre-trained models to downstream applications without updating all model parameters. Among these methods, low-rank adaptation (LoRA) (Hu et al. 2022) has become a widely adopted approach. For a pre-trained weight matrix Wo E g LoRA reparameterizes the fine-tuned weight matrix W E Rmmx as W = W, + BA, where B E Rmrr and A E R2 Since the rank r is chosen such that r < min(m, n)) matrices A and B contain significantly fewer parameters than the original matrix, resulting in reduced mem- ory requirements during fine-tuning as Wo remains fixed. Recently, Zhao et al. (2024) introduced a new method called GaLore, which compresses the rank of the gradient matrix instead of the weight matrix. This approach has been shown to outperform LoRA in terms of both performance and mem- ory efficiency. Furthermore, GaLore is applicable to pre-training tasks, expanding its utility beyond fine-tuning alone.
To explain the success of low-rank adaptation methods, existing research has primarily focused on analyzing their expressivity (Zeng & Lee 2024 Zhao et al. 2024) studying the optimization land- scape by assuming convex loss functions (Jang et al. 2024). However, the expressivity of low-rank
Work done during Xu-Hui Liu's visit King's College London.

---

Published as a conference paper at ICLR 2025
adaptation methods alone may not fully explain the success of techniques like LoRA and GaLore, and the convexity assumption does not hold for neural networks. Notably, several studies have shown that the learning curves of different fine-tuming methods exhibit distinct patterns. For instance, Jang eet al. (2024) and Xia et al. 2024) find that LoRA converges more slowly than full-rank fine-tuning, while Zhao et al. (2024) shows that Gole converges even faster. These phenomena are tied to the optimization landscapes of these methods, which are not well-explained by current theories. The lack of a comprchensive theoretical explanation raises questions about their generalizability to other tasks and limits the development of new low-rank adaptation methods.
To address this issue, we first analyze the regions in the parameter spaces of different methods that satisfy the PL' condition (Liu et al. (2022). Under this condition, the existence of solutions is guar- anteed, and the convergence rate of (S)GD is exponential. Our analysis reveals that the region the parameter space satisfying the PI." condition condition is significantly smaller for LoRA compared to Galore and the full-rank method. This suggests that LoRA more likely to encounter regions of the optimization landscape where convergence guarantees are weaker, leading slower convergence rates and suboptimal solutions. This explains why LoRA does not achieve the same convergence rate final performance the other two methods. To further explain GaLore's 's advantages over the full-rank method, we examine the presence of spurious local minima in both methods. During train- ing, solutions can become trapped in these spurious local minima, preventing further optimization. A lower occurrence of spurious local minima implies a better optimization landscape. Our analysis shows that GaLore is more likely to meet the condition of having no spurious local minima, whereas the full-rank method is less likely to avoid them. Therefore, we conclude that GaLore offers the best optimization landscape, while LoRA presents the poorest one, which aligns with the observed empirical results. Based on our theoretical analysis, the key to preserving GaLore's 's favorable op- timization landscape lies in projecting the gradient matrix into low-rank spaces. In GaLore, the projection is performed using Singular Value Decomposition (SVD) on the original gradient matrix, with the resulting projection matrices stored for future use. However, SVD computationally ex- pensive, and storing the projection matrices increases the memory usage. To enhance GaLore, introduce Gradient Random Projection (GaRare), which replaces the SVD-generated projection matrix with randomly generated one. Theoretically, GaRare preserves the favorable optimization properties of GaLore, providing a more efficient and memory-efficient alternative while retaining similar optimization benefits.
In experiments, we first validate our theoretical findings on small datasets and MLP networks. The results demonstrate the trade-off between expressivity and the optimization landscape as predicted by the theory, as well as the similarity in the optimization processes of GaRare and Gore Next, we conducted experiments on LLM pre-training and fine-tuning tasks. The results show that GaRare achieves comparable performance to GaLore while using less memory, further supporting the appli- cability of our theoretical insights to LLMs.
Our main contributions can be summarized as follows: First, we present the first comprehensive analysis of the optimization landscapes of current mainstream fine-tuning methods: the full-rank method, LoRA, and GaLore. This theoretical framework explains the differences in convergence rates and performance among these methods. Second, building on our theoretical insights, we in- troduce a novel algorithm, GaRare, which retains the advantages of Gal while further reducing memory usage. Finally, empirical results demonstrate that GaRare achieves performance compara- ble to GaLore in both pre-training and fine-tuning tasks, all while utilizing less memory.
2 BACKGROUND
2.1 NEURAL NETWORK
We consider input data from D2 C Rd and output data from Dy C. RT We model the data with layered, feedforward neural networks, that is, we study sets of functions {ge- D2
R
θ M) C G := (ge: D + mm : e M) with
ge = e' -e. f' for
and M C M= (0=
0²) @1 E gg xp' J. The quantities pd d and p1+1 m are the input and output dimensions, respectively. l the depth of the networks, and w == min (p__._"............. ..... pP'} the minimal width of the networks. The functions f$ Re IRe' are called the activation
2

---

Published as a conference paper at ICLR 2025
functions. We assume that the activation functions elementwise functions in the sense that - = P
for all b E RY, where f :R + R is an arbitrary function.
Given the number of samples in the dataset, empirical-rish minimizers the networks whose parameters are global minima of the objective function
+ {(ge)= Σ ((golz)).
over M for fixed data (21, (ii.),)....... (In, Un). The loss function L R x R + R is assumed convex in its first argument; this includes all standard loss functions, such the least-squares loss 8: (a, + la blg. the logistic loss : (a, b) + -(1 + b) log(1 a) - (1 b) log(1 - a), the hinge loss l (a, b) max ab), and forth. We use Dge represent the differential map of ge: IR + R where
E p the number of parameters of the neural network. 0(ge).
Dge is represented as a m t matrix, with (Dge)a.j = 09; The neural tangent kernel (acot
al. 2018 defined as m matrix K(+)= Dgo (Dge)".
2.2 GALORE
Gradient rank projection (GaLore) (Zhao el. 2024) demonstrate the following gradient update rules: 0- O, + Et=o AG,, and AG, U. (.)" where v) is the learning rate, G, the gradient matrices, Üg is the projection matrices, is an entry-wise stateful gradient regularizer. For example, for Adam, Pt(G,)
MM/VV,+ where M, 31 M + (1 Bi G., and V, 32% + (1 32) Therefore, Pe can be memory--ntenssvv. Projecting gradient matrix to low-rank space can reduce the memory usage significantly. In GaLore, the projection matrices is
selected based on Singular Value Decomposition (SVD): G. UEVT, U, = U[:, r] is the first columns of U.
3 RELATED WORK
(2022) proposed Low-Rank Adaptation (LoRA) fine-tune pre- trained models with reduced memory usage. Building on LoRA, numerous methods have been introduced to enhance its performance (Liu et al.] 2024 Yang et al., 2024; Lin al. 2024a b Hayou et al. 2024 Lialin et al., 2024 Meng et al. 2024). For example, LoRA Dropout( et al., 2024b) introduces random noise into the learnable low-rank matrices, increasing parameter sparsity to reduce overfitting. LoRA+ Hayou et al. 2024) assigns different learning rates to the low-rank matrices to improve training efficiency, while PiZZA (Meng et al. 2024) employs Singular Value Decomposition (SVD) weight matrices to extract principal components low-rank matrices.
Low-rank adaptation. Hu et al.
However, the optimization landscape of the LoRA-based framework restricts its application to fine- tuning tasks only. ReLoR A(Lialnn al. 2024) extends LoRA for pre-training but requires full- rank warm-up phase to match the performance of standard pre-training. FLORA, by establishing an cquivalence between LoRA and gradient compression, eliminates the need for warm-up phase in pre-training, GaLore (Zhao et al. 2024) projects gradient matrices into low-rank spaces, achieving strong performance and high memory efficiency in both pre-training and fine-tuning tasks. Building on GaLore, WeLore(Jaiswal et al.) 2024) adaptively selects the rank of projection matrices, and OwLore(Li et al. 2024) introduces layer-wise updates further improve flexibility and efficiency.
Theory of neural networks. The expressivity of neural networks refers to their ability to approx- imate target function. This concept is foundational, starting with the universal approximation theorems [Cybenko| 1989 Hornik et al.) 1990), which demonstrate that neural networks, under cer- tain conditions, can approximate any continuous function. Building on this, series of subsequent works further explored the limitations and potential of neural networks (Poon & Domingos 1
2011:Lu Lu et al. 2017: et al. 2023). From a different angle, studies on the loss landscape (Du et al. 2019 Zou et al. 2018 Allen al. 2019 Liu et al. 2022) have provided insights into how first-order optimization methods, such as gradient descent, are able to converge to
Bengio & Delalleau
global minima under certain conditions.
3

---

Published as a conference paper at ICLR 2025
Theory of low-rank adaptation. Aghajanyan al. (2021) found that intrinsic low-rank structure is crucial for fine-tuning language models. Zeng & Lee (0024 analyzed the expressive power of LoRA. and Zhao et al. (2024) examined the low-rank structure of gradient matrices. While these studies conclude that low-rank adaptation methods can achieve strong performance, the details of the optimization process remain unclear. Pang et al. (2024) attempted to analyze the optimization landscape of LoRA, but their analysis relies on the convexity assumption.
4 ANALYSIS
In this section, we analyze the optimization landscape of Gal.rre, LoRA and full-rank method. The analysis is divided into two parts. The first part found the optimization landscapes of GaLore and full-rank method are superior to that of LoRA. This part is based on PL" condition (Oymak & Soltanolkotabi 2020), variant of Dolyak-Lojasiewicz (PL) condition, which is framework for analyzing non-con systems, such as neural networks. PL" condition is important because the loss function that satisfies PL' condition is guaranteed with exponential convergence rate un- der gradient descent (GD) and stochastic gradient descent (SGD). Therefore, the larger the region satisfied PI." condition, the better the optimization landscape is. Liu et al. (2022) found that over- parameterized systems have high probability to satisfies PI." condition, which explains why large models always demonstrate better performance (Brown et al., 2020). Intuitively, LoRA harms the rer-parramtterizatoonn of the neural network, it only optimizes much smaller number of parame- ters than full-rank method. In contrast, GaLore retains the per-parraettiizttionn by optimizing all parameters. We verify this intuition by calculating the region where the PL" condition is satisfied for all three methods.
The second part finds GaLore has better optimization landscape than full-rank method. This analysis focuses on spurious local minima- fewer spurious local minima imply a better optimization landscape, the optimization process is less likely to get trapped in poor solutions. We find that it is challenging for the full-rank method to avoid spurious local minima, whereas GaLore easily achieves this. Due to space constraints, the proof's for this section are provided in Appendix A
4.1 GRADIENT LOW-RANK PROJECTION KEEPS OVER- PERR-PPRAMETERIZAAT
To show the relationship between werrpprrameterization and good optimization landscape, we first introduce the definition of PL." condition: A non-negative function & satisfies pr-PL"" condition on a set .M E R' for > 0, if [[ Z μC(O). VO E ... As we mentioned earlier, PL.* condition ensures the existence of solutions and guarantees exponential convergence for GD and SGD, implying a good optimization landscape. In this section, we analyze the regions where the PL condition is satisfied for each method. The following theorem reveals the relationship between PL' condition and over- parameterization. The connection is established by the eigenvalues of the neural target kernel K (()). Let Amin (K (()) be the smallest eigenvalue of K (9), we have Theorem 4.1 (Theorem and Proposition 4 of (Liu et al. (2022)). The square loss function f(ge) 2 elgge(> (x) - 1/ satisfies p-PL." condition on M if and only if Amin (oninnKK (0)) 2 1 1>>00 O.
Amin (K(+)) )min(K(()) space for over-parameterized systems, the intuition behind it is based on parameter counting (Liu let al. 2022). Note that K(@)- Dge Dge)= the singular set of O such that K(O) is not full rank will of co-dimension L n + 1, where i is the number of parameters, n is the number of samples. If n. i.c., the systems are under-parane pareemrarrmeteizedd, K()) is always rank deficient and therefore Amin (K()) = O. Hence such systems never satisfy PL condition. On the other side, the larger the degree of the model averrraramtterizationn t n is, the smaller the singular set is expected to be. This intuition explains why LoRA shows worse performance compared to full rank finetuning and Galore: LoRA reduces the number of parameters of each layer, the degree of over-parameetriizatoonn is reduced and even the systems become mnder-parameterized. Therefore, the PL condition is difficult to be satisfied if LoRA is used. In contrast, although Galore projects the gradient matrices to the low-rank spaces, the projected matrices will be projected back during the parameters updating process, and thus the degree if over weer-paameterizaaee kept. The theoretical guarantee for full-rank training is established by Liu et al. (2022).
0 implies K(O) is not singular. PL condition holds across most of the parameter
of the original systems
Theorem 4.2 (Theorem 4 of Liu et al] (2022). Consider the neural network defined by Eg. 7
where the initial parameter Oo is randomly chosen such that O% NO, Ips.ptt) for j E 1
4

---

Published as a conference paper at ICLR 2025
Let An Amiu (Qu)) denote the minimum eigenvalue of the kernel matrix K(O)). For any E No)) if the width of the network satisfies w = 52 mm
(20-1)² ). then the square loss satisfies j-PL' condition with high probability over the ball B(O., R) for full-rank method.
According to this theorem, the radius of the region that satisfies the PL* condition depends on the width of the network. The wider the network, the larger this region becomes, confirming the intuition that over peee-prraeterizaaionn leads to the PL" condition and thus a favorable optimization landscape. Based on the derivation of Theorem [42 we extend the results to GaLore and LORA, respectively.
Theorem 4.3. Under the condition of Theorem 4.2 let be the rank of GaLore, if the number of
training samples n satisfies n S E'=1'', then if the width of the network wo = 52 mmn ( the square loss satisfies p-PL." condition with high probability over the ball B(0,, R) for GaLore.
This theorem demonstrates that the GaLore method covers the same region as the full-rank method, with the exception of an additional mild condition: the number of training samples S rr <rEj=L. p² This condition is easy to satisfy. For instance, in the case of a IB model, if the rank is selected as r 512, the constraint on the number training tokens becomes 512 billion. This constraint exceeds the number of tokens required to train IB model. Then we present the result for LoRA.
Theorem 4.4. Under the condition of Theorem 4.2 let r be the rank of LoRA, ifr = á (mn
(A0- (A0-M)=
then the square loss satisfies pu-PI." condition with high probability over the ball B(0,, for LoRA.
The theoretical results support our intuition: the region satisfying PL" condition is significantly smaller in LoRA compared the Galore and full-rank methods. This is evident from the fact that r < w and the exponent of R increases from 67 + 2 to 121 + 2, resulting in a much smaller radius R under a fixed This reduced region indicates that the space where a favorable optimization landscape exists characterized by the presence of solutions and rapid convergence rates is more constrained in LoRA. Consequently, LoRA exhibits poorer performance compared to the others.
4.2 GRADIENT LOW-RANK PROJECTION HAS No SPURIOUS MINIMA
Spurious local minima are entities that optimization algorithms strive to avoid. Intuitively, a spurious local minimum is a point in the parameter space where the loss in its neighbourhood is higher than at the point itself, thereby preventing the optimization algorithm from escaping from this point. Formally, we use the definition of spurious local minima in Lederer (2020).
Definition 4.5 (Spurious local minima). Let θ E M be a local minimum of the objective function 2). If there no continuous function h 1] M that satisfies (i) M[] = Q and h(1] for
global minimum M of the objective function 2 and (ii) + E(gn [t)) is nonincreasing, we call
the parameter O spurious local minimum.
According this definition, if there is no spurious local minima in M, then there exists at least one non-increasing path belongs to M from every point in M to the global minima. For full-rank method, the optimized parameter space M is exactly the original parameter space M. For the whole parameter space, Lederer (2020) gives the result of full-rank method.
Theorem 4.6 (Theorem of Lederer (2020)) For the network defined by Eg. 7.) if w, the minimal width of the network, no less than 2m + 1)', then the objective function 2 has no spurious local minima with full-rank method.
This theorem demonstrates that neural network has no spurious local minima if it is wide enough. However, the minimal width 2m(n + 1)' is large and cannot be satisfied in application, especially for LMs, where n and / are much larger.
The result can be generalized to LoRA easily by considering the network of LoRA as ge x : r00 ".. ['03][0
where 0¹ E TRP'x xr O E - r is the rank for LoRA, and T is the identity function. Corollary 4.7 (No spurious local minima condition for LoRA). For the network defined by Eq. 1
if r, the rank of LoRA, no less than 2m(n + 1)21, then the objective function 2 has no spurious local minima with LoRA.
5

---

Published as a conference paper at ICLR 2025
It can be seen that the condition for LoRA is even more difficult to satisfy. The facts that < and the exponent from to 2/ implies LoRA cannot guarantee no spurious local minima in the optimization process.
For GaLore, while updates are performed within the low-rank parameter space M, the gradient computations carried out in the original full-rank space M. Consequently, whether a point is spurious local minima of GaLore is determined by the optimization landscape in M, rather than in M. However, this does not imply that the optimization landscape of GaLore is identical to that of the full-rank method. This difference arises because GaLore constrains the parameters to remain within M after each projection. Thus, the optimization process restricted M. while the determination of spurious local minima depends on the landscape in M. To formalize this concept, we introduce the definition of projected spurious local minima.
Definition 4.8 (Projected spurious local minima). Let θ M be local minimum of the objective
function 2 If there is no continuous function h [0, 1] 7 M that satisfies (i) h[0] θ and
h[]] = for a global minimum I' E M of the objective function 2 and (ii) & + E(gn [t]) is nonincreasing, we call the parameter O projected spurious local minimum.
Based on the definition, we have the condition of no spurious local minima for GaLore.
Theorem 4,9 (No projected spurious local minima condition for GaLore). For the network defined by Eq. ( w,, minimal width of the network, no less than 2r, where r is the rank of GaLore, then the objective function (2) has no projected spurious local minima with GaLore.
The condition is 2r instead of 2m(n + 1)¹ indicates that GaLore is less vulnerable to spurious local minima compared to the full-rank method. Spurious local minima are suboptimal solutions that can trap the optimizer and prevent it from reaching a globally or near-globally optimal solution. By reducing the likelihood of encountering such minima, Gal.ore benefits from smoother and more favorable optimization landscape, which allows the optimizer to explore more promising regions of the parameter space. This explains why GaLore trains faster and, some cases, surpasses the full-rank method in performance. This theorem is further verified in Figure of Section 6.1
4.3 DISCUSSION
In the above, we establish that GaLore offers the most favorable optimization landscape, whereas LoRA's landscape is the least advantageous. However, this does not necessarily mean GaLore will outperform the full-rank method in terms of final results. The superiority of one method depends on whether expressiveness or the optimization landscape's quality has greater impact. Intuitively, for smaller networks, where the optimization process is simpler but expressivity is limited, the full- rank method may perform better. Conversely, for larger networks, where expressivity sufficient for good results and the optimization process is more complex, GaLore tends to excel. Accord- ing to Theorem 4.9 the absence of spurious minima is guaranteed only when the rank r is small. Initially, increasing improves GaLore's expressivity, allowing it to model more complex func- tions effectively. However, r becomes too large, the optimization landscape may degrade due to the emergence of spurious local minima or poorly conditioned regions, even though expressivity continues to increase. When expressivity is not the primary performance bottleneck, we expect Ga- Lore's performance to improve with increasing r, but decline as r approaches the network's width, where the landscape quality diminishes. These conclusions are tested and validated in Section 6.1 with empirical results confirming this theoretical behavior.
GARARE: GRADIENT RANDOM PROJECTION
According to the analysis in Section GaLore has good optimization landscape, characterized by the same range of region that satisfy the PL. condition condition and a higher likelihood of avoiding spurious local minima compared to full-rank methods. The key point is GaLore project the gradient matrix to low-rank spaces with projection matrices. In GaLore the matrices are obtained by performing SVD to the gradient matrix, which is both cine-consuning and memory-consumingg However, to achieve the low-rank projection, we only need matrices with the same size as those of GaLore. Inspired by this intuition, we propose our new algorithm, which uses random matrices instead of the matrices derived by SVD.

---

Published as a conference paper at ICLR 2025
Table I: Comparison of GaRare, GaLore and LoRA. Assume E IRxx, rank v.
GaRare
GaLore
LoRA
Weights Optim States
pq
pq
pq + pr + qr
2gr
pr + 2qr
2pr + 2qr
Multi- Multi-Subspace
Pre- Tre-irinnnn
Fine-Tuning
5.1 ALGORITIIM AND THEORETICAL GUARANTEE
Note that it is infeasible to use arbitrary matrices that have the same size as Galeore, the vectors contained within these matrices must be linearly independent; otherwise, the projected spaces will have an effective rank lower than r. Fortunately, the following lemma shows the matrix generated by Gaussian distribution satisfies this almost surely.
Lemma 5.1. Given matrix R E Rexr (r < m), the elements of R are generated by Gaussian distribution N (0, o²), then we have P(rank(R) -r)=
The proof is deferred Appendix A.3 Based on this result, we analyze whether the random matrix can maintain the property identified by Theorem
4.3 and 4.9
Corollary 5.2. Under the condition of Theorem 4.2 if the random matrix R E TPXx is generated
from (O, 1/p), and the number of training samples r &' then if the network width 52
mm R*1+2
the square loss satisfies p-PL." condition with high probability over the ball
(Ao (A0-M}²)
B)O,
Corollary 5.3. For the network defined by Eq. D. if w,, minimal width of the network, less than 2r, where is the smaller dimension of the projection matrix, then the objective function funnttino has no projected spurious local minima.
The proof of the two corollaries is deferred Appendix A.3 These corollaries ensure that GaLore's properties are preserved as long as the projection matrix is generated using N (0, 1/p). Based on this, we propose Gradient Random Projection (GaRare), which replaces the projection matrices in GaLore with certain random matrices. GaRare retains the same hyperparameters as GaLore, includ- ing the scale factor a and subspace update frequency T. The scale factor a controls the strength of the low-rank update, similar to the a/r scale factor used in the low-rank adaptor of Hu et al.) (2022). The subspace update frequency specifies how often the random matrices are refreshed, with the random seed changing every T' steps. The pseudo-code for GaRare is provided in Appendix
The process of GaRare seems similar to that of FLoRA (Hao al. 2024). as both use a random matrix to project gradients. However, FLoRA is derived from the theory of LoRA and is designed to mimic its learning dynamics. In FLoRA, the random matrix is generated using (0, 1 1/pr). which leads to violation of Corollary (.2) Consequently, FLoRA does not share the same optimization landscape as Galore and GaRare. This distinction is further verified our experimental results.
5.2 MEMORY USAGE GARARE
We briefly analyze the memory usage of LoRA, GaLore, and GaRare here, with more detailed discussion in Appendix G LoRA requires storing the low-rank matrices E Rax and RR"x along with the full-rank weight matrix θ R2'9, resulting in pg + pr + qr weights, plus an additional 2pr + 2gr for optimizer states. GaLore reduces storage by eliminating B and A, retaining pg weights but adding pr + 2qr for optimizer states and the projection matrix. GaRare uses the same structure as GaLore but further minimizes memory usage by dynamically generating a random matrix at each iteration, requiring only 2gr for optimizer states and avoiding storing the projection matrix. A summary of memory usage is provided Table [ Although FLoRA matches GaRare in memory usage, its inferior optimization performance makes GaRare the focus of this analysis.

---

Published as a conference paper at ICLR 2025
Hiddon dim=256
Hidden dim=5
Hidden dim=1 1024
0.58
0.68
0.88
0.58
0.98
Accrray
0.52
Apcuracy
0.62
0.82
0.50
0.60
0.50
0.4
0.44
0.44
042
0.42
0.22
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
Timestop
165
Timestep
166
Timestap
1a5
GoLore
GaRare
LoRA
FLoRA
Fullrank
Figure 1: The performance of GaLore, GaRare, LoRA and Full-rank method on CIFAR-10 dataset. The dimension of hidden layers is set to be 256, 512 and 1024, while the rank for the low-rank adaptation methods are set as 128, 256 and 512, respectively.
EXPERIMENTS
In this section, first verify our proposed theorems in simple dataset. Then we evaluation GaRare on both pre-training and fine-tuning of LLMs. All experiments run on NVIDIA A 100 GPUs.
6.1 VERIFICATION OF THE THEORY
In this section, we describe the experiments conducted to validate our theoretical claims related to feedforward neural networks. specifically Multi-Layer Perceptrons (MLPs). We use the CIFAR- 10 dataset (Torralba et al. 2008 for our experiments. All experiments are training in 30 epochs. The learning rate selected from set of {le lc ..... 1e- "), and the best learning rate is chosen based on the final accuracy. detailed description of the network architecture is provided in Appendix B.1 The experiment results averaged
three random seeds.
As discussed in Section 4.3 Theorems 4.3 and 4.9 indicate a trade-off between the expressivity of network and its optimization landscape in Gorere. To illustrate this, adjust the hidden layer dimensions the MI.ss to three settings: 256, 512, and 1024. When the dimension is smaller, expressivity limits performance: conversely, larger dimensions improve optimization landscapes, leading to enhanced performance. Additionally, GaRare is expected to perform similarly to GaLore, as indicated by Corollaries 5.2 and and 5.3 In our experiments, we set the rank for low-rank adaptation methods to half of the hidden layer dimensions, specifically 128, 256, and 512. The primary metric for evaluation is the prediction accuracy on the test dataset.
The experimental results, illus- trated in Figure [ show that LoRA exhibits worse perfor- mance than GaLore and GaRare across the three network config- urations, underscoring its sub- optimal optimization landscape. FLORA shows similar perfor- mance LoRA, which in line with the conclusion of et al. (202).. In contrast, the perfor- mance of the other three meth- ods is better especially when the dimensionality of the hid- den layers large. Specifi- cally, with hidden dimension of 256, the full-rank method out- performs GaLore and GaRare due the limited expressivity being the performance bottleneck. At a hidden dimension of 512, all three methods demonstrate similar performance levels. However, when the hidden dimension increases to 1024, both GaLore and GaRare outperform the full-rank
GaLore
GaRare
0.50
0:52
0.52
0.50
3.50
0:50
3.66
8:58
6.42
0.42
8.40
Timestop
10
Timesiip
rarke8
Figure The performance of GaLore and GaRare on CIFAR-10 dataset with different ranks.
8

---

Published as a conference paper at ICLR 2025
Table 3: Comparison with low-rank adaptation methods on pre-training various sizes of LLaMA models on C4 dataset. Validation perplexity reported, along with memory estimate of the total of parameters and optimizer states based on BF16 format.
60M
130M
350M
IB
Full-Rank
34.06 (0.34G)
25.08 (0.79G)
18.80 (2.16G)
15.56 (7.85G)
LoRA
34.99 (0.28G)
33.92 (0.63G)
25.58 (1.38G)
19.21 (4.75G)
FLoRA
36.97 (0.26G)
30.22 (0.53G)
22.67 (1.19G)
20.22 (3.98G)
Galore
34.88 (0.26G)
25.36 (0.56G)
18.95 (1.25G)
15.64 (4.23G)
GaRare
34.45 (0.260)
25.34 (0.53G)
19.35 (1.19G)
15.88 (3 (3.98G)
r r/danddel
128 / 256
256 / 768
256 / 1024
512 / 2048
Training Tokens
I.IB
2.2B
6.4B
13.IB
method, suggesting that sufficient expressivity allows the optimization landscape to dominate the final performance outcomes.
Furthermore, explore the impact of rank selection on GaLore and GaRare by setting the hidden dimension at 1024 and testing four different ranks: 8, 256, 512, and 800. According to Theorem 4.9 the absence of spurious local minima guaranteed when the rank does exceed 512. Therefore, we hypothesize that performance should increase as the rank increases up to 512, due to improved expressivity without compromising the optimization landscape. Beyond this threshold, however, trade-off between expressivity and optimization landscape might impair performance. The results, depicted in Figure support this hypothesis: performance improves rank increases from 8 to 5 512, but begins to decline when the rank reaches 800.
is also noteworthy that GaLore and GaRare exhibit similar performance in most experimental con- ditions, with exceptions when the hidden dimension is 256 with rank of 128, and when the hidden dimension 1024 with a rank of 8. These deviations can attributed to Cor 5.2 and [.3 which ap- ply when the network is sufficiently large. The discrepancies in these specific conditions suggest that the network scale is too small to align with these theoretical assurances. These experiments on the CIFAR-10 10 dataset validate theoretical deductions and confirm the intricate dynamics between network configuration and performance outcomes.
6.2 PERFORMANCE ON PRE-TRAINING TASKS
To evaluate the performance of GaRare, we apply it to train LLaMA-based large language models using the C4 dataset. The C4 dataset is colossal, cleaned version of the Common Crawl web corpus, designed primarily for pre-training language models and word representa- tions (Raffel et al. 2019). We follow the experimen- tal setup outlined by Zhha et al. (2024), which utilizes a LLAMA-based architecture incorporating RMSNorm and SwiGLU activations (Shazeer 2020 Touvron et al. 2023). For each model size, we use the same set of hyper- parameters across methods, except for the learning rate. Both GaRare and FLoRA have their learning rates tuned under the same computational budget, and we report the best performance achieved. For the other methods, we present the results reported in ZZha et al. (2224.. All experiments are conducted in BF16 format to optimize memory usage. Detailed de- scriptions of our task setups and hyperparameters are provided in Appendix B.2
Table 2: Pre-training LLaMA 7B on C4 dataset for 30K steps. Validation perplexity and memory estimate are re- ported.
Mem
30K
8-bit GaRare
16G
19.94
8-bit GaLore
18G
19.93
8-bit Adam
26G
20.05
Tokens (B)
3.9
We report the final validation perplexity of the methods in Table 3 GaRare, GaLore, and the full- rank method exhibit comparable performance, outperforming other low-rank adaptation methods. While GaLore reduces memory usage, GaRare achieves even greater memory efficiency. Although FLoRA matches GaRare in memory usage, its performance is significantly worse. Furthermore, the comparable performance of GaLore and GaRare the -LaMA-baser structure suggests that our theory has the ability extend to other network architectures.

---

Published as a conference paper at ICLR 2025
To demonstrate the scalability of GaRare, train the 7B model using this method. Similar to Ga- Lore, GaRare can be applied to various learning algorithms, particularly memory- optimiz- ers, to further reduce the memory footprint. In this experiment, nique (Loshchilov & Hutter 2019) and compare 8-bit GaRare with 8-bit Galore and 8-bit Adam. Due to computational resource constraints, the model is trained for 30K steps using 3.9B tokens. The results are presented in Table 2 GaRare achieves performance comparable to GaLore while providing greater memory efficiency, reducing memory usage by up 10%, and eliminating the need for SVD computation. Notably, GaRare and GaLore outperform the full-rank method within the 30K steps, highlighting the superiority of their optimization landscapes.
incorporate the 8-bit Adam tech-
6.3 PERFORMANCE ON FINE-TUNING TASKS
We evaluate GaRare for fine-tuning the GLUE benchmark (Wang et al. 2019). which comprises variety of tasks such sentiment analysis, question answering, and textual entailment. In this experiment, fine-tune pre-trained RoBERTa models on GLUE tasks using GaRare and compare its performance with other methods. For LoRA, we use the hyperparameters from Hu et al.) (2022). for GaLore, learning rate and batch size. Detailed hyperparameters can be found in Appendix B.3] As shown in Table 4 GaRare delivers performance comparable to GaLore while outperforming other low-rank adaptation methods in both RoBERTa-Base and RoBERTa-Large models. GaRare has the smallest memory footprint among all methods. Although FLoRA has the memory usage GaRare, it exhibits poorer performance. This demonstrates that GaRare is an effective full-stack memory- efficient training strategy for both LLM pre-training and fine-tuning.
tune the the settings from Zhao al. (2024), and for GaRare and FLoRA,
Table 4: Performance on GLUE with RoBERTa-Base and RoBERTa-Large model. We report the average score of all tasks.
RoBERTa-Baa
RoBERTa-Large
Full-Rank
GaRare
GaLore
FLoRA
LoRA
Full-Rank
GaRare
GaL.rre
FLoRA
LoRA
Memory
748M
252M
253M
252M
2132M
718M
720M
718M
732M
CoLA
62.2
61.1
59.0
67.9
65.5
STS-B
90.9
90.3
89.9
92.3
92.5
MRPC
91.3
91.5
92.3
88.5
91.1
90.9
91.7
91.7
89.3
90.9
RTE
79.4
79.3
79.4
76.5
78.7
86.6
87.4
87.0
83.0
87.4
SST2
94.6
94.4
94.0
93.8
92.9
96.4
96.2
96.1
96.0
96.2
MNLI
87.2
87.2
87.0
86.6
86.8
90.2
91.3
90.8
90.4
90.6
92.3
92.3
92.2
91.9
94.7
94.6
95.7
94.0
94.9
QQP
92.3
90.9
91.1
90.9
92.2
91.8
91.9
91.5
91.5
Avg
86.3
85.9
85.9
84.6
85.6
88.8
89.2
89.3
87.8
CONCLUSION
This work presents comprehensive analysis of the optimization landscapes of prevalent fine-tuning methods, including the full-rank approach, LoRA, and Gal.ore. Our theoretical findings reveal that GaLore offers more favorable optimization landscape compared LoRA and the full-rank method, as it is less prone to spurious local minima and operates within broader region that satisfies the PL' condition. This explains GaLore's 's faster convergence and superior performance relative the other methods, In contrast, LoRA, while being memory-efficiee optimization landscape, which accounts for its slower convergence. Based on these insights, we troduce GaRare, a memory alternative to Gal.ore that retains similar optimization benefits. Experimental results confirm GaRare's effectiveness in large language model tasks. Additionally, thcoretical findings highlight the power of the gradient projection framework, underscoring its potential to drive future advancements in efficient fine-tuning algorithms.
struggles with more challenging
Our theoretical analysis is confined MLP architectures, which limits the applica- bility our findings and may also impact the performance of the derived algorithms. We consider extending this analysis to other architectures. such as Transformers, part of our future work. New theoretical insights could lead to the development of novel algorithms, potentially resulting in further performance enhancements and reduced memory usage.
Limitations:
10

---

Published as a conference paper at ICLR 2025
8 REPRODUCIBILITY STATEMENT
The proof of the theoretical results is provided in Appendix A The assumptions and conditions for the theorems are stated within the theorems themselves, and limitations are discussed in Sections 4.3 and 7
The pseudo-code for the algorithm is available in Appendix C
The model structure and hyperpa- The source code is included in the supplementary material.
rameters are detailed in Appendix B
REFERENCES
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the ef- fectiveness of language model fine-tuning. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natu- ral Language Processing, (ACL/ICCLPP) 21 pp. 7319-7328, Virtual, Event, 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning (ICML' 19), volume 97, pp. 242-252, Long Beach, CA, 2019.
Yoshua Bengio and Olivier Delalleau. On the expressive power of deep architectures. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory (ALT' 11), volume 6925, pp. 18 36, Espoo, Finland, 2011.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems 33 (NeuriPS 20), Virtual event, 2020.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals and Systems, 2(4):303-314 1989.
Simon S. Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference Machine Learning (ICML' 19), volume 97, pp. 1675-1685, Long Beach, CA, 2019.
Yongchang Hao, Yanshuai Cao, and Lili Mou. Flora: Low-rank adapters are secretly gradient com- pressors. In Proceedings of the 41st International Conference on Machine Learning (ICML'24), Vienna, Austria, 2024.
Soufiane Hayou, Nikhil Ghosh, and Bin Yu. Lorat: Efficient low rank adaptation of large models. In Proceedings of the 41st International Conference on Machine Learning (ICML'24), Vienna, Austria, 2024.
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural Networks, 3(5):551- 560, 1990.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. In Proceedings of the 10th International Conference on Learning Representations (ICLR'S 22), Virtual Event, 2022.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kemel: Convergence and generalization in neural networks. In Advances Neural Information Processing Systems 31 (NeurIPS' 18), pp. 8580-8589, Montréal, Canada, 2018.
Ajay Jaiswal, Lu Yin, Zhenyu Zhang, Shiwei Liu, Jiawei Zhao, Yuandong Tian, and Zhangyang Wang. From galore to welore: How low-rank weights non-uniformly emerge from low-rank gradients. arxiv preprint arXiv:2407.1 1139, 2024.

---

Published as a conference paper at ICLR 2025
Uijeong Jang, Jason D. Lee, and Ernest K. Ryu. Lora training in the NTK regime has spuri- ous local minima. In Proceedings of the 41st International Conference on Machine Learning (ICML'24), Vienna, Austria, 2024.
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. In Advances in Neural Information Processing Systems 35 (NeurIPS:22) New Orleans, LA, 2022.
Johannes Lederer. No spurious local minima: on the optimization landscapes of wide and deep neural networks. arxiv preprint arXiv:2010.00883, 2020.
Li'an ang Li, Yifei Duan, Guanghua Ji, and Yongqiang Cai. Minimum width leaky-relu neural net- works for uniform universal approximation. In Proceedings of the 40th International Conference on Machine Learning (ICML (33, volume 202, pp. 19460-19470, Honolulu, Hawaii, 2023.
Pengxiang Li, Lu Yin, Xiaowei Gao, and Shiwei Liu, Owlore: Outler-weighed layerwise sampled low-rank projection for memory-effiiiet LLM fine-tuning. arXiv preprint arXiv:2405. 18380, 2024.
Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. Relora: High- rank training through low-rank updates. In Proceedings of the 12th International Conference on Learning Representations (ICLR 24), Vienna, Austria, 2024.
Cheng Lin, Lujun Li, Dezhi Li, Jie Zou, Wei Xue, and Yike Guo. Nora: Nested low-rank adaptation for efficient fine-tuning large models. arxiv preprint arXiv:2408. 10280, 2024a.
Yang Lin, Xinyu Ma, Xu Chu, Yujie Jin, Zhibang Yang, Yasha Wang, and Hong Mei. Lora dropout as a sparsity regularizer for overfitting control. arxiv preprint arXiv:2404.09611 2024b.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In Advances in Neural Information Processing Systems 33 (NeurIPS'20) 20)), Virtual Event, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
Shih-Yang Liu, Chien-Yi Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang. Kwang- Ting Cheng, and Min-Hung Chen. Dora: Weight-decomposed low-rank adaptation. arXiv preprint 21t.:22002.0955333 2024.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of the 7th International Conference on Learning Representations (ICLR' 19), New Orleans, CA, 2019.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Advances in Neural Information Processing Systems 30 (NeurIPS' /7), pp.
Long Beach, CA, 2017.
Fanxu Meng, Zhaohui Wang, and Muhan Zhang. Pissa: Principal singular values and singular vectors adaptation of large language models. In Advances in Neural Information Processing Systems 38 (NeurIPS'24), Vancouver, Canada, 2024.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterizaatoo:: Global conver- gence guarantees for training shallow neural networks. IEEE J. Sel. Areas Inf. Theory, 1(1): 84-105, 2020.
Hoifung Poon and Pedro M. Domingos. Sum-product networks: A new deep architecture. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI'11), pp. 337- 346, Barcelona, Spain, 2011.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arxiv preprint arXiv: 10683, 2019.
12

---

Published as a conference paper at ICLR 2025
Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gomez Colmenarejo, Alexander Novikov, Gabriel Barth-Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, et al. A generalist agent. arXiv preprint arXlv:2205.06115. 2022.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L. Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi. Photorealistic text-to-image diffusion models with deep language understanding. In Advances in Neural Information Processing Sys- tems 35 (NeurIPS') 22), 2022.
Noam Shazeer. GLU variants improve transformer. arxiv preprint arXiv:2002.052002 2020.
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE transactions on pattern analysis and machine intelligence, 30(1 (0(11))1988-1900 2008.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshor, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura. Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. arxiv preprint arXiv:2307.0000 092888, 2023.
Alex Wang, Amanpreet Singh. Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 7th International Conference Learning Representations (ICLR' 19), New Orleans, LA, 2019.
Wenhan Xia, Chengwei Qin, and Elad Hazan. Chain of lora: Efficient fine-tuning of language models via residual learning. arxiv preprint arXiv:2407. 04151, 2024.
Adam Yang. Maxime Robeyns, Xi Wang. and Laurence Aitchison. Bayesian low-rank adaptation for large language models. In Proceedings of the 12th International Conference on Learning Representations (ICLR'24) 24). Vienna, Austria, 2024.
Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. In The Twelfth International Conference Learning Representations (ICLR'24), Vienna, Austria, 2024.
Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficient I1m training by gradient low-rank projection. arXiv preprint arXhv:2403.33507. 2024.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arxiv preprint arXiv: 1,08888, 2018.
A DETAILS OF THE PROOFS
A. PROOFS OF SECTION
A.1.1 DERIVATION OF THEOREM 4.1
Theorem 4.1 comes from two results from Liu et al. 2022
Theorem A.1 (Theorem of et al. 2022 ). If Amin (K(9)) 2 p > 0, AA E M, then the square
loss function {(ge) (x) 2 satisfies p-PL. condition M.
13

---

Published as a conference paper at ICLR 2025
Proof.
Vi(go))12 (go(x) -))" -)
Amin Amin (x(0))))90(x)) - -y1 [ 2 pl(ge)
This theorem shows Amin (e()) 2 p is sufficient condition of PL" condition. is also
necessary condition in a certain sense:
Theorem A.2 (Proposition of (Liu al. 2022 ). Amin (K(@))) = 0, then the system ge(x) = y
cannot be PL condition for all on any set M that contains θg-
Proof. Since Amin (ainn(((e)) (K()) = O, we can choose rey so that K (x) -y) = 0 and goo (x)
y * 0. Therefore,
1 (00(()) (xe(x))>))"(0((((((3) -
2 Ve(ge.))
This theorem implies it is also a necessary condition.
A.1.2 PROOF THEOREM
We first introduce one definition and two useful lemmas.
Definition A.3 (Uniform conditioning). We say that ge is p-uniformly conditioned (μ M c R' if the smallest eigenvalue of its targent kernel (()) satisfies
Amin (K(O)) Z μ. VO M.
According to Theorem A.1 if (()) is p-uniformly conditioned, it p-PL" condition. Let Hg be 8²
the Hessian matrix of function g, i.e. (Hy)s 00.00;
Lemma A.4 (Theorem 2 of Liu et al. (2022)). Given Oo. suppose the targent kernel matrix K(O,) is strictly positive definite, i.e., Ao == Amin (K (0o)) 0. If the Hessian spectral norm Aw-P
||Hي|| < 2T.,//R holds within the ball B(O,, R) for some R and > 0, where Lg is the Lips- chitz constant of then the tangent kernel K K()) is p-uniformly conditioned the ball B(Q,, R). Hence, the square loss satisfies the p-PL." condition in B(Q.. R).
Lemma A.5 (Theorem 3.2 Liu al. (2020)). Consider a neural network ge of the form Eq. 4 Let w be the minimum of the hidden layer widths, iee. w minjet p'. Given any fixed R >> O, and any θ B(0,, R), with high probability over the initialization, the Hessian spectral norm satisfies the following:
[H,[ = / /V
Lemma A.6 (Singular value product matrices). Suppose two matrices P and Q satisfies P pmxn Q E R let >²(:) and )-iu(-) be the i-th and minimal singular value of one matrix,
respectively, then
xx(PQ) Amin (P)),(Q)-
Proof.
x(PQ))
max S:dim[
min zES. |=||=
[PQr]
2 Amin (P).
max 8 siimm
min ZES.
||Q=]]
=1
= Amin (P)
14

---

Published as a conference paper at ICLR 2025
Then start our proof. Before projection, GaLore has the same tangent kernel ( and Hessian
matrix Hg as full-rank method. According to Lemma A.5 under the given condition, H (+)l =
Õ /vw). Directly plugging this into the condition of Lemma A.4 let e Ào - μr we get K ( ju-uniformly conditioned on the ball (0,,
During the projection process, GaLore first project the gradient matrix to a low-rank space, and then projects it back to full-rank space. Therefore, if K(O) still j--nnioomly conditioned on the ball O R), where K{)) is the tangent kernel after the projection process, the conclusion of Theorem 4.2 holds for GaLore based on the fact ((+) is j-uunformly conditioned. In the follows,
we analyze the singular values of K()). The analysis divided into two steps, the first step is to only consider one-layer neural network, and the second step is to generalize the result to multi-layer neural networks.
Step I:
For one-layer neural network, suppose the gradient matrix for the i-th sample G, E RPx0 where p < q. GaLore performs SVD to Go.
Go Go=UEV
where U E RexP and V E [2*4 are orthogonal matrices, 2 E RPX4 is a diagonal matrix. For rank r, the projection matrix is selected as U = Ui: r] E R**p, i.e., the first three rows of original U. Then G is projected by O and projected back by ÜT, After the projection process, the gradient
matrix G₃ becomes
--=0" =
According to the definition K(0), K(0) = Dgg (Dgs) and
vec Go) vec(Gi)
Dg0
where vec(G;) is the row vector transformed from matrix Gi. Thus, vec(G.) IRP9 and Dgo mmx,o After the projection process, Dgn becomes
vec(Gu)
vec(G1)
Dyo Dye
Lvee(G Gm
Let Ig be the q q identity matrix and & be the Kronecker product. Then we have
Dgo Dgo (1, (4)
According the definition of Kronecker product, In Ú results matrix consisting of q copies of the matrix Ü arranged along the diagonal, with other positions filled with zeros. Therefore, Ig & Ú E R
Note that Ô is the first rows of orthogonal matrix U, A(()) = 1 for i S Therefore, &0) = for i S rg. According Lemma A.6
Amin (Doe) (D
>n go (1, (1,))
(4)
Amiu (D )m (1)
p.
15

---

Published as a conference paper at ICLR 2025
The last inequality comes from Amia (Dss) Amin (K())) and the assumption $ rq. Thus, K (() is also j-uniformly conditioned and then conclude the proof.
Step 2: For multi-layer neural network, the gradient matrix not only one G, but a series of matrices GP. ......, G where is the number of layers. Let Ü, be the projection matrix for G. in this situation,
(1 2 UO)
(1 8
D D
(1, U,)T
For such a block diagonal matrix, the blocks are independent of each other, allowing for analysis of each block individually. According to the conclusion of Step I, An (Daa) 2 if S r(p + +p'
+p)).
A.1.3 PROOF OF THEOREM 4.4
When applied LoRA, the network defined by Eq. ( becomes
Jel x == ( [[09][0
(5)
where 0 E Re'x xr 0 Rx and is identity function. Apply Lemma A.5 to Eq. have
we
[H) Ô( /VT).
Combine this result with Lemma A.4 we get the final result.
A.2 PROOF OF THEOREM 4.9
We follow the analysis framework of Lederer (2020) In this section, we introduce essential concepts related to path relations and block parameters.
Definition A.7 (Path relations). Consider two parameters O, Г E M. there is a continuous function herr [0, 1] M that satisfies he,r(0] O, he.r(1] = Т, and + ((ghe.r(t) is constant, we say that @ and I' are path constant and write e ++ I.
If there is continuous function herr [0, 1] - MM that satisfies he.r(0) O, herr(1] r, and 1 ++ f [q]] is convex, we say that θ and are path convex and write θ 9- r.
there are parameters O', I' E M such that (i) θ + e' and P < and (ii) O' 9+ r', we say that θ and I are path equivalent and write @ om r. Definition A.8 (Block parameters). Consider a number E {0, 1,.... and a parameter θ E M. If
1. (0/); for all 8;
2. (0"),; 0 for all v (1,... 1} and i >> and for all E (l...., 1} and 8:
3. (0)); )iy for all s.
call O s-upper-block parameter of depth I.
Similarly, if
1. (0)), 0 for all j 5 pp1
2. (0"), 0 for all e {l,..., 1) and i S pp--1_ and for all (1....,/ / 1} and
j S p" s;
3. (0 )ij for all < -,
call θ an s-lower-block parameter of depth 1. We denote the sets of the --upper-block and looer-block parameters of depth / by Un, and L.,, respectively. According to the definition of block parameters, My.t M,, Then propose the following proposition.
16

---

Published as a conference paper at ICLR 2025
Proposition A.9. For every ④ E My. there are 0,0 E M with θ Un and O Cu,t such that O θ and θ ++ O
The proposition implies every parameter O E MM, it is path constant to j-uppeer-looc parameter and a y-lower-block parameter. To prove this proposition, we introduce two lemmas. The first lemma is proposed by Lederer (2020), while the second lemma will be proven here.
Lemma A.10 (Lemma 3 of Lederer (2020)). Consider permutations pd {1. (I.....P')
fI..... p²} for j E fo....,I +1.. Assume that pd and p are the identity functions: pO1]
pl for all j. The parameter @ E . is spurious local minimum of the objective function 2f and only ifT M defined through (T')ue == (@)) (n] for all j E {O.....!),e)
(I.....')
and U E (1....,"') is a spurious local minimum of the objective function 2
Lemma A.11. Consider three matrices A Ruxe B R and C E IR and a function h: I I.. With some abuse of notation, define h : Roxr - -Rexx through (h(M))s h[May] for all M E <Rux,, Assume the rank of BC is no larger than μ., then, there are matrices A E Ruxx
and B Roxo and a permutation p (1.....uu (1,...,?? 2) such that
A[hB[c]] [.I]BB[C]]]]
= j μi Byt for p and By, (B*), otherwise.
Similarly, there are mutrices A E Rux" and B E RR"x and permulation p (1,...,u} (1.....0) such that
A A, [,I]BBC
A, = 0. S pi: Bj; = 0 for S 2- and B,; = (B") otherwise.
Proof. Step a E u1. We first show that there a matrix À Ruax such that
1. AM[B]] Ah[BC]:
2. (j E [L...... o) Aus # 0} S p;
3. Auj Aus for all #* + k.
For every 1 E fl..... u) and i E (1....,r] elementary matrix algebra yields that
(Ah(BC)ss = Σ Akg (h(BC)))
Denoting the row vectors of a matrix M E Raxb by Mi...... Mas E Rd, we then get
(AN[BC))&+ Σ An5(1(BC))5
That is, (Ah[BC])k- lies in the space spanned by [([[BC]), -ー Because the rank of BC' is no more than m, there is at most (N[BC)), jo are linearly independent. Suppose the linearly indepen- dent vectors are [M((CC)),..
can be rewritten as:
(Ah[BC])&.
Σ t, (k(BC)),. #=1
Define
his
for a = k,j = js:
Auj
0
for k,j + jai otherwise.
Aaj
17

---

Published as a conference paper at ICLR 2025
Then Aaj follows the above three properties.
Step We then show that there is matrix À R such that
1. Ah[BC] Ah[BC]
2. # ( E [L....,.) o) Aus + 0, E (I....,, uf} S p.
Since Step I changes only the kth row of A, we can apply to one row after another.
Step 3: By Property 3 of the previous step, the matrix Á has at most μ nonzero columns. Verify that replacing A by Ap and B by Bp for suitable permutation leads to À whose entries outside the first j columns are equal to zero. We denote this version of Á by A. Note that
(MBPC))) = h ((BC)))) h
Σ (P) S6
Σ (CT (CTTBBBBB))) (0))
h
h
(BP)))
Combining this result with the results of Step (with A and B replaced by Ap and BP) yields for all E (l, and E [I. that
(A,M(BPC))a E (M(B))) Σ (BP))()))))))))))
min(u.))
(h(C (B3);
Σ 5=1
Aos (BB)
We then define B E ux through
(B")s
Bybji for S μ4; otherwise.
Bis 10
Then we have
min (v.0)
(A)h(BBC)a
Σ
(BP):)((
min(n.0)
min(u.))
Σ
Ang [h(" B)))=
B)))==
Σ
An,(h(BC))
AajlB(B))) (Ah(BC])a
The second part of the lemma can be derived in the same way.
Then start to prove Proposition A.9
18

---

Published as a conference paper at ICLR 2025
Proof of Proposition A.9 To facilitate the proof, define the data matrix X E R through Xji == (Ii), for all j E {1...., df and é E {l...., n), that is, each column of consists one sample. We finally write
ge [X] (gelzi),.... (e(n))) el -' f' ...
X]] f (0
R mx
for all @ M. Hence, ge [X] summarizes the network's 's outputs for the given data.
Given a parameter θ E Mr we establish corresponding upper-block parameter O E Us layer by layer, starting from the outermost layer. write
ge [X] =
O'- p (
=:AERo+1 =th =: =:BER xpl
CeRR 1xm
Lemma A.11 for two-layer networks then gives
[(+)]] 11.1000-....
ge X =x]=
for matrix @ E 12 xp' that meets Condition 3 in the first part of Def. A.8 on block parameters as long as 2 μ and for a matrix e¹ E Ruxxy that consists of the first rows of the matrix O!-1, Here we ignore the permutation in Lemma A. because of the symmetric property identified by Lemma 10 (We implicitly assume here and in the following p 2 μ for all j E (I,...,().)
Now, define parameter I'
.M through
I : 00' ,0.,,,0,0 09)
and function herr: [0, M₁ through
her = (1- 11 for all / E [0,
The function h is continuous and satisfies h [0] = θ and he.r= = rV. Moreover, we can 1. use the definitions of the function he,r and the networks, split the network along the outermost
layer, 3. invoke the block shape of @' and the definition of e- as the μ first rows of the matrix e 4. use the above-stated inequalities for the network ge [X], and 5. consolidate the terms to show for all E [0, 1] that
re [[[]] ((1 t)e' +
(1
(1 t)e f M t5' (00 ...
(1 - 1)ge XX] - Igo [X]
[e]
Hence, the function + ((ghe is constant. Suppose O UE. That is, θ and Is are path constant: θ ++ pdd
We then move one layer inward. Similar to the above derivation, we have
t o (2 - - [ ... 1
x
for matrix --11 E = that meets Condition 3 in the first part of Def. A.8 block parameters as long as s 2 14, and for matrix 8¹-² 2 e Ruxpf=2 that consists of the first rows of the matrix !
19

---

Published as a conference paper at ICLR 2025
Next, we define O E <R''xpp"
through
uv
for u S μ otherwise.
uu
Combining this definition with the above-derived results yields
ge X o' -' (()
and the matrix 3 meets Condition 2 in the first part of Def. A.8 on block parameters as long as 2 μ..
Similarly above, define parameter I E .M through
p=-1 = (0', e 1-1 O 15-2,,..,09 0
and function hygre 1: [0, 1] -> M through
brir [8] = (1 t)1 + + 1 for all t [0,1]
show that T ++ pl-1, In view of Property Lemma we can conclude that 4 P'-1 The proof can be finished by induction over the layers.
We state additional propositions by Lederer 2020), they necessary complete proof. Proposition A.12 (Proposition 3 Lederer 2020)). Consider two block parameters θ E Us. and
E' L.p. If w 2 2s, holds that è ewp
Proposition A.13 (Prop of Lederer (2020) Assume that for all θ E M, there is a global mini- mum of the objective function (4), denoted by T, such that @ emm Т. Then, the objective function (4) has no spurious local minima.
Let the global minima is Т. For any parameters θ M,, according to Proposition A.9 there exists O E Un such that O G. Similarly, there exists [ E Lu,, such that r <+ L.
I. Note that this relationship holds for all θ Mμ, we conclude that the objective function has no projected spurious local minima. Then we complete the proof of Theorem 4.9
According to Proposition A.12 +
L. Therefore,
A.3 PROOF OF SECTION
A.3.1 PROOF OF LEMMA 5.1
To prove that random matrix R gxxT (with m) whose entries are independently drawn from a Gaussian distribution (0, o²) has full rank with probability 1, we need to show that the probability of rank(R) R)) < is zero. Here's how we can establish this:
A matrix R has rank less than if and only if there exists non-zero vector x E R" such that:
Rx = 0
This equation represents a homogeneous linear system. For to have non-trivial null space, the columns of R must be linearly dependent.
The set of rank-deficient matrices can be characterized by the vanishing of r x r minors (deter- minants of submatrices). These minors are polynomial functions of the entries of R:
det RRx) 0 for all k
20

---

Published as a conference paper at ICLR 2025
where R3 denotes the submatrix formed by selecting any rows from R.
The set where these determinants vanish is an algebraic variety defined by polynomial equations. In Rmxr, such set has Lebesgue measure zero.
Since the set of rank-deficient matrices has Lebesgue measure zero and the distribution of Rt is absolutely continuous (Gaussian distribution), the probability that R is rank-deficient is zero:
P(rank(R) <) =
Therefore, the probability that R has full rank is:
P(rank(R)) R =)) P(rank (R) <r) =
A.3.2 PROOF OF COROLLARY 5.2
First, we need to introduce the following lemma.
Lemma A.14 (Marchenko- Pastur Law). Suppose a matrix E BRXP, where the entries Xij are in- dependent and identically distributed with mean 0 and variance 0². As n and p tend infinity, with the ratio n/p converging to constant X, the empirical spectral distribution (i.e., the distribution of eigenvalues) of the matrix 1XX" converges to a limit given by the Marchenko Pastur distribution. This distribution has a density function given by:
f(x) = 2T x V(b x) - a) a
where
= o b= oz VX)
The difference between GaRare and GaLore is the selection of projection matrix. GaRare uses random matrix R instead of Ú. Thus, Eq. (4) becomes
(D Am ge (In @ R)")
Amin (Dga)Am Am ((L, 8 R)²)
Similar to the proof of Theorem 4.3 Amin (D (Dga) 2 μ. Then we need to determine the singular value of In @ R.
For R E Rmxr, can apply Lemma A.14 by replacing and p with and o² with 1/m, the cigenvalues of LRA converges to f(x)
((b x) a) for x b, with
1 [1 vAJa b 1 VA)+
m
considering large language models, the actual distribution is similar to the given one. Therefore, Am (R)) >
Because
{1 vx)² 2 with high probability. Note that < then ra ss 1. Then we have Xm ( (R)= 2 with high probability.
Remember that I, 2 R is matrix consisting of copies of the matrix R arranged along the diagonal, with all other positions filled with zeros, we have Am (In @ R) 2 1 with high probability. Then with high probability.
Am (gg Zz.
The remaining proofs are the same the proof of Theorem 4.3
A.3.3 PROOF OF COROLLARY 5.3
The proof of Theoem 4.9 only uses the fact that the solution of GaL.re is located in low-rank spaces.
Thus, use R instead of U does not change the conclusion.
21

---

Published as a conference paper at ICLR 2025
Table 5: Architectures of the MI.Ps in Section 6.1
Parameter
Value
Parameter
Value
input dim
32 32
input_dim
32 x 32 3 fodden_dim hidden_din
hidden_diml andden_dimt
hidden_din
hidden_dimi
rank
hidden_dim'
hidden_die .di33
hidden_din dim
output.im
10
output.dim
10
B DETAILS OF EXPERIMENTS
B.I MODEL ARCHITECTURE OF VERIFICATION EXPERIMENT
The architecture of the MLPs in Section 6. is in Table B.I On the left is the architecture of full- rank method, FLoRA, Gal orre and GaRare, while on the right is the architecture of LoRA. Because the weight matrices of LoRA is frozen, omit them and only include trainable parameters in the architecture. hidden_ding dim and rank changed across different tasks according to the experiment setting.
B.2 ARCHITECTURE AND HYPER-PARAMETER OF PRE-TRAINING EXPERIMENT
We introduce details of the LLaMA architecture and hyperparameters used for pre-training. Table shows the most hyperparameters of LLaMA models across model sizes. We follow the setting of ZZao al., 2024), which uses a max sequence length of 256 for all models, with a batch size of 131K tokens. For all experiments, we adopt learning rate warmup for the first 10% of the training steps, and use cosine annealing for the learning rate schedule, decaying to 10% of the initial learning rate.
Table 6: Model architecture comparison across different parameter sizes.
Params
Hidden
Intermediate
Heads
Layers
Steps
Data amount
60M
512
1376
8
10K
1.3
130M
768
2048
12
12
20K
2.6 B
350M
1024
2736
24
60K
7.8
B
2048
5461
24
32
100K
13.1 B
B
4096
11008
32
32
30K
3.9
For GaRare and FLoRA each size of models (from 60M 1B), we tune their favorite learning rate from a set of (0.04, 0.05, 0.03, 0.02, 0.01). and the best learning rate is chosen based on the validation perplexity. For the other methods, full-rank method, LoRA and GaLore, we use results reported by Zhao et al. 2024) directly. The hyperparameters of GaRare is shown in Table 7
Table 7: Hyperparameters of GaRare across different parameter sizes.
Params
Learning rate
LoRA scale
Subspace update frequency
60M
0.04
0.1
500
130M
0.03
0.1
500
350M
0.03
0.1
500
0.02
0.1
500
7 B
0.005
0.01
500
22

---

Published as a conference paper at ICLR 2025
B.3 DETAILS FINE- TUNING ON GLUE
We fine-tune the pre-trained RoBERTa-Base and RoBERTa-Large model on the GLUE benchmark using the model provided by the Hugging Face!. We tune the learning rate and batch size for GaRare. Table 88 and 2 show the hyperparameters used for fine-tuning RoBERTa-Base and RoBERTa-LLarge for GaRare, respectively.
Table 8: Hyperparameter settings for each dataset for RoBERTa- model.
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
STS-B
Batch Size
16
16
16
32
8
8
16
16
Epochs
30
30
30
30
30
30
30
Learning Rate
1E-05
2E-05
3E-05
3E-04
IE-05
3E-05
4E-05
3E-04
Rank Config.
r 4
scale
4
Max Seq. Len.
512
Table 9: Hyperparameter settings for each dataset for RoBERTa-Large model.
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
STS-B
Batch Size
16
8
32
16
8
16
16
Epochs
30
30
30
30
30
30
30
30
Learning Rate
1E-05
3E-05
1E-04
3E-05
1E-05
1E-05
1E-04
3E-05
Rank Config.
8
scale a
Max Seq. Len.
512
C PSEUDO-CODE OF GARARE
Algorithm 1: GaRare
Input:
M, rank E N+ scale factor a, subspace update frequency T, random seed x,
MaxIter >> O.
Initialize: First-order moment Mo O; Second-order moment Vo =
for k = to Maxlter do
T T then
x+=1
Compute loss function according to Eq. 2 with parameters θ and get gradients
G, E R= Generate random matrix R E mxx sampled from (O 1/m);
d, Rd 96i
Get parameters update Agi by optimization method (e.g., Adam, Adafactor);
AG. = RAG;
θ θ + AG;;
Output: W
23

---

Published as a conference paper at ICLR 2025
Loss curve
0.20
Full-rank GaRare
0.19
Loss/oss Mean
0.18
0.17
0.16
0.15
0.14
1250
1500
1750
Timestep
Figure 3: The training curve of EDM on full-rank training and GaRare.
D COMPUTATIONAL COST
Table 10: Compuational time of full-rank training, GaRare, GaLore, FLoRA and LoRA on various sizes of LLaMA models on C4 dataset.
60M (Igpu)
130M (2gpu)
350M (2gpu)
IB (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
T/ dmodel
128 / 256
256/
768
256 1024
512
2048
Training Tokens
1.IB
2.2B
6.4B
13.1B
E GARARE IN EDM
To evaluate the generalizability of GaRare, we applied it to optimize EDM (Karras et al. 2022 a widely used diffusion model. The model was trained on the CIFARI0-32X32 dataset, with the loss curve presented in Figure 3] While GaRare shows a relatively slower convergence rate, its final performance comparable that of full-rank training. Notably, GaRare reduces memory usage to 564M compared to 1024M for full-rank training.
SENSITIVITY ANALYSIS
We analyzed the sensitivity of GaRare to random seeds and subspace update frequency. First, we used three random seeds to run the experiments and reported the mean and standard deviation, as shown in Table G and G to demonstrate the robustness of GaRare with respect to random seeds. Second, we evaluated the sensitivity of GaRare to the subspace update frequency. Following the approach GaLore Zhao et al.) (2024), we conducted experiments on LLaMA 130M using the C4 dataset, with the results presented in Figure 4 The performance remains stable when the update frequency exceeds 100, indicating that this hyperparameter can be selected with a relatively large value without significantly impacting performance.
24

---

Published as a conference paper at ICLR 2025
G MEMORY USAGE ANALYSIS
In this section, we analyze the memory usage of LoRA, GaLore, and GaRare by discussing weights and optimizer states separately.
Weights
LoRA: Requires storing the low-rank matrices B E RRxr and E Rrxy, along with the full-rank weight matrix θ TRPx This results in total of pq + pr qr weights.
GaLore and GaRare: Both eliminate the need to store the low-rank matrices B and A, requiring only pa weights for the forward computation.
Optimizer States
LoRA: Requires storing gradient momentum and variance for B and A, adding 2pr + 2qr to total memory usage.
GaLore: Stores optimizer states in the low-rank spaces and for the projection matrix, re- sulting in total of pr + 2gr.
GaRare: Reduces memory usage for optimizer states to 2qr by regenerating the projection matrix each iteration, avoiding the need for additional storage.
This breakdown highlights how GaRare matches GaLore in weights but achieves superior memory efficiency in optimizer states.
Table 11: The mean and standard deviation of GaRare on various sizes of LLaMA models 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:10.09
25.49=0.20
19.24
15.69-0.114
dmodel
I28 / 256
256 768
256 1024
512 2048
Training Tokens
1.1B
2.2B
6.4B
13.1B
Table 12: The mean and standard deviation of GaRare with RoBERTa- and RoBERTa-Large model on GLUE.
RoBERTa-Bas Base
RoBERTa-Large
Full-Rank
GaRare
GaLore
FLoRA
LoRA
Full-Rank
GaRare
GaLore
FLoRA
LoRA
Memory
748M
252M
253M
252M
257M
2132M
718M
720M
718M
732M
CoLA
62.2
61.0=0.1
60.4
59.0
61.4
68.0
67. 67.6+0.4
68.3
65.5
68.2
STS-B
90.9
90.3+0.0
90.7
89.9
90.6
91.5
92.3=00.0
92.5
92.5
92.6
MRPC
91.3
91.4+0.2
92.3
88.5
91.1
90.9
91.7+0.11
91.7
89.3
90.9
RTE
79.2.0..3
79.4
76.5
07.
87.0
83.0
SST2
94.6
94.2:
94.0
93.8
92.9
96.4
96.0-0.3
96.1
96.0
96.2
MNLI
87.2
87.0 0.2
87.0
86.6
86.8
90.2
0.4
90.8
90.4
90.6
ONLI
92.3
92.1:10.2
92.2
91.9
92.2
94.7
94.5:10.1
95.7
94.0
94.9
QQP
90.9-0.3
91.1
90.9
92.2
91.9-1022
91.9
91.5
91.5
Avg
86.3
85.8
85.9
84.6
85.6
89.1
89.3
87.8
25

---

Published as a conference paper at ICLR 2025
Performance Subspace Update Frequency
32
Perplexity
30
26
200
400
600
800
1000
Subspace Update Frequency
Figure 4: Ablation study of GaLore on 130M models on subspace update frequency.
26


Reviews:
[{"review_id": "NRv9Y7gcCp", "reviewer": "Reviewer_Nysi", "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.", "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. \n\n2) 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nMarginal 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7CmhuDmdH1", "reviewer": "Reviewer_9dCt", "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.", "questions": "N/A.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ I believe the paper is a great application of the PL* condition to fine-tuning LLMS which is of significant interest. \n+ The theoretical analysis is rigorous and well-founded.\n+ 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EpqLYluAQp", "reviewer": "Reviewer_c5w7", "summary": "The paper has two main contributions:\nFirstly 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.\nThen, 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.\n\nOverall I find the paper well written, technically sound, and emprical results sufficiently supporting the claims.", "questions": "- The theoretical analysis focuses on train-from-scratch setting, is there any difference between training from scratch v.s. fine-tuning setting? \n\n- How much extra runtime overhead would the random matrix generation cost in practice?\n\n- 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.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- Learning rate swipe is conducted, making the emprical results more convincing!\n\n- 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.\n\n- 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.\n\n- 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.\n\n- (Minor) The proposed method uses random projection, which could introduce additional sensitivity to random seed in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9zDs6Irj6d", "reviewer": "Reviewer_eja2", "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.", "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?\n2. 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)?\n3. How do the computational costs of these methods compare in Table 1? Does GaRare introduce any additional slowdown?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n2. 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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dTtMF2Icco", "reviewer": "Reviewer_YR66", "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.", "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?\n\n2. 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\n2. 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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GPdErybAgh", "reviewer": "Reviewer_cY2C", "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.", "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?\n2. Could the theoretical framework be extended to transformer architectures?\n3. How do the projected minima relate to the full-rank optimization landscape?\n4. Why weren’t comparisons with higher-rank LoRA (r=8) and other recent low rank adaptation techniques included?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Important focus on understanding optimization landscapes of fine-tuning techniques\n2. Practical algorithm (GaRare) that improves efficiency\n3. Comprehensive experimental validation\n4. Clear mathematical formulation and complete proofs\n5. Good connection between theory and practice", "weaknesses": "1. Theoretical analysis limited to MLP architectures, making conclusions about LLMs less direct.\n2. Incomplete empirical comparisons:\n   - 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. \n   - 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?\n   - 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).\n3. Some claims about LoRA’s performance relative to full-rank fine-tuning are oversimplified.\n   - Contradicts findings from AdaLoRA paper with higher ranks.\n   - Doesn’t account for sparse adaptation methods’ success.\n4. Ambiguous definition of projected spurious local minima.\n   - Unclear relationship between projected minima and full-rank space:  how these minima relate back to the full-rank landscape?\n5. Limited novelty in theoretical results: some of the theoretical results appear to be direct extensions of established theorems.\n6. Memory analysis could be more detailed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)