Subspace Optimization for Large Language Models with Convergence Guarantees
Authors: Yutong He
Pengrui Li
Yipeng Hu
Chuyan Chen
Kun Yuan
Venue: ICML 2025 poster (2025)
Keywords: Large Language Models
Memory-Efficient Training
Gradient Projection
Primary area: optimization
TL;DR: This paper shows the non-convergence of GaLore and proposes variants with convergence guarantees.

Abstract: Subspace optimization algorithms, such as GaLore (Zhao et al., 2024), have gained attention for pre-training and fine-tuning large language models (LLMs) due to their memory efficiency. However, their convergence guarantees remain unclear, particularly in stochastic settings. In this paper, we reveal that GaLore does not always converge to the optimal solution and provide an explicit counterexample to support this finding. We further explore the conditions under which GaLore achieves convergence, showing that it does so when either (i) a sufficiently large mini-batch size is used or (ii) the gradient noise is isotropic. More significantly, we introduce **GoLore** (**G**radient rand**o**m **Lo**w-**r**ank proj**e**ction), a novel variant of GaLore that provably converges in typical stochastic settings, even with standard batch sizes. Our convergence analysis extends naturally to other subspace optimization algorithms. Finally, we empirically validate our theoretical results and thoroughly test the proposed mechanisms. Codes are available at https://github.com/pkumelon/Golore.

Subspace Optimization for Large Language Models with Convergence Guarantees
Yutong He H Pengrui Li
Yipeng Hu'
Chuyan Chen
Kun Yuan 145
Abstract
reduced computing resources, Most approaches (Vyas et al.
2024
Ramesh et al.)
2024]
Luo et al.)
2023
Liu et al.
Subspace optimization algorithms, such Ga-
2024
Bini et al.
2024
Hao et al.
2024
Zhao et al. 2024
Lore (Zhao et al., 2024),, have gained attention
Muhamed et al.
2024
Pan et al.
2024
Loeschoke et al.
for pre-training and fine-tuning large language models (LLMs) due to their memory efficiency. However, their convergence guarantees remain unclear, particularly in stochastic settings. In this paper, we reveal that GaLore does not al- ways converge to the optimal solution and pro- vide an explicit counterexample to support this finding. We further explore the conditions un- der which Gal.re achieves convergence, showing that does so when either (i) a sufficiently large mini-batch size is used or (ii) the gradient noise is isotropic. More significantly, we introduce GoLore (Gradient random Low-rank projection), novel variant of GaLore that provably converges in typical stochastic settings, even with standard batch sizes. Our convergence analysis extends naturally to other subspace optimization algo- rithms. Finally, we empirically validate our the- oretical results and thoroughly test the proposed mechanisms. Codes are available https:
2024 Hayou et al.
2024
Lialin et al.
2023
Han et al. 2024
concentrate on reducing the memory of optimizer states, which are critical components of overall training memory. For instance, Adam (Kingma 2014) and AdamW (Loshchiloy 2017) maintain first and second-orde momentum terms for gradients as optimizer states, leading to significant memory overhead for large models.
Song al. 2023
Among the most popular memory-efficient fine-tuning algo- rithms is LoRA (Hu al. 202T). which decreases the num- ber of trainable parameters by employing low-rank model adapters. However, the low-rank constraint on weight up- dates can result in substantial performance degradation for tasks that require full-rank updates, particularly in the pre- training of LLMs. To address this issue, several LoRA variants have been proposed, including ReLoRA (Lialin) ct al. 2023) and SLTrain (Han et al. 2024). Recently, Ga- Lore Zhao et al., 2024) has emerged as an effective solu- tion, significantly reducing optimizer states by projecting full-parameter gradients into periodically recomputed sub- spaces. By retaining optimizer states in low-rank subspaces, GaLore can reduce memory usage by over 60%, enabling the pre-training with 24GB of memory. In contrast, the vanilla 8-bit Adam without low-rank projection requires over 40GB of memory.
7B model on an NVIDIA RTX 4090
1. Introduction
Large Language Models (LLMs) have demonstrated impres- sive performance across a variety of tasks, including lan- guage processing, planning, and coding. However, LLMs re- quire substantial computational resources and memory due their large model size and the extensive amounts of train- ing data. Consequently, recent advancements in stochastic optimization have focused on developing memory- efficient strategies to pre-train or fine-tune L.LMs with significantly
1.1. Fundamental open questions and main results
While GaLore's memory efficiency has been well estab- lished, its convergence guarantees remain unclear. This raises the following fundamental open question:
Q1. Can GaLore converge stationary solutions, under standard and mild assumptions?
'Peking University ZZhongguancun Academy BBeihang Univer- sity" AI for Science Institute, Beijing, China National Engineering Laboratory for Big Data Analytics and Applications. Correspon- dence to: Kun Yuan <kunyuan @ eku.edd.en>.
By stationary solutions, we refer to first-order stationary points x E R such that Vf(=) 0 for ʃ Be - R. By standard and mild assumptions, we refer to common conditions in non-convex smooth optimization, including lower boundedness, L-smoothness and unbiased stochastic gradients with bounded variances, as in Assumptions
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Contrary to expectations, our investigation reveals that Ga- Lore is NOT theoretically guaranteed converge precisely with standard and mild assumptions. The intuition behind this finding is straightforward: GaLore projects the stochas- tic gradient matrix onto a low-rank subspace spanned by the top r singular vectors obtained via Singular Value Decom- position (SVD), effectively capturing the dominant com- ponents of the stochastic gradient matrix. However, the stochastic gradient comprises two components: the true gra- dient and gradient noise. When the true gradient dominates, the $ SVDDiidentifie subspace primarily captures the gradi- ent component. In contrast, as the algorithm approaches a local minimum so that the true gradient diminishes while noise persists, the greedy and biased SVD-derived subspace captures only the noise component, ultimately leading to non-convergence. To validate this intuition, we construct counter-example demonstrating that GaLore fails to con- verge to stationary solutions, see the illustration in Fig. [ This leads us to a subsequent open question:
It is evident that GaLore's SVD-based projections cannot extract meaningful information from noise-dominant ma- trices. To address this issue, this paper proposes modify- ing the SVD projection to Gradient Random Low-Rank projection, resulting in the GoLore algorithm. This ran- dom projection can effectively capture gradient information even when gradient noise predominates, allowing for conver- gence in the stochastic and non-convex setting with normal batch sizes. We establish that GoLore converges at rate of O(1/VT) under standard assumptions.
In our empirical experiments, we implement GaLore during the primary phases of pre-training or fine-tuning LLMs due to its efficacy in capturing the gradient component using SVDD-basd projection. In contrast, we employ Gol.ore in the final phase, leveraging its ability to extract the gradient component from noise-dominant stochastic gradients using random projection. This approach enhances performance compared to employing GaLore throughout all stages.
While our analysis primarily focuses on GaLore, it also has significant connections to other memory-efficient algo- rithms. We demonstrate that a ReLoRA- implementa- tion is equivalent to GaLore, which is more computational efficient with little additional memory overhead. Further- more, our theoretical results can be easily adapted to sparse subspace descent algorithms with minimal effort.
Q2. Under what additional assumptions can Gre converge to stationary solutions?
Based on the preceding discussion, we conclude that the SVD-identified subspace aligns well with the descent di- rection when the true gradient component dominates the gradient noise. This observation naturally leads to several additional assumptions under which GaLore can converge:
Contributions. In summary, our contributions include:
We find that GaLore is not theoretically guaranteed to converge to stationary solutions under Assumptions [ The key insight is that GaLore's SVD projection is biased and greedy; it may completely lose the true gra- dient information when the gradient noise is anisotropic and dominates the true gradient. We validate the non- convergence of GaLore by providing an explicit coun- terexample. This addresses Question QI.
Noise-Free Assumption We theoretically establish that GaLore converges rate of O(1/T) in the deter- ministic and non-convex setting.
3
Large-Batch Assumption. We theoretically demon- strate that GaLore converges at a rate of O(I/VT) in the stochastic and non-convex setting, provided that the batch size is extremely large and increases with the number of iterations e.g., batch size of ((VT).
Inspired by the aforementioned insight, we propose different additional assumptions under which Gre can provably converge to stationary solutions. Under the free assumption, we establish that GaLore converges rate of O(1/T). Under the large-batch assumption or isotropic noise assumptions, we demon- strate that GaLore converges at rate of O(IVVT). This addresses Question Q2.
We further investigate GaLore's convergence under the Isotropie-Noise Assumption, wherein the noise is assumed to be evenly distributed across all directions, mitigating the bias introduced by the top-K K selection.
However, none of the aforementioned assumptions apply to the practical pre- treiiraining and fine-tuning of LLMs, where
When possibly anisotropic gradient noise persists and the batch size maintains constant, we modify GaLore's SVD projection to a random projection, resulting in GoLore that provably converges to stationary solutions at a rate of O(1/VT). This addresses Question Q3.
gradient noise is not assumed isotropic (Zhu et al. 2018
HaoChen et al. 202T Mori et al. 2022, Wu et al. 2022
Wang& & Wu) and fixed batch sizes are commonly employed. This observation raises fundamental open question:
Q3. Under what modifications can GaLore provably converge in LLM settings, where possibly anisotropic gradient noise presents and the batch size is constant?
We present an equivalent yet more computationally ef- ficient implementation of GaLore/GoLorr and extend our analysis to sparse subspace descent algorithms. We
2

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithms using AdamW
Algorithms using MSGD
25
Goloor@500%
GoLore@75%
L.B. GaLore
20-
L.B. Galore
GaLore
GaLore
f(x)-fmin
15
Full Params.
f(x ((x)-fmin
1.5
Full Params.
5
1000
750 1250 1750 2000 Iterations
Iterations
Figure 1. Loss curves of algorithms using AdamW (left) and Momentum SGD (right) on problem where L.B. GaLore stands for large-batch Galorre, GoLore @ororrrrr 3% applics Gal for the beginning (100 =3)% iterations and GoL.ore for the last 3% iterations.
conduct experiments across various tasks to validate our theoretical findings. Alternately using GaLore and GoLore in different phases achieves enhanced empirical performance in LLMs pre-training and fine-tuning.
GaLore by incorporating error-feedback; Fira (Chen et al., 2024a) and APOLLO (Zhu et al. (024) adapt learning rates using optimizer states in the subspace.
Convergence for lossy algorithms. Many optimization algorithms utilize lossy compression training dynamics, such as gradients, particularly in the realm of distributed op- timization with communication compression. Researchers have established convergence properties for these algorithms based on either unbiased (Li et al.
1.2. Related work
Memorr-efficient training. In LLM training, the primary memory consumption arises not only from the model param- eters but also from activation values and optimizer states. Jiang et al.] (2022) and Yu et al. (2024) have proposed meth- ods to compress activation values into sparse vectors to alleviate memory usage. Other approaches primarily focus on reducing optimizer states, A notable work, LoRA (Hu ett al. 2021) reparameterizes the weight matrix W E _m*x as W Wo BA, where Wo E Rmxx remains frozen as the pre-trained weights, and B Rmxr and A R learnalle low-rank adapters. Variants of LoRA, such as those proposed by Liu et al. (2024) and HHyou et al. (2024), aim to enhance training performance. However, constrained to low-rank updates, LoRA and its variants are primarily effective for fine-tuning tasks and struggle with pre-training tasks that require high-rank updates. To address this limitation, ReLoRA (Lialin et al. 2023) en- ables high-rank updates by accumulating multiple LoRA updates, while LISA (Pan et al. 2024) learns full-parameter updates on dynamically selected trainable layers. GaLore (Zhao et al. 2024) and FLORA (Hao et al. (024) achieve high-rank updates by accumulating low-rank updates in pe- riodically recomputed subspaces, and SLTrain (Han et al.] 2024) employs additional sparse adapters for high-rank up- dates. SIFT (Song et al., (2023) also utilizes sparse updates. Although these algorithms have demonstrated comparable empirical performance to full-parameter training methods, theoretical guarantees regarding their convergence have not been established. Recently, [iing et al.] (2024) proposes an online subspace decent algorithm with continuous time con- vergence results; IDAdam (Robert al. 2024) improves
2020
Li Richtárik
2021 Condat et al. 2024 Huang & Pu
2023
He al.
2024a Mishchenko et al.
2019 Gorbunov et al.
2021 AP
istarh et al.
2017 He et al.
2023
contractive RRihhtarik
ct al.
2021
Xie et al.) 2020 Fatkhullin et al.
2024 He
et al.
2023 compressibility. Kozak et al. (2019) provides
a convergence analysis for subspace compression under Polyak-Loojsiewiiz or convex conditions, where the sub- space compression adheres contractive compressibility at each iteration. Despite these extensive findings, analyzing the convergence properties of subspace descent algorithms like GaLore remains challenging, as illustrated in Sec. 1.3
1.3. Challenges in theoretical analysis
Neither unbiased nor contractive compression. Gradient projection onto the subspace can be viewed as gradient com- pression. Traditional analyses of optimization algorithms with lossy compression typically rely on either unbiased compressibility, iee., the compressor C satisfies
B[C(=)) = x, B[I[(()) x x S w||=||
Vo e
for some w 2 0, or contractive compressibility, i.e.
B[I[((=:) x012] < (1 1>
Var E IRd
for some 8 E (0, 1]. However, GaLore's subspace com- pression is neither unbiased nor contractive due to the reuse of projection matrices. For example, consider a pre- computed projection matrix P R.xx. There exists a
3

---

Subspace Optimization for Large Language Models with Convergence Guarantees
full-parameter gradient G E R=xx such that G o and C(G) = P 0, violating both compressibilities
Specifically, GaLore performs SVD on G( = UEVT
and obtains rank-ra projection matrices P(( = [ rd] R x and Q ( Vi::: rel E R where [::: de- notes the selection of the matrix's first r columns. When my S Rtg Gal.ore projects Ge onto Pt, yielding a low- rank gradient representation (P(2) G E EReex Con- versely, when my > Th,, Galore projects G. onto Qz, re- sulting in Ge Q² R In either scenarios, the memory cost of optimizer states associated with these low- rank representations can be significantly reduced, leading to memory- efficient LLMs pre-training or fine-tuning:
Periodically projected optimizer states. When GaLore changes the subspace, the retained momentum terms must be adjusted to track the gradients in the new subspace. Since these momentum terms were initially aligned with the gra- dients in the original subspace, such adjustments inevitably introduce additional errors, especially when the two sub- spaces differ significantly. In the extreme case where the two subspaces are entirely orthogonal, the momentum from the previous subspace becomes largely irrelevant for opti- mization in the new one.
((()
(x()
+ p()) (0) x
((P()) D if S nei
x (((+))
8 Pi
+ Pi (0)
(G Q (Q()), if if > ne.
2. Preliminaries and assumptions
Typically, GaLore selects pe(-) as the Adam gradient op- erator, illustrated in Alg. [ However, GaLore can also choose (+(-) to be gradient operators in either vanilla SGD or MSGD. Since SVD is computationally expensive, Ga- Lore updates P(u) or Q( periodically. In other words, Ga- Lore computes p!()) or Q when iteration step ( = 0 (mod T) where T > 0 is the period, otherwise p(()) = P ((t-1)
Full-parameter training. Neural network training can be formulated as the following optimization problem:
min fxx) == EE 20
collects all trainable parameters, Nr. is the number of layers, X2 E gm denotes the weight matrix in the 8-th layer. F(x; E) computes the loss with respective to data point &. D denotes the training data distribution. In full- full-parameter training, we directly apply the optimizer to the full-parameter x::
Here, x = TT) vec((N,))
and Qfth = = " remain unchanged. Both the gradient subspace projection and periodic switches between differ- ent low-rank subspaces pose significant challenges to the convergence analysis for GaLore-like algorithms.
G V. (eF( (1); (())
Stiefel manifold. Stiefel manifold is the set of low-rank projection matrices to use in subspace optimization. An m Stiefel manifold (r S <m) is defined as
x (+D = x + P (G (- NZ:
where Ve computes the gradient with respective to the f-th weight matrix Xz, superscript (4) denotes the variable in the 1-th iteration, and P3 is an entry-wise stateful gradi- ent operator, such as Adam or Momentum SGD (MSGD).
Stm,r = {PP E R | P- 1,).
In GaLore, we have p!!) E Stmer and Q! SSnngre
Basic assumptions. We introduce the basic assumptions used throughout our theoretical analysis. Each of these assumptions is standard for stochastic optimization.
Specifically, using MSGD leads to the following PE (.):
(t)
M = (1- 1,) + G/
Assumption 1 (Lower boundedness). The objective func- tion f : Rdd - R satisfies inf wn f(x) > -00, where d d= ENr, t=1 mgn; represents the total number of parameters. Assumption 2 (L-smoothnesss) Function f Fd
Pi (1) (G -n (0)
N2
where 17 is the learning rate, 31 E (0, 1] is the momentum co- efficient, and ( is the momentum state. In pall-parameter LLMs pre-training/fie-tuuii
Rdd + R
satisfies [[V](() - v (1())l2 S L||æ - y l2. Va, y E Rd. Assumption 3 (Stochastic gradient). It holds that
the memory requirements for storing momentum in MSGD and the additional variance state in Adam are highly demanding. According to Zhha let al. (2024), pre-training LLaMA 7B with a single batch size requires 58 GB of memory, with 42 GB allocated to Adam optimizer states and weight gradients.
Ee-DIV {)] Ve.( and
E (eF=;() - (=))) oo Vx E IR.
where (F, represents the gradient oracle, or i scalar. Summing all weight matrices we obtain
GaLore algorithm. To address the memory challenge, (Zhao et 2024) proposes novel Gradient Low-Rank Pro- jection (GaLore) approach that allows much more memory- efficient full- -arammeerr learning. The key idea is to project each stochastic gradient G$ E Xne onto a low-rank sub- space, yielding dimensioiln gradient approximation.
B (VF(;; {) = ffx)), and
E E V (x: - f fz)) so² Væ E R2,
where o v EE= of.
N₂
4

---

Subspace Optimization for Large Language Models with Convergence Guarantees
grad
of GaLore when solving problem ① It is observed that Gal.ore fails to converge the optimal solution, regardless of whether the AdamW or MSGD optimizer is used.
noise
Gradient dominates during the initial stages
Non-convergence of GaLore. The following theorem de- picts GaLore's non-convergence based on the above insight.
Theorem (Non-convergence of GaLore): There exists an
objective function f: I2 R satisfying Assumptionn | stochastic gradient oracle (F, D) satisfying Assumption initial point x² E Rd, a constant En > 0 such that for any rank T < min,me, ne), subspace changing frequency r, any optimizer p that inputs a subspace gradient of shape re x ng and outputs a subspace update direction of the same shape and any > 0, holds that
noise
Noise dominates when close to minimum
grad
Figure 2. Gradient noise dominates when close local minimum.
3. Non-convergence of GaLore
In this section, we demonstrate why GaLore cannot guar- antee exact convergence under Assumptions I S illustrate the insight, then present the formal conclusion.
We first
|V N co-
Insight behind non-convergence, As reviewed in Sec. GaLore performs SVD on stochastic gradient G UEV
2
4. Conditions for GaLore to converge
and obtains rank-r projection matrices P = U(t, : r] E 1mxr. GaLore projects G onto P. yielding low-rank gradient representation P G E Rrx*, In other words, Ga- Lore projects the stochastic gradient matrix onto a low-rank subspace spanned by the top r' singular vectors, capturing the dominant components of the stochastic gradient matrix. However, the stochastic gradient comprises two compo- nents: the true gradient and gradient noise, as shown in Fig. 3 When the true gradient significantly exceeds the gra- dient noise, typically at the start of training (see Fig. 2). the low-rank subspace obtained via SVD effectively preserves the true gradient information. As training progresses and the true gradient diminishes zero, especially near local minimum (see Fig. 2). the subspace may become increas- ingly influenced by gradient noise. When gradient noise is not isotropic, the doiinnddmd subspace captured by SVD may become orthogonal to the true gradient subspace due to its greedy nature, leading to non-convergence.
GaLore provably converges in the noise-free setting. Ac- cording to Sec. 2 Gore Lore fails to converge when gradient noise dominates the true gradient in magnitudes. This mo- tivates us to examine the deterministic scenario where true gradient f can be accessed without any gradient noise. GaLore with noise-free gradients presented in Alg. [or Alg. 3 in Appendix [B.3). where the true gradient oracle is highlighted with label (det.). Without gradient noise,
the projection matrix p(") obtained by SVD can effectively capture the true gradient even when approaching a local minimum. For simplicity, analyze GaLore with MSGD and the following momentum updating mechanism:
M, 11) P(
10 P MB (11)) Q +B1 Q m m
P(u
OO G mm
(1-3)M Q
19
If the subspace does not change at iteration f, it holds that (P!")) T p((-1) = (Q( Q = I,, and reduces to regular momentum updates. If the subspace changes at iteration t, we inherit (1 by first projecting back to the original space and then to the new subspace. We use momen- tum projection (MP) to refer to mechanism (2). When MP is used in the algorithm, we label the corresponding with (w/ MP) in Alg. otherwise (w/o MP) The following theorem provides convergence guarantees for GaLore using deterministic gradients and MSGD with MP.
Counter-Example. We consider the following quadratic problem with gradient noise:
f(x) J AXII + (B,
VF(X: = v + CoC,
(D
D
9)
where A (In-r 0) ()) B
e
Raxe with D E ((n--)x((--)) generated randomly, C=
(0
Theorem 5 (Convergence rate of deterministic GaLore): D if the number of iterations T Z
( I, E Raxn, & is a random variable uniformly sam- pled from {1, 11 per iteration, and is used to control the gradient noise. It is straightforward to verify that prob- lem (I) satisfies Assumptions
Under Assumptions 64/(35) and we choose hyperparameters 3,, T, according to Appendix[B..x GaLore using deterministic gradient and momentum gradient descent with MP converges as
33 Moreover, as X ap- proaches the global minimum of f(X,, the true gradient fX()) + 0. while the gradient noise persists with a vari- ance on the order of a² Fig.] iillustrates the performance
T (
10
)1
o
LA
T
85/2T
r= 0
5

---

Subspace Optimization for Large Language Models with Convergence Guarantees
G
P P ( ( (
U
SVD
Projection p
Large gradient
True gradient
Good gradient estimate
Gradient noise
P
gradiant
SVD
Projection on P?
Bad gradient estimate
Small gradient
Gradiont
Figure An illustration of the insight on why GaLore fails converge small-gradient scenarios. We use color green for true gradient and red for gradient noise.
where A = f(xx()) in fxx and 5 == ming min me).
large-batch MSGD with MP converges as
Remark Theorem demonstrates that GaLore converges at a rate of (L/ in the deterministic scenario, which is on the same order deterministic full-space gradient descent. More details presented in Theorem TO in Appendix [3.3] However, in deep learning tasks with exceptionally large training datasets, computing the true gradient becomes im- practical due to significant computational and memory costs. Therefore, We will next focus on the stochastic setting.
f (1) -
LA 85/2T
LAo2
8
where = f(x f(x) and ming min mm
Remark 3. A more detailed result is presented in Theorem 12 Appendix B.4 The large batch size B = @(vT) grows with iteration T, leading increased memory over- head, making it less practical than small batch sizes. With gradient accumulation, additional variable is needed to track the gradient, complicating compatibility with per-layer weight updates, Otherwise, larger batch sizes raise the mem- ory for activation values. Therefore, exploring algorithms that converge with constant batch sizes becomes essential.
When ry + min {m,, n. 5 + 1, and the con- vergence rate in (erorrem]Jreducee to that of full- aull-pareettr gradient descent. This implies the sharpness of our analysis.
Remark
GaLore provably converges with large-batch stochas- tic gradients. Inspired by the insight presented in Sec. 2 GaLore converges in cases where the true gradient dom- inates the gradient noise. This convergence can en- sured by reducing the gradient noise through an increased batch size, particularly as the algorithm approaches a lo- cal minimum. Specifically, we replace the stochastic gra- dient ((t) (x)() ((1) with large-batch gradient a( B L ( e(L.))) which reduces the vari- ance of gradient noise by B times. The GaLore algorithm with large-batch stochastic gradients is presented in Alg. (or Alg. inn Appendix B.4), where the large-batch stochas- tie gradient oracle is highlighted with the label (l.b.).. It is worth noting that the non-convergence of GaLore primarily stems from the erroneous subspace dominated by gradient noise. Therefore, we compute large-batch gradient only for the SVD step while maintaining smaller batch size for other computations, see Alg. [ As the batch size B increases with iteration T, GaLore provably converge to sta- tionary solutions, as established in the following theorem:
GaLore provably converges under isotropic noise as- sumptions. In Appendix C demonstrate that under specific isotropic noise assumptions, the SVD-induced sub- space reliably preserves the true gradient information. Con- sequently. GaLore, even with constant batch sizes, achieves a guaranteed convergence rate of (1/vVT). However, isotropic gradient noise rarely considered in the conver- gence analysis of machine learning or deep learning algo- rithms (Zhu al. 2018 HaoChen al. 2021 Mori et al.)
B
2022
Wu et al. 2022 Wang & Wu Koloskova ct al. 2020
Empirical validation. Fig. illlssrates the convergence of large-batch Gal (blue curve) in solving problem (T). demonstrates that large-batch GaLore effectively corrects the bias present in small-batch stochastic GaLore (green curve), achieving convergence to stationary solutions.
5. GoLore: random low-rank projection
Theorem (Convergence rate of larch-batch GaLore): Un- der Assumptions [3 if the number of iterations 2 2+ 256/(35) (256g )- (9/8 LA) and choose hyperparam- 7, B, $1,9 n according Appendix B.4 Gal.or using
GoLore algorithm. The main issue with SVD-based pro- jection in GaLore that aims to capture the dominant component in the stochastic gradient matrix. Consequently, when gradient noise overshadows the true gradient as the
6

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm 1
GaLoree /
GoLore
algorithm framework large-batch gradients
algorithm approaches local minimum, the SVD-based
projection fails to identify valuable gradient information.
using stochastic
/ deterministic/
with
without
momentum projection
To address this, we propose replacing the SVD-based projec- tion with a random projection, which captures components of the stochastic gradient matrix randomly without any pref- erence, This results in the GoLore algorithm presented in the GaLore method highlighted with the label (GaLore) samples the
Input:
Initial point (0)), data distribution D, learning rate Nr, 7, subspace changing frequency т, rank (re) opti- mizer hyperparameters 31, 82. e, large batch size B.
Alg. ( Alg. in Appendix B.5). In Alg.
[
Output: (ax(1)
Initialize optimizer state (M{-)) and (v(-")> )
projection matrix p(t) via SVD. In contrast, the GoLore method highlighted with the label (GoLore) samples P(() from (S. ). a uniform distribution on the me Tt Stiefel manifold. The following proposition provides a prac- tical strategy sample from distribution (Stt,..))
to zero;
for t = 0, 1, 1,, T do for = 1,2, ,Nr, do
if 0 (mod r) then
G ( (sto.)
Proposition 7 (Chikuse (2012), Theorem 2.2.1). A random matrix X uniformly distributed on Stm.r is expressed as X= = - Z) where the elements of Z E RRxr are independent and identically distributed as normal (0, 1).
G Ve)(=(()); (det.)
G + 1 Σ ((la)))(((.)) (l.b))
U. U,Σ, V (V p(() U(::re)
Convergence guarantee. Unlike SVD used in GaLore, the random sampling strategy in GoLore prevents the subspace from being dominated by gradient noise. The theorem below provides convergence guarantees for GoLore when using amall-batch stochastic gradients and MSGD with MP.
0 Vl: rel: (GaLore)
Sample p(t)) ~ U(Stmerre)
2000 ~ (Stmeere)) (Golore)
Theorem 8 (Convergence rate of GoLore): Under Assump- tions 3 for any T 2 2 + 128/ (35) + (128a) / /9//AA) if we choose hyperparameters 31, T, 77 according to Ap- pendix [B.5] Golore using small-bated stochastic gradients
else
G + V(F()()):(()); (sto.)
G Vel(=!!)); (det.)
and MSGD with MP converges as
( (t (l.b.)
p(")
+ !t-- (t)
(t-1);
B f (9)) =0
LA 85/2T
+
LAØ2 87/2T
end if
(((())
) G
(t)
if my S nz
R
Q!
(1) if m ne
where A = -(xx(())-in)) f(x) and ò = ming min mes
Compute ( via (2) (w/ MP)
Remark 4. Theorem 8 demonstrates that GoLore converges at a rate of O(1 ((1/VT), which is consistent with the con- vergence rate of fall-paaameter pre-training using standard MSGD. A more detailed result presented in Theorem [4] in Appendix B.5] where established convergence for more general hyperparameter choices. Unlike determinis- tic GaLore and low-rank GaLore discussed in Sec. 2 the newly proposed GoLore algorithm converges in the non- convex stochastic setting with constant batch sizes. Fur- thermore, GoLore converges without assuming isotropic gradient noise, and it remains effective whether the gradi- ent noise is anisotropic or not, making significantly more suitable for LLM pre-training and fine-tuning.
-D < (1 - 31) M (1-1) + 31 3,R( R( (w/o MP)
Vi() & -1 V2 (-1) + B2 R @ R
if using Adam then
Md < -M,") /(1 -11 ;:);;;
v(()) t v. 111-((111) (1- 32)");
NO + M///C /(V V + +c);
else if using MSGD then
N: M,.)
end if
X (1+1)
x (1) - P (1) NOO,
if ms S nz:
x - N (1))..
)T,
if mm > ng
Remark 5. Notably, this paper presents the first discrete- time convergence analysis for GaLore-like algorithms under standard assumptions. Among the few GaLore-like like studies providing convergence guarantees, Liang et al. (2024) es- tablishes continuous- time convergence, while Robert et al.
end for end for return {x(1) To=
7

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithms using AdamW
Algorithms using MSGD
80
2.50
Gol.or@550%
GoLore@20%
75
Gal.ore
2.25
GaLore
70
2.00
Full Params.
65
1.75
60
43.5
0.8
42.3
20.0 25.0 30.0
1,00
0.7
0.5
4,0
0.75
0.50
2.0
(xerationsxx10000
Iterationsxx1000)
Figure 4. Pre-training curves of various approaches using AdamW with BF16 precision.
Figure 5. Fine-tuning curves of various approaches using MSGD with BF16 precision.
Table 1. Fine-tuning results on GLUE benchmark using pre-trained RoBERTa-Basc.
Algorithm
CoLA
STS-B
MRPC
RTE
SST2
MNLI
QNLI
QQP
Avg
Full Params.
62.07
90.18
92.25
78.34
94.38
87.59
92.46
91.90
86.15
GaLore
61.32
90.24
92.55
77.62
94.61
86.92
92.06
90.84
85.77
FLORA
57.71
89.59
91.96
76.17
94.50
85.42
91.93
90.49
84.72
GoLore 20%
61.66
90.55
92.93
78.34
94.61
87.02
92.20
90.91
86.03
Empirical validation. Fig. [shows the convergence of the hybrid algorithm (red curve) applied to problem ([. which employs Gal Lore in the early training phase and switches to GoLore in the later stage. It is observed that the hybrid algorithm successfully converges to stationary solutions.
Table 2. Results for fine-tunin pre-trained OPT-13B models BoolQ, OOM stands for "out of memory".
Algorithm
Memory
Accuracy
Full Params.
OOM
Galore
77.68 GB
79.79
6. Experiments
GoLore 30%
77.68 GB
81.96
We evaluate GaLore and GoLore on several different tasks, including a counter-exampee problem ([). pre- pre-training and fine-tuning LLMs with real benchmarks. Throughout our ex- periments, GoLore@ @x% uses GaLore in the first (100-x)) % iterations and GoLore the last x% iterations, L.B. GaLore denotes large-batch GaLore, and Full Params. denotes full- parameter training. Further results and detailed experimen- tal specifications including the hyperparameter choices and computing resources are deferred to Appendix D andd F
2024) demonstrates convergence using more complex error feedback technique, relying on contractive assump- tion on the projection matrix that becomes stronger as the subspace recomputing period 7 > 1. In contrast, Gol.ore guarantees convergence by replacing the SVD projection with random projection, without significantly altering the algorithmic structure or introducing restrictive assumptions.
Practical application of GoL.ree in LLMs. While Gole have theoretical convergence guarantees, directly applying GoLore in LLM tasks may not be ideal. The advantage of using randomly sampled projection matrices becomes evident the later stages of training, where stochastic gradi- ents are primarily dominated by gradient noise. However, in the early stages, projection matrices derived from GaLorees 's SVD retain more gradient information, leading to more ef- fective subspaces, see Fig. [ hybrid approach: initially using GaLore to converge toward the neighborhood of the solution, then switching to GoLore for refinement and achieving more accurate results.
GaLore's non-convergence. In order to validate the non- convergence of Gal Lore and the convergence properties of GoLore and large- batch GaLore, we compare them with full-parameter training on the constructed quadratic prob- lem defined in (I. Fig. shows that, regardless of whether AdamW or MSGD is employed as the subspace optimizer, GaLore does not converge to the desired solution. In con- trast, both Golore and large-batch Gal Lore, along with full- parameter training, achieve exact convergence, thereby vali- dating our theoretical results.
Therefore, we recommend
Pre-training. To validate GoLore in LLM pre-training tasks, we pre-trained LLaMA-60N. on the C4 (Raffel et al.)
8

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Table 3. Memory and computation comparison between Gal original implementation and our Ro--AR-l version, both utilizing MSGD with batch size b. We assume the weight W E =m=x satisties m I n.
GaLore Implementation
Memory
Computation
(Zhao et al. 2024)
mn + rm + en + bm
6bmm + 4rmn + 2mn + 3rm
Our BeLoRA-like version
mn rm 2rn + bm + br
4bmn + 4brm + 6brn + 5rn
2020) dataset for 30,000 iterations using various algorithms, including Gal.ore, Golorre and full-parameter training. All implementations utilized the AdamW optimizer in BF16 format. As illustrated in Fig. + the perplexity dramatically decreases when shifting from Galorre GoLore, demon- strating the effectiveness of our approach.
is independently sampled from TromN((0))) (V 1/r), 1/r),/r), and thus P may not belongs to Stm,r-
Connection with SIFT. SIFT fine-tunes LLMs with sparsi- fied gradients, which can also be viewed as subspace descent. While Gal.ore projects gradient G' to PT G via projection matrix P. SIFT projects gradient G' to S @ G via a sparse mask matrix S. Our theoretical analysis can be directly transferred to sparse subspace descent with little effort, im- plying similar results as in low-rank subspace descent, see Appendix D
Fine-tuning, To validate the efficiency of GoLore in LLM
fine-tuning tasks, we fine-tuned pre-trained RoBERTa mod- els (Liu 2019) on the GLUE benchmark (Wang 2018). LLaMA2-7B models (Tuvron et al., 2023) on the Wino-
Grande dataset (Sakaguchi et al. 2021). and OPT-13B mod-
Connection with zero-th order methods. Zero-th order methods (Malladi et al.) 2023 Zhang al.] 2023 Chen et al. 2024b) are another line of works on memory-eficient training. While these algorithms randomly select a direction to estimate the directional derivatives by finite difference, GoLore computes subspace gradients via back propagation. The directions used in zero-th order methods change ev- ery iteration, while GoLore applies a more lazily strategy changing its subspace every iterations.
els (Zhang et al. (2022) on the BoolQ dataset (Clark al.] 2019) Fig. displays the loss curves for fine-tuning WinoGrande with rank 1024, while Table [ present the task scores for GaLore/GoLore with rank 4. GoLore consistently outperforms GaLore in the above experiments.
present
7. Connections with other algorithms
Connection with ReLoRA. Optimization algorithms like Lor that optimizes in periodically recomputed subspaces can be implemented in an equivalent yet poten- tially more computational efficient, ReLoRA-like way. Con- sider a linear layer y W with W E Rmx", where m n., GaLore first computes the full- parameerrr gradient WwC = (Vy T via back propagation and update W in the subspace as W + W + P (VwC)), where Pe E mm is low-rank projection matrix. If we use LoRA adaptation W- = Wo + BA with B E Rmxx and A E Rexn, we compute A's gradient VaC = (V=C)=* = B (V T, where
Connection with gradient sketching methods. Gradient sketching methods like Hanzely et al. (0118) and Wang et al. (2024) uses gradient sketches in algorithm iterates. These methods recover gradient estimates from projected gradi- ents and retains full-size gradients and optimizer states. In comparison, GoLore directly updates with projected gradi- ents and retains compressed gradients and optimizer states, which is more memory-
8. Conclusion and Limitations
Bx is the additional activation. If we fix B- P. update A t A + p(V AC) is equiva- lent to W +- W + Pp( PT (V w L)). The memory and computational costs of the two implementations are com- pared in T showing the potential of our ReLoRA-like implementation to reduce computation with little memory overhead. Detailed algorithm deseriptions and calculations are in Appendix A
This paper investigates subspace optimization approaches for LLM pre-training and fine-tuning. We demonstrate that GaLore fails converge to the desired solution under reg- ular assumptions, as the SVD-based projection often gen- erates potentially anisotropic noise-dominated subspaces when the true gradient is relatively small. However, we establish that GaLore can achieve exact convergence when using deterministic or latge-batch stochastic gradients. We further introduce Gol Grr- variant of Galore employing randomly sampled projection matrices-and establish its convergence rate even with small-batch stochastic gradients. A limitation of this paper is that our convergence analysis framework has not readily covered the use of the Adam optimizer and recent GaLore variants such as Fira.
Connection with FLORA. Aware of the equivalence of the two (GaLor//RcLoRA-iike) implementations, the main difference between GoLore and FLORA lies in the choice of projection matrices. Though both algorithms sample P E x randomly, GoLore uses a uniform distribu- tion on the Stiefel manifold (Stm.r)) while FLORA uses random Gaussian distribution where each element in P
9

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Acknowledgements
Gorbunov, E., Burlachenko, K. P., Li, Z.. and Richtárik, P. Marina: Faster non-convex distributed learning with compression. In International Conference Machine Learning, pp. 3788-377777 179888 PMLR, 2021.
The original submission is supported by the National Natu- ral Science Foundation China (No. 124B2017, 92370121, 12301392) and the National Key Research and Develop- ment Program of China (No. 2024YFA1012902 final revisions are additionally supported by Zhongguancun Academy Project (No. C20250205).
The
Han, A., Li, J., Huang. W., Hong, M., Takeda, A., Jawan- puria, P., and Mishra, B. Sltrain: a sparse plus low-rank approach for parameter and memory efficient pretraining. arXiv preprint arXiv:2406.0222 2024.
Impact Statement
Hanzely, F., Mishchenko, K., and Richtárik, P. Sega: Vari- ance reduction via gradient sketching. Advances Neu- ral Information Processing Systems, 31, 2018.
This paper studies the non-convergence and convergence properties of GaLore under different assumptions, whose goal is to gain better understanding of GaLore and design better memory-efficien optimization algorithms. Aiming to advance the field of Machine Learning, we do not feel any potential societal consequences of this work necessary to be discussed here.
Hao, Y., Cao. Y., and Mou, L. Flora: Low-rank adapters are secretly gradient compressors. arXiv preprint arXiv:2402.03223, 2024.
HaoChen, J. Z., Wei, C., Lee, J., and Ma, T. Shape mat- ters: Understanding the implicit bias of the noise covari- ance. In Conference on Learning Theory, pp. 2315-2357. PMLR, 2021.
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. Qsgd: coamuunication-fffciieee sgd via gradient quan- tization and encoding. Advances in neural information processing systems, 30, 2017.
Hayou, S., Ghosh, N., and Yu, B. Lora+: Efficient low rank adaptation of large models. arXiv preprint arXiv:2402. 12354, 2024.
Bini, M., Roth, K., Akata, Z., and Khoreva, A. Ether: Efficient finetuning of large-scale models with hyperplane reflections. arXiv preprint Stti::2005220277 2024.
He, Y., Huang, X., Chen, Y., Yin. W., and Yuan, K. Lower bounds and accelerated algorithms in distributed stochas- tie optimization with communication compression. arXiv preprint arXiv:2305.07612 2023.
Chen, X., Feng, K., Li, C., Lai, X., Yue, X., Yuan, Y., and Wang, G. Fira: Can we achieve full-rank train- ing of Ilms under low-rank constraint? arXiv preprint arXiv:2410.01623, 2024a.
He, Y., Hu, J., Huang, X., Lu, S., Wang, B., and Yuan, K. Distributed bilevel optimization with communication compression. In Forty-first International Conference on Machine Learning, 2024a.
Chen, Y., Zhang, Y., Cao, L., Yuan, K., and Wen, Z. Enhanc- ing zeroth-order fine-tuning for language models with low-rank structures. arXiv preprint 1r00022410.07698, 2024b.
He, Y., Huang, X., and Yuan, K. Unbiased compression saves communication in distributed optimization: when and how much? Advances in Neural Information Pro- cessing Systems, 36, 2024b.
Chikuse, Statistics on special manifolds, volume 174. Springer Science & Business Media, 2012.
Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang. S., Wang, L., and Chen, W. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2 (olv:2/00.06885, 2021.
Clark, C., Lee, K., Chang, M.-W., Kwiatkowski, T., Collins, M., and Toutanova, K. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint arXiv: 10044, 2019.
Huang, K. and Pu, S. Cedas: A compressed decentralized stochastic gradient method with improved convergence. arXiv preprint arXiv:2301.0580
2023.
Condat, L., Maranjyan, A., and Richtárik, P. Locodl: Communication distributed learning with lo- cal training and compression. arXiv preprint arXiv:2403.04348, 2024.
Jiang, 7.,, Chen, X., Huang. X., Du, X., Zhou, D., and Wang, Z. Back razor: Memory-efficient transfer learning by self-sparsified backpropagation. Advances in neural information processing systems, 35:29248-209 292611, 2022.
Fatkhullin, I., Tyurin, A., and Richtárik, P. Momentum provably improves error feedback! Advances in Neural Information Processing Systems, 36, 2024.
Kingma, D. Adam: method for stochastic optimization. arXi:: arXiv preprint arXiv: 1412. 628000 2014.
10

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning. pp. 5381-5393 PMLR, 2020.
Mori, T., Ziyin, L., Liu, K., and Ueda, M. Power-law escape rate of sgd. In International Conference Machine Learning, pp. 15959-15975. PMLR, 2022.
Muhamed, A., Li, O.. Woodruff, D., Diab, M., and Smith, V. Grass: Compute efficient low-memory Ilm train- ing with structured sparse gradients. arXiv preprint arXiv:2406. /7660, 2024.
Kozak, D., Becker, S., Doostan, A., and Tenorio, L. Stochas- tic subspace descent. arXiv preprint arXiv:190.001444 2019.
Pan, R., Liu, X., Diao, S., Pi, R., Zhang, J., Han, C., and Zhang, T. Lisa: Layerwise importance sampling for memory-efficient large language model fine-tuning, arXiv preprint arXiv:2403. 17919, 2024.
Li, 7. and Richtárik, P. Canita: Faster rates for distributed convex optimization with communication compression. Advances in Neural Information Processing Systems, 34: 13770-13781, 2021.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21 (140): 1-60) 2020.
Li, Z., Kovalev, D., Qian, X., and Richtárik, P. Accelera- tion for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002. 1364, 2020.
Lialin, V., Muckatira, S., Shivagunde, N., and Rumshisky, A. Relora: High-rank training through low-rank updates. In The Twelfth International Conference on Learning Representations, 2023.
Ramesh, A. V., Ganapathiraman, V., Laradji, I. H., and Schmidt, M. Blockllm: Memory-efficient adaptation of IIms by selecting and optimizing the right coordinate blocks. arXiv preprint arXiv:2406. 17296, 2024.
Richtárik, P., Sokolov, I., and Fatkhullin, I. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384-4396, 2021.
Liang, K., Liu, B., Chen, L., and Liu, Q. demory-efficient IIm training with online subspace descent. arXiv preprint arXiv:2408. 12857, 2024.
Liu, S.-Y., Wang, C.-Y., Yin, H., Molchanov, P., Wang, Y.-C. F. Cheng, K.-T., and Chen, M.-H. Dora: Weight-decompoosed low-rank adaptation. arXiv preprint arXiv:2402.09333, 2024.
Robert, T., Safaryan, M., Modoranu, I.-V., and Alistarh, D. Ldadam: Adaptive optimization from low-dimensional gradient statistics. arXiv preprint arXh::4410.16103, 2024.
Liu, Y. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
Sakaguchi, K., Bras, R. L., Bhagavatula, C., and Choi, Y. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
Loeschcke, S., Toftrup, M., Kastoryano, M. J., Belongie, S., and Snæbjarnarson, V. Loqt: Low rank adapters for quantized training. arXiv preprint arXiv:2405.16528 2024.
Song, W., Li, Z., Zhang, L., Zhao, H., and Du, B. Sparse is enough in fine- tuning pre-trained large language model. arXiv preprint arXiv:23 1875, 2023.
Loshchilov, I. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101 2017.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama Open foundation and fine- tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Luo, Y., Ren, X., Zheng, Z., Jiang, Z., Jiang, X., and You, Y. Came: manfidence-uuided adaptive memory efficient optimization. arXiv preprint arXiv:2307.02047, 2023.
Vyas, N., Morwani, D., and Kakade, S. M. Adamem: Memory efficient momentum for adafactor. In 2nd Work- shop on Advancing Neural Network Training: Computa- tional Efficiency, Scalability, and Resource Optimization (WANT@ ICML 2024), 2024.
Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, J. D., Chen, D., and Arora, S. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038- 53075, 2023.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. Distributed learning with compressed gradient differ- ences. arXiv preprint arXiv: 090999999999....9909990990 2019.
Wang, A. Glue: multi-task benchmark and analysis plat- form for natural language understanding. arXiv preprint arXiv: h 1004.80040000 004.07461, 2018

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Wang, M. and Wu, L. A theoretical analysis of noise ge- ometry in stochastic gradient descent. arXiv preprint arXiv:2310.00692.
Wang, Y., Ye, H., Dai, G., and Tsang, Can gaussian sketch- ing converge faster on preconditioned landscape? In Forty-first International Conference on Machine Learn- ing, 2024.
Wu, L., Wang, M., and Su, W. The alignment property of sgd noise and how it helps select flat minima: A stability analysis. Advances in Neural Information Processing Systems, 35:4680-46933 2022.
Xie, C., Zheng, S., Koyejo, S., Gupta, I., Li, M., and Lin, H. Cser: commumication-ecffcccee sgd with error reset. Advances in Neural Information Processing Systems, 33: 12593-12603, 2020.
Yu, Z. Shen, L., Ding, L., Tian, X., Chen, Y., and Tao, D. Sheared backpropagation for fine-tuning foundation models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5883- 5892, 2024.
Zhang, L., Thekumparampil, K. K., Oh, S., and He, N. Dpzero: dimeessooninndepeddett and differentially private zeroth-order optimization. In International Workshop Federated Learning in the Age of Foundation Models in Conjunction with NeurlPS 2023, 2023.
Zhang, S., Roller, S., Goyal, N., Artetxe, M.. Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., Mi- haylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, P. S., Sridhar, A., Wang, T., and Zettlemoyer, I. Opt: Open pre-trained transformer language models, 2022.
Zhao, J., Zhang, Z., Chen, B., Wang. Z., Anandkumar, A., and Tian, Y. Galore: Memory-efficien Ilm train- ing by gradient low-rank projection. arXiv preprin! arXiv:2403.03507, 2024.
Zhu, H., Zhang, Z.. Cong, W., Liu, X., Park, S., Chandra, V., Long. B., Pan, D. Z., Wang, Z., and Lee, J. Apollo: Sgd- like memory, adamw-level performance. arXiv preprint arXiv:2412.05270 2024.
Zhu, Z., Wu, J.. Yu, B.. Wu, L., and Ma. J. The anisotropic noise in stochastic gradient descent: Its behavior of escap- ing from sharp minima and regularization effects. arXiv preprint Xiv: 0000/003.00000 00195, 2018
12

---

Subspace Optimization for Large Language Models with Convergence Guarantees
A. The ReLoRA-like implementation
An equivalent, ReLoRA-like implementation Alg. T is as illustrated Alg. where we only present the case with small-batch stochastic gradients for convenience. In fact, applying ReLoRA with fixed or is not our contribution, as has already been used in several previous works et al. 2024 Loeschcke al., 2024). While leading the same results, this ReLoRA-likk implementation (Alg. 2 can potentially save computation it computes the subspace gradient directly without computing the full-parameter one. Consider the case where S n and we use MSGD and batch size of b. The computation complexity of GaLore's ' original implementation is 26mn for forward propagation, 4bmn for backward propagation, 4rmn for projection, 3rn for momentum update and 2mn for weight update. The computational complexity of our ReLoRA-like implementation is 2bmn + 2brm + 2brn for forward propagation, 26mn + 2brm + 2brn for backward propagation, 3rn for momentum updates and 2rn for weight updates. As illustrated in Table 3 our implementation can potentially reduce computation with little memory overhead.
B. Theoretical proofs
B.1. Notations and useful lemmas
We assume the model parameters consist of Nr weight matrices. We use X; E m to denote the ε-th weight matrix and æ E R (vec(X,) TT .... voc(XNN,)T) to denote the vector collecting all the parameters, d = - meng. We assume GaLorr/GoLLre applies rank-r; projection to the f-th weight matrix and denote
T8
81
min ISSS
de: 6 max dz. ISPSN
min, me
We define M as
[P( (
if me S no
M
if > mi
and m = (vee((i)) vec(MNz )olN)))) TT. While using Alg.
with MSGD and MP, it holds for m. S mg that
P.P.!o/ (P(0)) (0) T
t == 0;
(9)
(P( T (1 (1-B)) (t-1) + +B
t = KT, k EEN;
(1-B:)M
(1-1) + ((()) {
t= KT +r, KEN, 15r<T;
for my > ng that
G Q (Q
(0) 10) (0)
t= 0: 1= KT, N
M
(11- M (-11) + 31 G( 0 (Q
(1 M 11 + B G Q (Q)").
t= Ke 15T<T
and for both cases that
x (1+1) = x(() !M
Lemma (Error of GaLore's projection): Let G UVV be the SVD G p projection matrix P U[..r]].
Q Via r), min(m,n). It holds for S that
< (1 m G
and for m > n that
[GQQQ - G < (1-2) :) G.P.
13

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm 2 A-like implementation of Gal.ore
GolLoee algorithm using stochastic gradients with without
momentum projection
Input:
Initial point (0)), data distribution D, learning rate subspace changing frequency rank {ra Je optimizer
hyperparameters 31. 32, e, large batch size B.
Output: (=
Initialize LoRA adaptation X; We A, for = 1,2,.. Nr. where w x A = 0 and B 0: 1i No I 1=1
(0)
Initialize optimizer state {M, for 1. 0, 1,... T do for 1,2, ... .n do
and (V,
(-))))) 1 Nr
Tt=
to zero;
if / = 0 (mod 7) then
_ - V {())))
U. U.E.V (") p(o) U(. rel. Q²
Vla re]; (GaLore)
Sample (()) ~ ((ttmm..))
2 (
U(Stnn,rr): (GoLore)
( G if mm S ne:
R(())
G (0 !
mf ng:
else
V VA, ((z)))))))))))
if me S ng:
R
V B (2)11,
my ni:
end if
M
(1 - (P (1) R M 1- + 3 R M, /1 11 A Q + R
mf S ne;
(with MP)
if m4 ne;
M (1 (1) 11 + 3, R, (t), (without MP)
(1) <- -(1 -11-B2) V2) + B, R @ R
if using Adam then
~ M, /01111111)) B1), v 1(2//1111111 -3))
NO M, /(v v.(0 +c);
else if using MSGD then
N(0 M
end if
if 0 (mod 7) then
w
(++
w! (t)
+ B 10:
(1+1)
( (t)
if m S ng;
A
if m > ne
p(O)
(((-1)
if m < RE
~ if m > RE
else
W
(
A
A (1+1)
mz S ne
(1)
if ml n1;
B(O)
((t-)_
if m S n4.
B(O
(
if n6
end if
end for
end for
14

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Proof. Without loss of generality assume m S (the other be proved similarly). Let Q U[i + 1) :). It holds
that I = UUT PP QQ' T Thus,
- =1(1 PP JUEV 1/3
=tr(VE U (1 - PP (UEVT
-tr(E U "TQ' QQUUE,
where the second equation uses |
tr(x X) and the last equation uses tr(AB) tr( V and
Q Q I. By Q and p p 0, we have
U UUQQU- =
P Q
QQ
T
(P Q) =
Opxr
Orx(m-r) I m
(4)
Let 2 2 ... mm 2 0 denote the eigenvalues of G, 4 implies
Opxr
(m-(m-r)
x
E STUQQUUT
0 Ofm-r)xx (n-m)
diag(Or+1,"' am)
(n))) 0 (m-m)
(5)
())
Applying (5) to 3) yields
m
GP
= Σ
of
S
m
G
m
1=+1
where the inequality uses | = Gr = tr(E Σ) Σm of7
Lemma (Gradient connections):
holds for any t, T > that
(x: 11>
Vel( (tt(t)))) (T 1 Σ
V Ves(a(ttrtt)) (es(x((t>)] ||
(6)
Proof. For any r 1, -- 1, it holds that
(eff -
vef(x(()))
(2x + 2 +2 -
For any r = 2,..., -- 1. holds that
Vee - =
(ef(x()+.))) (ef(x((ti-1))
(Ve Vef(a((ttin))
(8)
where the inequality uses Cauchy's inequality. Summing from r = to 7- and applying
8 yields
|
(
2
Vel ((+r) )12 +2 j=1 t=1
Vef( -
1) Σ
(et((((()))) (ef(a((ts-1))1
j=1
which is exactly 6
15

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Lemma (Projection orthogonality): If P m. it holds for any A, B R [mxx
that
|PP A+ (T PP ) PP A 3 + (I(I PP-
B
(9)
Proof. By definition we have P P = It suffices to note that
(PP A, - B) tr(A (I- P B) = tr(0) 0.
Lemma (Descent lemma); Under Assumption
2 for update
x ((+1) (0) -nmm (0)
holds that
L ||x
f(x {(((()))
x011 +
m
21j
マ/ (z)((()) I|
(10)
Proof. By T-smoothness of f (Assumption 2 have
f(x(((+1) - f(x(())
S(Vf(x(()) (1) ),
xx (1+1)
- (!)))
+ x (0+1) - 11
{( (t) xx(++1) (1))
ml)
2 xx++1) =x(1) ) + T, (t+11) 1010
(z(((())
L
||x
(0) 1/
1 [V m1
17
(zx
2n
2
which is exactly TTP..
Lemma (Error of GoLore's projection): Let P ~ U(Stm.r):: Q U(tttt holds for all G Rmxx that
r I. E[QQ = r
E PP
.I.,,
(11)
and
PPPPTGGG
= (1 (1-5) m
|
El| - -G = (1- (1-5) n
G
(12)
P Proof. We refer the proof of 11] to Theorem 2.2.2 in Chikuse 2012). By PT I, we have
PP G G
=|[L[G (I -I- PP GG)
(I-
- (I-E|PPT)J]
(13)
Applying
to 13 yields
PP
G =tr G [I- 11- G)
Gr(GT) G)
m
|
The other part of can be proved similarly.
16

---

Subspace Optimization for Large Language Models with Convergence Guarantees
B.2. Non-convergence of Galore
In this subsection, present the proof for Theorem We first restate Theorem follows:
Theorem (Non-convergence of GaLore): There exists objective function f : Rd - R satisfying Assumptions 1
stochastic gradient oracle (F, D) satisfying Assumption 3 an initial point xx E I&d constant én > 0 such that for GaLore with any rank Te < min(me me). subspace changing frequency any subspace optimizer with arbitrary hyperparameters and any t > 0, it holds that
[V 112 60-
Proof. Consider target function /(X) = tr( pp x) where 1> 0, X E IRux with n > 1 and = ,1,0,..,,0 R". holds that
.. ,)
f(X) 2 Ip x 1 20
thus f satisfies Assumption Since Vx(X) = Lpp" X, it holds that
[V Vf(Y))l L|ppp" (X 1) S L
L
|al| Y1FF L| -II
thus f satisfies Assumption
2
Consider the following stochastic gradient oracle:
F(X; :)) =(x) Eo ur(QQ' x), and PEEDlE = 1] PE-plE -1] = 0.5,
where ē o/v((rr 1 and
Q =- diag (1, 22
1a)(n-1),
vn -I
Note that VF(X:E) VX(() + QQQQ T, it holds for any X E g that
Eg~D\V/ [) (v
n-
E (ao>II/VF((X V
||
0
nn
1)n/2 2
1=
thus oracle (F, D) satisfies Assumption 3
Consider the following initial point:
X (>p)
where 0 < À i scalar and A 1)xm is an arbitrary matrix. We show that GaLore with the above objective function f, stochastic gradient oracle (F,D), initial point (0), arbitrary rank 0 frequency and arbitrary subspace optimizer p, can only output points (() with |V (t) ||
n, arbitrary subspace changing
for 2 0.
When 5 f, GaLore recomputes the subspace projection matrix at iteration f. If the first row of x (t) equals Ap i.e.
x [1, :] = Xp the stochastic gradient is given by
Lpp X + DQQ diag (L,, v2 Vn vn- 1((1)))
since LA < o computing SVD yields
LX
0
0
0
(
Tg(t)
n
17

---

Subspace Optimization for Large Language Models with Convergence Guarantees
0
C1 0
Vn
lā
0
0
S
2
0
0
0
Σ
where G.... E 1.. For any rank < n. the projection matrix is thus
0
p(t)
0
0
S--r+1
gnxr.
:
0 Sn-1
0
Ca
0
0
Using this projection matrix, the subspace updates in the following T iterations is as
A (+ (P()))
((+Aa) = x0) (()
[1,+ = >p"
for A, -1,,,..,, Since [1,) Xp T, it holds for all f that [1,) Ap and thus
V (9) 11 1,2x² = 60-
Remark 6. When setting B = 0 in the quadratic problem setting (Sec. (). the quadratic problem is equivalent to the counter-example we construct in the proof of Theorem The illustration in Fig. 6 displays the loss curves for this problem.
B.3. Convergence of deterministic GaLore
In this subsection, we present the proof for Theorem GaLore using deterministic gradients and MSGD with MP is specified as Alg. 3
Lemma 6 (Momentum contraction): In deterministic GaLore using MSGD with MP (Alg. 3 if 81 S term M(
has the following contraction properties:
When / = 0. it holds that
| (0) - Vif(X())) <(r 1)(1 - -5281)
V [ef(
vef(cc""))
2(1 - 5631) (
T-1
+ T
Σ
(x=))))))
(14)
When t kr, & N it holds that
|M (ef(2((0)) - 1 1 (11((1-
8z
4
2(1 82) T-1
[(f(z(( + 5(1 - 31)
(ef(((")) - ve
r=0
+(7 - 1)(1 - (z)) Σ
V (z -
(15)
18

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithms using AdamW
GoLore@50%
0.7
L.B. GaLore
0.6
Full Params.
0.5
Loss
0.4
0.3
0.2
0.1
0.0
200
400
600
800
1000
Iterations
Figure Loss curves of algorithms using AdamW. GoLore @ 50% uses GaLore in the first half shifts to GoLore in last half, Full Params. denotes full-ppraan parameter training.
When f kr + r, le E N. S < T, it holds that
(t)
(1--111
(1- (1- 56 B1
[|
(()(
[ >> 5(1 31)
B1
2
10r81
+ 82
(M
(16)
Proof. Without loss of generality assume me S ng (the other case can be proved similarly). When have
M (0)
Vef(2 (0) )0) (P; (P. /T - v)ve((z - (1 - v.f (0)
(1- - ve 00 + (1=
-[1-6)31]\V.((<>>
(17)
where the inequality uses Lemma I and Jensen's inequality. Applying Lemma to yields 14
When f. = kr, 1 E N we have
| (9) (1
= -IPP(") (1-))T(1111)))))) + Vef(2(")) - (I (I e
=IIP(" (1 (t-1) - Ves(x( |[I (P(() (
<|[ ( (1-1) (()) 1/ + (1 8z) ())
(18)
where the second equality uses Lemma and G.ft = vef(x (1), the incquality uses Lemma and |P (P.('(()) ) = 1. By Young's 's inequality, we have
|M (M 11-1) (ef(2("))11
=|(M, (el()(((11))) (VV(((2()) (e)(a(t-1))113
19

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm 3 GaLore using deterministic gradients and MSGD with MP
Input: Initial point (0) learning rate 7), subspace changing frequency т, rank {re) momentum parameter 31. Output: (xx()) JZ-
Initialize optimizer state {M, 1-
to zero;
for t = 0, 1, ... T do
for { = 1, , do
_
(z)((()));
if = 0 (mod r) then
U, Σ, V SVVD(G
if me S nt then
p.l + U[U rel:
M t (1 - (P())( T p( + (
x x -npl M
else
Q(1) [(a: rel;
M (1) t (1 -3)) (1-1) (Q (t ) TQ + G q.
x, ((+1) + x n (Q/ )T
(1)
end if
else
if me < ny then
P( f- P(" p(t-1). 1)
M (t) t (1 (1-3))
M (-11) + (P !
x (++1) x (t)
pp 1 M
else
Q Q (1-1))
M (t) t (1 - M (- + 3,G Q (0)
x((+) x t Mn,,
(t) (1) ()))
end if
end if
end for
end for
1+
IM |M (t-1) - (ef(z((-1))1 + 1+
4
[ef((x()) - (e 12.
(19)
4
Applying Lemma
2 and 19 to 18) yields 15)
When = Kr +r, E.
< T. we have
| (1) (2
=I1(1 RM) (1-1) +3
<(1 - M (1-1) Vef(x + B1l [ (kT) (P!kT) T T)
P!(h
(20)
= where the inequality uses Jensen's 's inequality and p(l) = P! - p!! p((t) bounded as (1). For the second term, we have
The first term can be similarly upper
(I - P( (KT) (P( (kr) () 112
de
II(I - (KT) (P! (b( (TV
1
4
+
1 +
4
|[T -o (KT) (p!
(K)))) T>V)(a)))V - (
5z
de
_/
5
[Vee(((00) - )
<
+
(1
+
(21)
4
5z
20

---

Subspace Optimization for Large Language Models with Convergence Guarantees
where the first inequality uses Young's 's inequality and the second inequality uses Lemma | By Young's inequality, we have
(e (1 δe _ [[ + [+ + 8t)
4 |Vef(z(9) - vef(x((>>)) 172.
(22)
Note that / 1 Ki + r, we further have
[vf((z(0)- - (ef(z =
V (ef(x((tt))))) - -vr(((((rti11)
Sr V ( Vef(2 (Ar+ 1) 1170.
(23)
where the inequality uses Cauchy's 's inequality, Applying
22 2.3 to 21
yields
(I - p( (( (p( (kr) (2x 1
$ 1
[ef(
+ 10r
de Σ
[el((lltt)) Vef(allrti-1)))1
(24)
2
Applying 21
24 to 20
yields (T)..
Lemma 7 (Momentum enror): Under Assumption 2 if0 < 31 < 1 in deterministic GaLore using MSGD and MP (Alg.
it holds for any K 21 1 that
mm ((
5(1 - 31)
5T(T - 1)
T T- 1
L2
Kr-2
x ((+1) - x (012
(1 - 5/4)589
8/4)
(1 8/4),3
1 8/2
2
Kr-1
+
| (1)
(25)
8/4
(1 8/4)T31
t=0
Proof. By Lemma 6 we have
Kr-1
M
(1)
(1-(0)
(1- (1-
31
Kr-2
Σ
M
(1)
(ef(
1=0
1=0
- 55(1 B1)
5-(T 1)31
Kr-2 Σ
+
+ (T 1)
[ef(x((+11) - -ve((e())1
8r31
di
1=0
+ 2 +
(1-
5e
31
Kr-1
Σ
|/ (z: )1.
2
1=0
which implies
Kr-1
Σ
|M (t) (0)
1=
5(1 - -8))
+ 5T(T 1)
T-1
Kr-2 (ef(x((+11) (ef(
+
(1 0
(1 (1-de/4)6..
(1-
1=0
1 8e/2
2
Kr-1
+
(z (+)
)|
(26)
1 8e/4 (1
8
1)
Summing 266 for f = 1,.., Ny and applying Assumption yields 25p
21

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Now are ready to prove the convergence of Alg.
Theorem 10 (Convergence of deterministic GaLore): Under Assumptions
if hyperparameters
64
1
3631
35 807 L
3
<< 31 11
72
3
0 1
min
4L
80L
V
16T L
(27)
GaLore using deterministic gradients and MSGD with MP (Alg.
converges
Kr
164
(1)
)13
(28)
KT
Kn
for any K 1, where A f(x:(0)) inf f(x:).
Proof. By Lemma 4 we have
Kr-1
V 112 2[((xx
2 - [(x(k)))]
Kr-1
Σ
| (1)
(z)
1=
L
(1+11
x 1013
(29)
Applying Lemma to 29 and using 6 < < yields
Kr-1
6 8
(
4
3T
< f (0) ((xx(Kr))
2
17
1
L
20(1
B1)L²
20T(T - 1)L2
4(T - 4(T- 1)L23
Kr-1
[x+11)
(000
(30)
1/2
35,3
35
331
0=0
By 27
we have
L 20(1 B1)L²
20-(T
1)L²
4(7 1)L2
and
max
(31)
4
31
4r/2
3537
36
33
Applying
331 to 30 yields 28
We now prove Theorem which is restated as follows.
Corollary 11 (Convergence complexity of deterministic GaLore). Under Assumptions 7
ifT 2 64/(38) and we choose
8 =1
64
T
383
-1
807,2
80
16r
4T. +
+
35
35
3
GaLore using deterministic gradients and MSGD with MP (Alg.
converges
LA
T M
[V
(32)
S
where A = f)) - inf f(x). Consequently, the computation complexity reach an e-accurate solution such that [[] Seis 0
LA
80745
22

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Proof. T 1 64/(30) guarantees 7 r. Let T Kr where K N and 0 S < Ifr 0,
32 is direct
result of Theorem 10 Ifr > 0, applying Theorem 10 to K = K yields
Kr
LA
VV
Vf 1 012 =0
KT
85/22T
B.4. Convergence of large-batch GaLore
In this subsection, we present the proof for Theorem 6 GaLore using large-batch stochastic gradients and MSGD with MP is specified as Alg.
Lemma 8 (Momentum contraction): Under Assumption B
in large-batch GaLore using MSGD with MP (Alg.
0 < 81 - 1, term _ has the following contraction properties:
When / = 0, it holds that
E|| M 00)
(x $2(T 1)(1 55
(((())))) - vef(x
4(1 4(1-6631)
43102
Σ
E Vef |1
(33)
7
B
When t kT, & No, it holds that
E|| M (0)
(x )
1 1 (11--
4 (1-) 31 BIIM ()
4(1 62)
E|ll V ff ( + 5(1 31)
[((V15((<(0)) - ves(a((-1))
5r81
T
r=U
50
+ 2(T - 1)(1 - 5z)
E ee (z (2f(2(((TT)) )12b}
(34)
B
When t kr h E 1 15r< it holds that
56 4) B1 -
B1| M - V |121 (1--0-111111
1
EIIM! - vel(o((-1))) 1))1
88
5(1 31)
V ef
1
Ell Vef(x() vef(a((-1))1
2
15r31
11,81
V (
33 oz.
(35)
82
5eB
Proof. Without loss of generality assume m, ng (the other case can be proved similarly). When = 0, we have
E |
(0)
P( T.. (0)
=E]| 00) (0) - 1) + 3, (G - Vef(x - (1=
<B 00 (T) - I)G + G (0) + --) )
(36)
where the inequality uses Jensen's inequality. For the first term we have
(P (P( )T () + G
vef(x(
23

---

Subspace Optimization for Large Language Models with Convergence Guarantees Vef(a (z)
< P (P. G
|/ + 2E||
<2 - (.)) G A) + ||0 G vef(=!"))
(4 20
52 - 6r)
vel 10) > +
(37)
B
where the first inequality uses Cauchy's inequality, the second inequality uses Lemma the third inequality uses E B V=f(< S of/ /B (Assumption Applying (37) and Lemma 2 to 33 yields (3
When L = kT. k E N we have
||| M 8 (c) (ef(2(0))1
=I P (1) )
(11 B1) B 11 +B ve((x(())) (I ) Ve
PE (t) (11 B,)M, (-11) + +B Vel(x 11]
+ +[ - P ( ) (e)((( 11?).
(38)
By (P(() ) we have
where the second equality uses Lemma
B[| (P (1) [ - B1) B (1-1) + {
<I[[|(1- - B:) + B, - vef(x("))
=E[I((1 ( )
+ ( ( Vvf(<()))
<B[I 3.)(M( (-1))
vef(x -V (0
SEEIG (=f
(39)
where the last inequality uses the unbiasedness of G (Assumption) 3
By Young's inequality, we have
El| M (t- 1) - vef(x(()))
[MII(MM!! (t-1) (=((x((111)) - (Vel(z!0)- (e((xx((11))11
1 + 5eB1 B
(t-1) Vef(o(t-1))11 (1+
4
E (ef(((t)
Vef(
(40)
3031
Applying (40) to 33 yields
E
P(P(()) (P()))(((1 [11-)) 31 vef(2
3602
1
31
Ell
E|IM (t-1 (- +
4
B
5(1 31
E
Vef(=(1)
[ef()((-\))11
(41)
3r
For the second term in
38
we have
[|[ - P (
<2E[]|[I - P. (P. (0 ) J. (0 [
2E|] p. (p(0)) TT(! - (e)(
<2(1 - [ ||
(1)
+ 2E [E||G
(1)
- (:61-8)55|lv+f('''' MI 4
(42)
where the first inequality uses Cauchy's inequality, the second inequality uses Lemma 1 and || P(O) (P. (1)
T the
third inequality uses Assumption Applying (41 to (38) and using Lemma Zyields (34)
When = kr +r, E N. 1 5 r < we have
E M, (1 vef(2.(0))
24

---

Subspace Optimization for Large Language Models with Convergence Guarantees
(1 31)(M((1)
+ + T ves(a(")))
-1]1I(1 (M)
((-1) Vef(x! + (P, (P(2) (0) +33
I)Vel(x!))) )1
+ +..EEP ( ) - v
S( 1-1-3:)-1 31) (1- - Ve + BII P (
+ |EPP (P()) - - ).f(
(43)
where the second equality uses the unbiasedness of G and the independence implied by p( = P p(t-1) the inequality uses Jensen's ss inequality. The first term is similarly bounded as (40) For the second term, we have
Bill(I P (T)) (P&
(kr))
/e ||
56
EI p(th (k)) (P(hT)) G (kr) ||:1
1
+
4
BIIlII - p((t) (P! (PA (k)) (V -G( )
+
1
+
5z
1
35
BIIG ||]) + 2
E|||
[+ bz
4
El|GG(T)
(e
4
+
1+
|||| (e) Vef(
(44)
dz
where the first inequality uses Young's 's inequality, the second inequality uses Lemma I and Cauchy's 's inequality. We further have
36g
B
[1] [1::]
(kT)
+
1
4
B[|GG(Tr)
Ves( (kr
4
5z
36g
|1
+ dz
11
Bll BlIl((T)
(KT)
4
38
(( (kT) |1 + Foo1
4
b.B
8c) (1) MF + 1+ 3z
11o2
Bill Bl]Vef((())) (kT)))(
(45)
2
8
where the first inequality uses unbiasedness of G( (KT)) the second inequality uses Assumption 3 the third inequality uses Young's inequality.
Applying
45 to and applying Cauchy's inequality yields
[[[ - ( TV ||3:]
(1
52 2
1102
15r
E ElI
|1 +
+
E V Vef(e ef
Vef(x((
(46)
8
For the third term, we have
p(rt)) T ((G! vef(x S E - vef( s oz.
E||l
(47)
| (KT) (p(kT) T122 = 1, the second inequality uses Assumption 3
where the first inequality uses
Applying 40
4064600
47
to
yields
35
Lemma (Momentum error): Under Assumption 2 3
0 < B1 S 1 in large-batch GaLore using MSGD and MP (Alg.
it holds for any K 2 1 that
Kr
B m (4) V (x) (
25

---

Subspace Optimization for Large Language Models with Convergence Guarantees
5(1 - -1)
15r(r - 1)
2(T 1)
Kr-2
+
I
El ||| (t((t))) - x+))
(1 6/4)684
2(1 5/4)6
(1 - 8/4).3
6/2
4
Kr-1
B|Il |1
5/4
(1- - 5//4)BB/
k=
5K
11KT
KTß1
0²
(48)
(1 B
11-5/4)08
1 1-0/4
Proof. By Lemma
8 we have
Kr-1
El| M
(0)
Vef(=(()))1
1
1
d8
31
Kr-
Σ
B M vef(x!0)
4
15(1
31)
(T - 1)81
Kr-2
+
+ + - 11
Σ
B|ll
Vell (z - vef(2(())
V
28
1=0
dq
Kr-1
5K
11Kr31
+
+
1
31
[ Vel (2) (1)
11 +
+ KT o2:
B
t=0
which implies
Kr
B||| M (=f(
(1)
5(1 B1)
15T(T 1)
2(T -(T-)) 1)
Kr-2
B|ll ( -eef( 1121
+
- 5
2(1 - 6z/4)5z
(1 - 8
8c/2
4
Kr-1
+
+
B||l Vef (1) |
8e/4
(1 5e/ $1
t=
5K
11KT
KTB1
+
(1 B +
of.
(49)
(1- 5
1 0r/4
Summing 44 for L = ,,,,,,,,,,,,,, .N and applying Assumption yields 48
Now we are ready to prove the convergence of Alg.
Theorem 12 (Convergence of latge-batch GaLore): Under Assumptions 13
if hyperparameters
128
1
383
5 40 L
33
0 < 31 < 1, T2
0 < 17
S min
(50)
33,5
4L
80L
32-L2
GaLore using large-batch stochastic gradients and MSGD with MP (Alg.
converges as
164
160
352
32
E V (1)
<
+
+
o2
(51)
Kr
Knkr
38"B
35
t=0
for any K 2 1, where A = =f(x inf f(z).
Proof. By Lemma
we have
E E[[VS( (0) ())) [x
KT
Elll m (1)
(z)
26

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Kr-1
1
I x (t++1)
x: (1)
(52)
Applying Lemma 9 to 52 and using 0 5 < yields
0 16
Kr-1
Σ
|ill f )
4 3T
2
20K
4
4KT
f2(((x))))
-[(x(k)))]
0²
11
3
36B
20(1
B1)L2
107(7
1)L²
8(T
1)L2
Kr-1
Blll (++1) - x1
(53)
172
3031
331
By 50 we have
5
16
5
1
L
20(1 B1)
10T(T 1)L2
8(T 1)
and
2
max
(54)
4
3T
8'
4np²
17
303
3,
Applying (54) to 53 yields
51
We now prove Theorem 0 which is restated as follows.
Corollary 13 (Convergence complexity of large-batch Gal.ore.. Under Assumptions (256g)) VĀLLL) and we choose
if 2 2 + 256/(35)
+
0T
81
1
LA
128
T
35,31
80L
2
32T
4L +
+
3587
8
38
B
GaLore using large-batch stochastic gradients and MSGD with MP (Alg.
converges as
LA
LAO²
E (9
10
(55)
T
85/2T
/
where A f(x:(0)) - inf (xx). Consequently, the computation complexity to reach an E-accurate solution such that [VV[())) < e 0
LAge
+
LA
+
Proof. T> + (38( (128a)) ((9/8LA) guarantees T r. Let Kr + r, where K No and 0 Sr <
55) is direct result of Theorem 12
If
0, applying Theorem 12 K K yields
RT-1
Σ
EI
11
KT
Σ
El|
=
LA
LAO2
T
KT
85/2T
87/2T
1=0
27

---

Subspace Optimization for Large Language Models with Convergence Guarantees
B.5. Convergence of Gol.ore
In this subsection, we present the proof for Theorem is specified as Alg. Lemma 10 (Momentum contraction): Under Assumption 3
g GoLore using small-batch stochastic gradients and MSGD with MP
in large-batch GoLore using MSGD with MP (Alg. 5p, if
< 31 - 1, term M has the following contraction properties:
When t = 0, it holds that
B 10)
Ves
S(T 1)(1- -531)
El (e - (
2(1 - 2(1-6631 +
Elll V (f + 8823907
(56)
When t = kr, k E N", it holds that
(er( (1) [[2] - -e ( 6e
11-(1-2)
B M (1)
31 BII (e(( 112]
2(1 - 5z)
5(1 - 31)
[1 15 (xx (k+++) || +
E (el(((()) - (x
E
31
-=0
( - 1)(1 - 52)
E Bl (ef(x(( 112]+ 05.3002
(57)
When
-k t
k E 7, holds
holds that
MI|M (1) Vif( |1 (1- 1
56
4
Bi E EIIM (1-1) (e
E1
88
5(1 81)
1
11 +
E[ Vef((() Vef(or(
2
30.1
10r31
ElI (KT+i))
V (e(((utrii-)) S.02.
(58)
82
Proof. Without loss of generality assume m. S ng (the other case can be proved similarly). When = 0, we have
|| vef(z
P| 00) (P( 1 a (z)
P| (0) (P) 0)) - [Vv, ())
BPEIII (P) (0) TGG! v=((
=tr((Vef(zz)) (0) P! -
+ (E (G (0) - Vef(x T E Ep
(G - Vef(x (1) ))))
(59)
where the second equality uses unbiasedness of ( By Lemma
we have
[[(3P (P) r) =I - (2 E 10) (P(
=I - (2 F6
thus
((((ee(((00)) (E( ( (P(()) -01 5c - Ve)
-11
28

---

Subspace Optimization for Large Language Models with Convergence Guarantees
6(1-6+8111 Vel
(60)
Similarly, by Lemma we have
tr(E (0) [G Vef(x!!1)) T Ep- (PP (PPT)" - Vef(x(())))
E ( - -ve((x()))
(G) - -ve((e -vellal
=tr
me
-. (1) Vel(
<ò.0
(61)
where the inequality uses Assumption 3
Applying 61 and Lemma 2 to 59 yields (56).
When = kT, E N we have
[|| M \ef(
=I[| P/ (pp(((((())) (P(")) (11 (1))) + +.G.
Vef(2(")) (I (
[1 - (t-1) +
Ves(a + (1 6τ) (.)
(62)
where the second equality uses Lemma and Lemma 5
For the first term, we have
E[ll (1 M (1-1) + BIG )1)
[1] - (MM (1 v=)(x(())) - 31 (G (x)( [12]
<][[[( - (.) v.((z( + GEIIG - ves(
<(1 - [I) (-11) -ve((x )12] + B9
(63)
where both inequalities use Assumption 3 By Young's inequality, we have
M (- (=f( [ia]
-M] (t-1) Vef(x((-11)) (Vef(x(1)) Vef(
1+ 82,1
BIIl (1-1) - vel(=(t-))113 1| (1+
4
E ((((t)(( (
(64)
Applying 633
64
and Lemma
62 yields (7).
When ( kr rr. N, we have
E|l M (1
(1 - ()M( vef(xx()) +. (1) TG vef(< (1)))
=E[][(1 - (M) (1-) v.((=())++(((()) (1) T (v) (1) (1)) [|
+ +B?E!P!00 (P.(0) [( ())
<(1 3:)E[| M (1-1)
+ B P (ef(2
(1) (P("))
(65)
where the second equality uses the unbiasedness of GI and the independence implied by p.()) p!!-"), the inequality uses Jensen's 's inequality. The first term is similarly bounded as (64). For the second term, we have
(kr) (P (K))) ( BiIl(I -
< (1 (1 Bill(T I P! (kt) P( (P) (r) T ( (+)))
δz 4
(p.tt))
29

---

Subspace Optimization for Large Language Models with Convergence Guarantees
+
1 1+
B[I (I - ( ) - (es(
36t 4
[ V e ( (k)) || + (1
4 5e
(el(((()) - -ee((o(( [1:]
(66)
where the first inequality uses Young's 's inequality, the second inequality uses Lemma and I Pl (P((r)) By Young's ss inequality, we have
Tl1 1.
6g 1
B VelVef(a 11 + (1 + 4 5z Blll BlIVof((z!0) - )ef( (67)
||| V o a (6)) 11 -
4
Applying (67 to (66) and applying Cauchy's inequality yields
[II[[I
(((T))
dp 2
E V
10r 5z
E1J V ((o Vel(oc(trti 11)11)
(68)
For the third term, we have
((T) ( Vef( S E||| vef( S oo
E
(69)
where the first inequality uses ||P (P
(k))
(l T//2 = 1, the second inequality uses Assumption 3
Applying (64
68
669
to 65 yields
58
Lemma 11 (Momentum error): Under Assumption 2 3
if 0 < B1 S 1 in Golore using MSGD and MP (Alg. 5), it holds
for any K 2 that
Billm (1) - {=(x())
5(1 (1)
55(T - 1)
T-1
L2
Kr-2 2
Σ
- x 10
(1 8/4)688
(1- 6/4)
(1- 5/4334)
1=0
1-6// 5/2
2
Kr-1
Kr
E
(70)
6/4
(1- 8/
1 - 88/4
Proof. By Lemma 10 we have
K--1
- 1 (
Kr-2
E|| M (1) - (e((((()))1
31
Σ
El M - V )0
4
1=
0=
55(1 - 91)
5π(r 1)
Kr-2
+ (T 1)
Σ
V
vef(
dR
1=0
2 +
(1
5t
Kr-1
+
31
E|l ( (2 (1)
+ KK
T
2
which implies
KT
[I |||M (1) (e((2 1121
t=
5(1- - 31)
57(T- 1)
T-1
Kr-2 2
E||| (+l(((t))) - (x)( )1
+
(1 81/4)88.3
(1 -5//////
(1- 5e/4)
30

---

Subspace Optimization for Large Language Models with Convergence Guarantees
1 - 6t/2 +
2
Kr-1 E
KT
(71)
1 6
(1 (1- 61/4)TB1
1 6
Summing 71 for 8 = 1, Ny and applying Assumption yields 70
Now are ready to prove the convergence of Alg. Theorem 14 (Convergence of Golore): Under Assumptions
13 if hyperparameters
64
1
359
35
3/1
0 < 31 S
3
0 17
S min
4L
V
S0L2
8072
V
16T
(72)
GoLore using small-batch stochastic gradients and MSGD with MP (Alg.
converges
1
164
32
E
V
S
(73)
KT
36
for any K 2 1, where A = -((x(0)) ) i f(x)
Proof. By Lemma 4 we have
(zx ([)( B[f (x)()(()))
Kr-1
[E[ m (t)
(z)
Kr-1
1
Σ
E 2 (e+1) (0))
(74)
173
Applying Lemma
11 to (74) and using 8 < yields
6 8
Kr-1
E|ll Elll Vf
4 37
2
2
B[f (z (0))
[x(x((
4KT
20(1
B1)
207(T 1)L2
4(7 4(7- 1)L2
Kr-1
Elll (++1) - (1
(75)
172
353?
35
331
By 72
we have
8
6
L
20(1 B2)
20-(7
1)L2
4(7 1
and
> max
(76)
3T
4rj²
11"
3537
35
33
Applying 776 to
yields
73
We now prove Theorem which is restated as follows.
Corollary 15 (Convergence complexity of GoLore). Under Assumptions and we choose
3
isT 2 2 128/(30) + (128g) 1/2/0))
8
3/2
2T
8
1
+
LA
64
358
31

---

Subspace Optimization for Large Language Models with Convergence Guarantees
80L2
80T
16r
4L
+
+
3581
3
3
GoLore using small-batch stochastic gradients and MSGD with MP (Alg.
5 converges as
(
(
LA
T
B
11 =0
(77)
T
85/2
8
where A = f(x(0)) in f()) Consequently, the computation complexity to reach an e-aceurate solution æ such that LAo" 67/2
[Vf < is 0
+
LA
8P + 1)
8
Proof. T> 2 128 (36)
(1280) )2 1//9/////// guarantees T T. Let Kr + r. where K N and S If
r= 77 is direct result of Theorem 14 If
0, applying Theorem 14 to K = K + yields
Kr
Rr-1
LA 851
LAO?
Σ E
11
Σ
El| [(
=
+ V
T
KT
8T12T
C. Convergence of GaLore under isotropic noise assumptions
Based on the anisotropic gradient noise we use to construct the counter-exampee in the proof of GaLore's con-convereence under standard assumptions, an interesting open question is whether GaLore is guaranteed to converge if the noise are further assumed isotropic. In this section, we consider the following additional assumption:
Assumption 16 (Isotropic noise). The distribution of stochastic noise for each gradient matrix is invariant under orthogonal
transformations, i.e., it holds for any layer & = 1, .N. parameter E Rd and orthogonal matrix O₃ E me O₂ E R xxy that
veF(=;)) V (a) dist O -
where A dist
represents A and B shares the same distribution.
Remark 7. The property in Assumption 16 can be satisfied by multivariate Gaussian distribution, e.g., vec(V (o(;V)
vef(z)) ~ NO, of Imex
Besides Assumption T6 we consider an additional assumption, which crucial in analyzing the projection error.
Assumption 17 (Leading property). Let Dz(x) denotes the distribution of gradient noise (<F(x:)) Vzf(x). We
assume (x( satisfies the following "leading property": if A ~ De(r)), B E R satisfies B11 2 B2 2 ... 2
Bmin mmin(me.ng me) min 2 0 and B:j 0 for i * j. the SVD decomposition UEV = A B satisfies
1 Σ
E E
& me? mE
k. mé
m S ne
r
vI ne, my > ni.
Though not fully established in theory, we can empirically validate that multivariate Gaussian distribution may satisfy Assumption 17
Specifically, we consider the following experiment setup. Let veo( A) ~ NO o² T22x32) for some noise scale a > 0 and select a fixed matrix B with Bn > B22 2 ... 2 B32.32 2 0. In order to validate the properties in expectation, we sample matrix A for 200,000 times and uses the empirical expectations B[U,)'s to estimate the true expectations E[U,,]* |s.. Figures represent results under different noise scales a 10, 1, 0.1, respectively, where "r ro" in each figure plots the line connecting points (k, no Σ , E(U3) for k 2, 32. As presented, all lines "r ro" with 32 are above the line "r = 32", which is guaranteed to pass through the points (k, ( k 1, ... 32, in theory. Consequently, we have good reason to believe that multivariate Gaussian distribution can empirically satisfy Assumption 17
i
With Assumptions 16 and we can establish new error bounds for GaLore's SVD projection.
32

---

Subspace Optimization for Large Language Models with Convergence Guarantees
1.0
0.8
0.6
F=
r=
r=17
r=25
0.4
r=
r=10
r=18
r=26
r=3
r=11
1=19
r=27
r=4
r=12
r=20
r=28
r=
1=13
r=21
r=29
0.2
r=
r=14
r=22
r=30
r=7
r=
r=
r=31
r=
r=16
r=
r=32
0.0
10
15
20
25
30
Figure Observations with small noise scale 0.1.
1.0
0.8
0.6
1=1
r=
r=17
r=25
0.4
r=2
1=10
1=18
r=
1=3
r=
r=19
r=
r=4
1=
r=
r=
0.2
5=
1=
r=
r=
r=
r=
r=22
r=30
r=7
1=
r=
r=31
r=8
r=
r=24
r=32
0.0
0
10
15
20
25
30
Figure 8. Observations with medium noise scale 1.
33

---

Subspace Optimization for Large Language Models with Convergence Guarantees
1.0
0.8
0.6
1=1
r=
r=17
r=
0.4
1=2
r=10
r=18
r=26
r=3
r=11
r=19
r=27
r=4
r=12
r=20
r=28
0.2
r=5
r=13
r=21
r=29
r=
r=14
r=22
r=30
r=7
1=15
r=
r=31
r=8
r=16
r=24
r=32
0.0
0
10
15
20
25
30
Figure 9. Observations with large noise scale 10.
Lemma 12 (Error of GaLore's projection under isotropic noise): Let G Vef(x) and E veF(z; Vef(x),
projection matrix P = U [. re).
Q Vi : rz] where UEV G + E is the SVD of stochastic gradient (xF(x; it for my S my that
holds under Assumptions 16 and
PP G S
1
m
and for me > ng that
BlI - G <
rt ni
G
Proof. We only consider the case where my < neg, as the proof for the other case is similar. We first conduct SVD of G and get G V. holds that
PPT G =tr(G PP G)
=tr(Vo U, PPT
=tr(E, U, Up)
(78)
Denote Ü U,J U and V VTV. V. it holds that U VT (U,TO) V)T is SVD of U (G E)Vo
U EV, + En E + Eg. By Assumption 17
dist
we have
k 1==1,2- 1.2,...,ma m,.
(79)
1=
me
Let 01 2 02 2 ...0m 2 represent the singular values of G. taking expectations of 78 yields
E(| PP
G =tr -tr E PP PPT
34

---

Subspace Optimization for Large Language Models with Convergence Guarantees
m/
i=1
/=1
m2
TE
TF
|
(80)
mg
where the inequality applies of 2 o3 2 ...om and 79
Based on
80
we have
E| Pp PPTG- - G = | - E EI
1-
rt
GGll
my
which completes the proof.
Lemma 13 (Momentum contraction): Under Assumptions
3 17 GaLore using MSGD with MP, if 81 S term
0 has the following contraction properties:
When t = 0, it holds that
T-2
E | (0)
v.f(((o)) 1( 66)
RI e (( (
r=0
2(2 - 5r)
T-1
Bll V (f B907
(81)
T
When t kr, & N,, it holds that
E||l M (ef(x 1(1- (1- 1
69
31 BIIM 1-1) - (e
4
2(1 52) E||| v (xT ||2]] + 5(1 31
E (() - (e
(r 1)(1 - 5e)
E ([ Vef(an(kttr)) +2
(82)
When / = kr k E N. S5 holds
holds that
(z |1 - (1 (1-(1-
1- 8e B1 El| EIIM 1-1) (tx
E|| M
5(1 31)
B RE /5 (1) )12]] +
Eill (e)((()) (t((
2
5r,1
10r31
V ( So
(83)
Proof. Without loss of generality assume S ny (the other case can be proved similarly). When t = 0, 81 is direct
result of Lemma & by letting B 1. When / = 0. we have
M 00) (0)
=E|1 P( 00) (P(()) (0) T G 0) - (x)
=E]] P
(0) (p(()) (0) - (v 11)
I 3 (0) (P.")) (+((2())))
(84)
For the first term, we have
[[I( P (0)
(P("))T I)
(1)
35

---

Subspace Optimization for Large Language Models with Convergence Guarantees
- - 3,) | P| (0) (Pt ) ( BIIK PP: (P. (0) V)
< - 8)) + (1 5e)) I
S (2 62) (z))))
(85)
where the first inequality uses Lemma For the second term, we have
(G (0) (ef( )) Bl|G (=f(z s oz.
(86)
Applying 85
86
to and using Lemma 2 yields (81)
When t kr, ke E N according to the proof of Lemma we have
El|l MIlM (1-1) V. (z))
1 + 60.1
BIIAA1 (11) - Vef(a (1)) + (1+
4
E
((f(((() - (e 11
(87)
1
and
E|| M, 10 - ves(z
-E 1 (P( [( M ( + 31 G.G. (0) - vef(
[[1
<B[ [ (M) (t-1) Ves(x + 33002 + - 5 Vel (1) 11?)
-
(88)
where the last inequality applies Lemma
Applying
to 88 and using Lemma
2 yields 82
When t = kT + r. k N. 1 < we have the following results according to the proof of Lemma
8
| 0 (0
S(1 B, B M (1-1) Vef(= 3 [[] ( (Z)
(zx
+ P (1) - V
5(1- B1)
+ EIl P [ + +3002
Vef(((
(89)
For the second term, we have
E
EII
(((TT)
(P! (T))) (e 11)
E[l[(I P! (T) ((((t) f ||)
+
4
B[I[[I P! (K))) (P (kT)) (V( V. (e
1
+
5z
38
E||l V. (co
+
(1
Eill (=)))))))))))) (x
4
5z
dt
4
V (2)
||22] + 2
1+
((]Ver(<>()) - vef(x( (KT) )|
2
5e
de 2
10r
BIIV:5(a (1)
(2 (xr+
(90)
82
where the first inequality applies Young's 'sun'ssiinnn inequality, the second inequality applies Lemma 12 the third inequality applies Young's 's inequality, the last inequality applies Cauchy's inequality. Applying (77) to (89) yields (83)
Lemma 14 (Momentum error): Under Assumptions any K3 2 that
16
17
0 < 81 S in GaLore using MSGD and MP, holds for
K
Blllm (4)
(zx
36

---

Subspace Optimization for Large Language Models with Convergence Guarantees
6(1-81) B1)
5- - 1)
2(T 1)
Kr- 2
L
E |||| - ax(1
(1 -1/4)88
(1-8/46
(1 (1- 5/4)33
2=
- 8/2
4
Kr-1
KT
E
(91)
5/4
(1- 8/4)T31
1 - 68/4
Proof. By Lemma 13 we have
Kr-
Σ
||| M (0) - (e((
- (1 11-11-90
(1-6)
1-
dp
31
Kr-2
Σ El B 1 - vef(x!"))
4
1=
t=0
5(1 - 31)
5T(T
1)31
+ 2(T - 11)
Kr-2
Σ
[I| V Vel (I ve((x(()))
5g
52
1=0
4 +
de
Kr-1
+
1
31
R1 [ 11 + 37
t=
which implies
Σ t=
1E M (1) vef(x(0))11
5(1 - (1)
+ 3T(T-1)
2(T 1)
Kr-2
E||l (ef(x((+1)) - (0
+
(1 80/4)8.33
(1-6e/4)0-
- (1-6e/4)83 6r/4)81
1 8e/2
4
Kr-1
Krš10²
+
B ((IVes(x(1)))
(92)
1 5
(1-
8//4)78/
/
Summing 92 for f= 1,.., Nr. and applying Assumptions 2 yields 91
Now we are ready to prove the convergence of GaLore with small-batch stochastic gradients under isotropic noise assumptions. Theorem 18 (Convergence of Galore under isotropic noise assumptions): Under Assumptions
16
17 if hyperparameters
128
1
353
35 80,2
3,1
< 1, T
0 17 S min
(93)
3,1
4T,
807.2'
1,2'
32,
GaLore using small-batch stochastic gradients and MSGD with MP converges as
1 Kr-1
16A
32
<
+
(94)
Kr
Kn
35
for any K 2 1, where A = f(x(0)) - inf f(x).
Proof. By Lemma 4 we have
E| V[ (0 < ())) (K
Kr-1
(l( (1) ff(xx
1=0
Kr-1 1
1
L
Σ
E x (++1)) -001)) (0)
(95)
172
7
37

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Applying Lemma
14
(5)
and using 8 yields
Kr-1
16
[1)
4
3T
t=0
2
4 4KT310²
[ (0))
[xx
+
1?
1
20(1
B1)
20T(T - 1)12
8(7-
8(7 - 1)1,2
Kr-1
E B[[|2[(11] (t+1) 10
(96)
112
3
36
331
By 933 we have
6
16
8
1
L 20(1 B,)
20T(T 1)L2
8(T 1
and
max
(97)
4
31
8"
4xp²
3537
36
331
Applying 977 to (96) yields 94
Corollary 19 (Convergence complexity of GaLore under isotropic noise assumptions). Under Assumptions 2 2 25//(3/)) (35) + (2VL)) and we choose
17
if
3/2
2T
31
1+
LA
128
T
35
-1
801,2
80,2
32r 1,2
7 =
4L +
+
35
35
3
GaLore using small-batch stochastic gradients and MSGD with MP converges as
(
LA
LAo²
B f
0
(98)
T
85/2T
8
where A = f(x((0)) - inf (a=) Consequently, the compulation complexity to reach an E-accurate solution such that [V](2)] < is 0
LAo? 87/
LA
+
BULA
Proof. T> + 236/(38) + (256x) )²
(9/0 guarantees T 2 Let = KT where K N and E < If
r r= 0, 998) is direct result of Theorem 18
Ifr
0, applying Theorem 18 to K == K + yields
Kr RT-1
LA 55/2T
LAo2
B B/
|1
T
(0)
=
+
V
57/2
D. Results for sparse subspace optimization
In this section, we illustrate how to transfer the main results of this paper to sparse subspace optimization algorithms. We first present the detailed algorithm formulation, then present the theoretical results corresponding to GaLore/GoLood Although it only requires little effort to transfer results in Gorore/GoLore to sparse subspace optimization, we still include proofs for completeness.
38

---

Subspace Optimization for Large Language Models with Convergence Guarantees
D.I. Algorithm design
While low-rank subspace optimization algorithms like GaLore/GoLore project full-parameter gradient G (mxx)) into low-rank subspaces via projection like P G, sparse subspace optimization algorithms sparse mask S to get S @ G. Specifically, consider the following set
Spm.. = (S [0,1] mM ||||| =
Le., of n matrices contains & ones and (mn k) zeros. Corresponding to the subspace selecting strategy in GaLore, consider Top-k strategy which places the k ones at indices corresponding to G's elements with the & largest absolute values. We also consider a Rand-k strategy which samples the sparse mask matrix S from the uniform distribution on SP SPm., corresponding to GoLore. For convenience, we name the algorithm using Top-k strategy as GaSare (Gradient Sparse projection), and the one using Rand-k strategy as GoSare (Gradient random Sparse projection). 'he concerned sparse subspace descent algorithms are described as Alg.
D.2. Notations and useful lemmas
We assume the model parameters consist of N₁. weight matrices. We use X, E me to denote the f-th weight matrix and æ E _ (vec(X;) ..... vec(XN,)T) to denote the vector collecting all the parameters, Ei' mynge We assume GaSare/GoSare applies sparse mask in Sp to the f-th weight matrix and denote
li mene
min òe, ISESNE
max dz. 15
We define M = -( @ M and i (vec(M)) vvec .T.
While using Alg. 6 with MSGD, holds that
$ (0)
t= 0:
5(0) (11 M
(1-1) + +
kt, d E EEN:
(1 -1- (1-3)) 3 (111) + BiSt l KT + 1EN,1 1Sr<T;
and that
(((+)) x1) 1M use Em, to denote the all-one m x n matrix, i.e.,
E Em,m
gmxn
Lemma 15 (Error of GaSare's projection): Let be the Top-k mask of G E mx"", holds that
h |IG..
Sso - G
1
mn
Proof. Let 91, g2, Umn be elements of G' such that 1g1|
>
1 > ...
Immn
It holds that
S SS G
G
(gk
2x
(0 gx))
1=1
1=
gk
1 1+
k
39

---

Subspace Optimization for Large Language Models with Convergence Guarantees
(1
|G||
where the inequality uses
mm -+
9
Σ i= g..
Lemma 16 (Error of GoSare's projection): Let S ~ U(Spm, it holds for all G E mg that
h
E
Em.ns
(99)
mn
and
B||ls 3 G - G (1
k mn
_ |
(100)
Proof. To prove (99.. it suffices to note that for any element Stg in S, holds that
(mn 1)1/[(mn k))(k - k (mm)!/[(mm k)]A
E[S P(S.. 1]
mm
To prove (100] we have
S
G
E
P[S., = =(1 mn
k |
Isism,
D.3. Non-convergence of GaSare
In this subsection, present the non-convergence result of GaSare, similar to that of GaLore.
Theorem 20 (Non-convergence of GaSare): There exists an objective function f TR IR satisfying Assumptions
stochastic gradient oracle (F', D) satisfying Assumption 3 an initial point ("), constant eo > such that for GaSare with any sparsity level K < meng, subspace changing frequency 5 and any subspace optimizer with arbitrary hyperparameters and any /. 0, it holds that
| fz (1)
Proof. Consider target function f(X) = [pp x X where > 0, X Rexn with n > 1 and = (1,0,..-,0)) ..,0,,...,000 R. holds that
f(X) = LX?
2 0,
thus satisfies Assumption
Since v/(X) = [ppp]] T ④ X, it holds that
[V f(() (pp)) T) e (x Y)lle & L|| -Yle,
thus f satisfies Assumption
Consider the following stochastic gradient oracle:
((X:))=f(X) + Eo tr(QX), and PęWDLÉ 1] = Pę.DDI 11] 0.5,
where ā = (n - 1)/2 and
n
1 n
Vn
+I
2 n +
Q
E Raxn
2n
Vn²
40

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Note that VF ( ( + & it holds for any X Rxx= that
Eg-D VF (X; {) (X)
0²
E Be-D|I [
| 1
i 0²,
n2 (n² 11/2
i=1
thus oracle (F.D) satisfies Assumption 3
Consider the initial point X (0) with X X, where 0 < < 8/L is a scalar. We show that GaSare with the above objective function f, stochastic gradient oracle (F, D), initial point X (0), arbitrary sparsity level 0 < k < n² arbitrary
subspace changing frequency T and arbitrary subspace optimizer p. can only output points X with I
X ) 2 cu
for ED = _2 >
When I, GaSare recomputes the sparse mask matrix iteration t. If ( X, the stochastic gradient given by
G = L(pp)) 1 X + TQ
since LA < o, the Top-k mask S E TR satisfies
vec( (0,0,-. .0. 1,1, ,1 R= (n² (n²-))x k)x
Using this mask matrix, the subspace updates in the following T iterations as
((++ = (t) + Stt) o Σ ( o G
((+Ai) x(10 = X,
,,, for A, = 1,2, ,, Since x >, it holds for all > that x(1) and thus
|V 11 = 22 E0.
D.4. Convergence of deterministic GaSare
In this subsection, we prove the convergence properties of GaSare with deterministic gradients. The results and proofs similar to those of deterministic Galore in Appendix B.3
Lemma 17 (Momentum contraction): In deterministic GaSare using MSGD (Alg. 6 if 31 S term M, has the following contraction properties:
When t = 0, it holds that
| (0)
V.
>1 S S(T- 1)(1 -5311
V Vel(a((+11)) - (es(
2(1 - 5g81) +
| [eef
(101)
T
When t kT, l No, it holds that
| - (ef( - (1 1 (1-4
4 (11((1-)))
8z
31)
-
2(1 52) [if(((( + 5(1 - 31)
(ef(((()) - ve
deβ1
r=0
+(T- - - (6))) Σ
V (e - - V
(102) )

---

Subspace Optimization for Large Language Models with Convergence Guarantees
When l = kr + E N. 1 Irr<T, it holds that
(1--1111110 5t Bi T RIIM (ef(ac(t))) 11:
B
M (1)
(1)))
5(1 31)
B
BIll
2
5r,31
10r31
+ 52
Bll Vet (e((x(brti-)))11 )1
(2
(103)
Proof. For convenience we use E to denote Emenne- When t = 0, we have
|| - -
(0) 112 (s v
-E) O Vef(2 - (1
(1 - v (0)) >1 + 11= -(1 -b5)))]Ve
(104)
where the inequality uses Lemma 13 and Jensen's 's inequality. Applying Lemma to 104 yields (0O
When = kT, k E N we have
[M )1
=1S @ [1 B1) b + 3 G/G Vef( (1)) - - - 5(00 o (z)))()))
(t-1)
= -1Ss @ [11 - (M -ee(2"))) + E
- <|((1 -
5,) (1-
(105)
where the inequality uses Lemma 15 By Young's 's inequality, we have
| (t-1) 1) - (ef(x("))
=I(M, (t-1) - (el( - (ve)(x - ves(a((-1))11
< 8631
| (111 -v + 1+
4
[Vef(z
(106)
4
Applying Lemma 2 and (06) to TOS yields T02).
When kr + +r. N. S T, we have
|M (ef(
= =I[(1 - (i)-)/ (z)( + (S( E) の (.
5(1- B1)1 (e +BillE -s((T) o (
(107)
where the inequality uses Jensen's 's inequality and s(D) = S.t ((t-1) .... (((T) The first term can be similarly upper bounded as (106). For the second term, we have
E
(kr) S
(ef(=(0))
1 +
de
I[
s/(tT)) o (e)(
4
|(E (ih 2 (Ve Vef(
1 ++ dz)
1
de
)
(1
5 +
5
-
(108)
de
42

---

Subspace Optimization for Large Language Models with Convergence Guarantees
where the first inequality uses Young's inequality and the second inequality uses Lemma 13
By Young's inequality, we have
[e (1)
1+
de
(Vves(<00)1
(1+bg) 4 dt
(1
|ee((=!))
)
(109)
Note that & kT + r, we further have
(es(((()) (ef(
V Vel (el((((t)()) Ves Ves(o((
V Ves(z((ktt)) V Ve
(110)
where the inequality uses Cauchy's inequality. Applying 109
110
to 108
yields
E S
(k))
Vef(
dz
(ef(w(())
113
10r
(ef(a((rttt)
(ef(a((rtt-1)))11
(111)
Applying (T06) 111
107
yields 103
Based Lemma 17
can prove the convergence properties of deterministic GaSare similarly the proofs of Lemma Below directly present the final convergence results.
Theorem 10 and Corollary 11
Theorem 21 (Convergence of deterministic GaSare): Under Assumptions if hyperparameters
22
64
1
3837
35 80r2 L2 V
3,1
< 81 <
1,
2
0 <
S min
33
4L
80L
16T
GaSare using deterministic gradients and MSGD (Alg.
converges as
Kr-1
16A
(1) >12
Kr t=0
Kn
for any K 1, where A f(x(0)) inf f(z) T 64/(38) and further choose
31 =1
64
T 3831
80L2
8072
16T
1
4L
+
+
35
35
3
GaSare using deterministic gradients and MSGD (Alg.
converges
LA
[0
= o
T
85/2
Consequently, the computation complexity to reach an e-accurate solution æ such that [f < is
( ++))
D.5. Convergence of large-batch GaSare
In this subsection, we present the convergence properties of GaSare with large- batch stochastic gradients. The results and proofs are similar to those of large-batch Gal Appendix B.4
43

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Lemma 18 (Momentum contraction): Under Assumption in large-batch GaSare using MSGD (Alg- 6 if0 81 1
term M has the following contraction properties:
When t = 0, it holds that
E| M 00)
Vef(
22(T 1)(1 - 6r31)
E V V (2lt)))
- vef(
n=0
4(1 -11-801h 4(1--1811)
43107
B V (r) ||
(112)
B
When t kr, A E N", it holds that
(1 1 (1- (1-(1- dt ( 31 BIIM 1-1) - ((-))(
M (1)
(=
4(1 52)
+ 5(1 - 31)
|ill Vis
B (lIVo/((x()) (e
5r81
507
+ + - 1)(1 6τ)
[l - - )1/²]
(113)
B
then = E 5r <. holds that
Vef(x )11 - (1- 56 (1-(1-)) B1
E
M -
E B (1-1) Vef(e((-11) (1]
Vef (0) 112] + 5(1 - B1)
1
E1ll
V ()) - (=f(x((-1)
2
3e,1
15r3
11,h
E
+
83 oz.
(114)
5B
Proof. For convenience we use E denote Emg.ne- When have
| (x)
1 (0) : G ())(2
(S Q G - (G vef(z(0)) - -(1 (1- 31) fz (z)
( E) ( G Vef( ) 11 (1- (zz
(115)
where the inequality uses Jensen's inequality. For the first we have
" E) o
ves(x ||>
<2E|| (00) G 12 2B|| (0) vef(= ()))|
52(1 - 6.) G |
2E G ())
vef(z
M| + (4 )
( 6
(116)
where the first inequality uses Cauchy's inequality, the second inequality uses Lemma [5] the third inequality uses E||G (0) (z) || < / (Assumption
3). Applying (116) and Lemma to 115 yields (122).
When kT, E N we have
B M (0
44

---

Subspace Optimization for Large Language Models with Convergence Guarantees
= ② [11 11-1113100000000 3,), B.G Ve](a[()] - (E- (E-S 5/9) Vel(a("))
~ 0 , M B
Vef(x + ) o )ef(
(117)
We further have
B||s| - BI) (-11 + G - ves(a(
<BIl M 1- 3,G )
-B[I[(1 (- " Vef(x
31 -
<T[I[(1 3)M( - Ves(x -Vi((a"
&E - vef(2"))
(118)
where the last inequality uses the unbiasedness of G (Assumption 3 By Young's inequality, we have
M (1-1) v=f( [1:1
= [ (1-1)
Ves(ar(t-))) (VeS(z!1)) - (es(a((-))
$ 1+ +
8281
M 11 (I+
4
E ((((((() - (ef(a(t-)))
(119)
4
5r
Applying (199) to 118) yields
Elll E|llst @ [[1 - M + 3/ - Vef(<("))]1
1 - (1
_
5z
31
Elll M! (t-1) - vef(x((-1))
370²
4
B
5(1 31)
E (z)(x)()) - )(
(120)
5e
For the second term in 117 we have
E[I(E 1 2 (ef(x())1
<2E[I[E - 5 G || + 2E| ((0) o ( - ve[(a!))))
52(1 - 6 || + 2E G!! (ef (t) |1
40²
22 - 6.)
|1 +
(121)
B
where the first inequality uses Cauchy's inequality, the second inequality uses Lemma 15] the third inequality uses Assumption 3 Applying (120) (1I) to (177) and using Lemma yields (113).
When t= kr tr N. 1 S < we have
M (1) )1:
=ElIl(1 (M (1-1) vef(x(()) + & o O
(
(ef(2(())) )1
=E]I((1 - (M) (1-1) vef(z())) )) + ((S E) O Vef ||
+ ! @ (G
vef(a!")))
<(1 3:) (1)
ves(a(()))
((0) 3 (1))
+ { о (G
(122)
where the second equality uses the unbiasedness of G and the independence implied by 0 = s(t-1) the inequality uses Jensen's 's inequality. The first term is similarly bounded as (T19). For the second term, we have
E|]((E -((tt) @ Vef( (1) 12:
45

---

Subspace Optimization for Large Language Models with Convergence Guarantees
dg 4
Ell( E -
3 G (k)) [|:]
+
Bill E 5 (
3 (Ves(x!()) - -G )
+
1 +
5z
38
4
G (kT)
|1:11 + 2
1+
BlIG (1
4
5z
+
2
1 +
E (
Vz)(
(123)
where the first inequality uses Young's inequality, the second inequality uses Lemma 15 have
and Cauchy's inequality. We further
36g
B| AT)
11 + 2
1+ 5z
E BilG (|]
Vef(x ||
4
36;
B[IVes[(a (kT) |1 + Bll ( - (1a
11
4
38,
B||l BIIVes( (K (1)) + 1oo2
4
5.8
11o7
||2:1 + 1 8z
[(I - (=((ar((T))
(ar(
(124)
2
5,
where the first inequality uses unbiasedness of G(lT), the second inequality uses Assumption 3 the third inequality uses Young's 's inequality.
Applying 124) to
123 and applying Cauchy's 's inequality yields
B|ll E ((()) o (=f(=(0))
de
11o7
15r
s 1 (1-2)
E (<
+
Ves (x((t(ttt)
(125)
8
82
For the third term, we have
E [|||st
(r) @ (G
< ((f(< \1al S So
vef(z()))
(126)
where the second inequality uses Assumption
Applying (119)
125
126
to (12 yields 114
we can prove the convergence properties of latge-batch GaSare similarly as the proofs of Lemma Theorem 12 and Corollary [3 Below directly present the final convergence results.
Based on Lemma 18
Theorem 22 (Convergence of large-batch GaSare): Under Assumptions
if hyperparameters
128
1
3537
5 40
3
31
<
33,
17
min
4L
80..
32
GaSare using large-batch stochastic gradients and MSGD (Alg.
6
converges as
Kr-1
16A
160
352
32
E
+
+
o²
KnkT
36
35
t=0
for any K3 2 1, where A = ()) inf f(z). IfT 2 2+ + 256/(30) + (256a) ( (2/99////))
and we further choose
3/2 02/ 2T
B1
1+
LA
46

---

Subspace Optimization for Large Language Models with Convergence Guarantees
128
3631
-1
801,2
40T21,2
32r
1,2
17
4L +
35.31
+
6
+
V
3,31
B
031
GaSare using large-batch stochastic gradients and MSGD (Alg.
6
converges
T-1
LA
LAo2
T
B
f (1
>121
=
85/2T
87/2T
Consequently, the computation complexity reach e-accurate solution æ such that | [=))] is given by
O LAg?
LA
+
LI
D.6. Convergence of GoSare
In this subsection, present the convergence properties of GoSare with small-batch stochastic gradients. The results and proofs are similar to those of GoLore in Appendix B.5
Lemma 19 (Momentum contraction): Under Assumption in GoSare using MSGD (Alg- 6 0 < 31 S term M, has the following contraction properties:
When / = 0, it holds that
M (0)
Vef(X
1 S(T - 1)(1 -523))
Σ E V Vef( Vef(a(")))
+ 2(1 -
EI
||3] 683908
(127)
T
When t = kr, h: E No, it holds that
(()) 86 (1- (1 (1-111
E M (t)
31 EIlM! - (e)()
4
2(1 5t)
5(1 - B1)
Σ
[1|| ( (kT+ |1
E (ef((x))) - (t-
31
r=0
(T- 1)(1 - 5e)
E V [[]Ve((((((*
Vel(
(128)
When t = kr r, h: E N. 1 5 7, it holds that
V. |1 - (1 (1- (1 (1- de
E
MM
B1 Ell EIIM!!-) (es(x((--1)) (t1)
4
B (1)) 5(1 - 31) (el( - (t
B
2
3e,11
10r31
(ef(z(( (((+
+ +3.03.
(129)
Proof. For convenience we E denote Emggne- When have
M|
E
(2)))
47

---

Subspace Optimization for Large Language Models with Convergence Guarantees
=
(=)(2())) Vef(x (
s E
|1 + s o
(G. vef(x!")))|
(130)
where the second equality uses unbiascdness of C By Lemma we have
S (0)
E O (ef(
E
[[ 1is Vef (1)
(0)
ISiSmilSiSm
E 23 vo
IsiSm.usis
<(1 Ve
(131)
Similarly, by Lemma we have
E (0) (G) (0) - (=)()())))
Σ H vef( ())
=
ISiSm
V v=f(2(0))
<5007
(132)
where the inequality uses Assumption 3
Applying
131
132 and Lemma to (10 yields 127
When kT, ls E No we have
E M (+)
=||| 8 @ [11 (
(t)
(1-1) + G
Ves(x(()) - (E (( v=s(
611111(11 3 (
(1-1)
+3 ( (1)
(133)
where the second equality uses Lemma
16 For the first term, we have
E (1 M,) + BIG - vef(a(()))
[I] - 3:)(M - ve((z(()) - 3: (G - ve)( [i:]]
<][][( - ())((((1)) - Vef( + SEI| (ef(x
<(1 BI) (( Ves(x(")) S,02
(134)
where both inequalities use Assumption 3
By Young's inequality, we have
El|l E|IM (1-1) (=f(2(())) [
-F(I((M (t-1) (=((((((-1))) (ve((x!)) - (=
1+ deB31 B (1-1) (ef(x((t1))11 1
4
E (((()((
(e 1|1.)
(135)
Applying (134 135) and Lemma to 135 yields 128
When ( < < T, we have
M - (ef(
=Bil[(1 -3)( ))
+ ((( o o
(0)(2
=
(0((1-38)10 -B)(()("") (v)((a())) (1( E) (=) ||
48

---

Subspace Optimization for Large Language Models with Convergence Guarantees
+ ( @ (G ves(a!"))
BI 5(1 (1-33))Bll M (11) - - vef(a("))
+ ! @ (c) vef(=("))
(136)
where the second equality uses the unbiasedness of @ and the independence implied by s = s((-1) the inequality uses Jensen's 's inequality. The first term is similarly bounded as (135). For the second term, we have
E E
S kkk
@ V fx)
1
B E (k)))
& (kr)))
4
B[I[(E s(AT)) o (Ve((x(")) - Ves(((
+ 1 +
bt
3dt 4
B| V
(zz || + 1
4 55
B {
e (kr) [P]]
(137)
where the first inequality uses Young's inequality, the second inequality uses Lemma 16 By Young's ss inequality, we have
&
(1+ 4 5/²
||| V (kT)
|| - 1
E BII |1=) +
B[IVes((x())
vef(z )|
(138)
Applying (188
137
and applying Cauchy's inequality yields
|||| E E
S (((T)) C vef(x("))
de
E (<)
10r
Ell (e Vel(x((rti-11)))
(139)
52
For the third term, we have
E|||s((T) o (G
-
sE|I
Vef( S oo
(140)
where the second inequality uses Assumption
Applying 135
139
140)
to (36) yields 129
Based on Lemma
19
we can prove the convergence properties of GoSare similarly as the proof's of Lemma Below we directly present the final convergence results.
Theorem
4
and Corollary
15
Theorem 23 (Convergence of GoSare): Under Assumptions
3 if hyperparameters
64
f 1
3837 800
35
3
0 81 <
7
0 17
min
3
4L
80,2
16
GoSare using small-batch stochastic gradients and MSGD (Alg.
6
converges as
1 Kr-1
16A
323,0²
E
(1)
+
Kr
Kn
35
for any K 2 1, where A = f(x(0)) inf ve f(x). IfT 2 2 128/ (35) + (128a) and we further choose
3/2 83/2 2T
3
1
LA
64
353
49

---

Subspace Optimization for Large Language Models with Convergence Guarantees
80L2
80
16r
4L +
+
3681
3Ø
3
GoSare using small-batch stochastic gradients and MSGD (Alg. converges as
T-1
B
=0
(1) M1
=
LA
LAo²
T
85/2T
/
Consequently, the computation complexity to reach an e-accurate solution æ such that f=)) S E is given by O LAo"
LA 8972g
+ 8172A + + +
E. Experimental specifications
In this section, we elaborate on the missing details concerned with the experiments we present in Sec. 6
Galoree' non-convergence. compared Galore, large-batch Gal.ore, GoLore and full-parameter training on the constructed quadratic problem defined in T We used a batch size of 128 for large-batch GaLore and batch size of for the others.
Pre-training tasks on C4 dataset. We pre-trained LLaMA-60M on C4 dataset for 30,000 iterations on 4 NVIDIA A100 40G GPUs. We use batch size 128, learning rate 1.0e-3, rank 128, scaling factor = 1, subspace changing frequency 200, and a max sequence length of 256.
Fine-tuning tasks on WinoGrande dataset. We fine-tune pre-trained LLaMA2-7B model on the WinoGrande dataset for 30 epochs on 4 NVIDIA A A100 80G GPUs. We use batch size 1, rank 1024, subspaces changing frequency 7 500 and max sequence length of 2048. The learning rate and scaling factor set as 1. 1.0e-4 and for GalLor//GoLLor thus corresponds to a learning rate of 4.0c-4 in full-put nallmparrmeter fine-tuning, The test accuracy is presented in Table 4 where GoLore performs similarly to GaLore due to overfitting.
Fine-tuning tasks on BoolQ dataset. We fine-tune pre-trained LLaMA2-7B model on the BoolQ dataset on 4 NVIDIA A100 80G GPUs. We use batch size 1, rank 1024, subspaces changing frequency す = 500 and a max sequence length of 2048. We use MSGD as the subspace optimizer, where the learning rate and scaling factor are set as 1.0e-4 and a = 4 for Gorere/GoLore, corresponding to a learning rate of 4.0c-4 in full-parameter fine-tunie fine-tuning. Table Table4present presents the test accuracy of different algorithms, where GoLore outperforms Galore. We further fine-tune pre-trained OPT-13B for epoch using the same experimental setup, whose results are shown in Table 2
Table Evaluating Gal.ore/Gol.no Lore for fine-tuning on WinoGrande and BoolQ using pre-trained I.aMA2-7B.
Algorithm
BoolQ (1 epoch)
BoolQ (3 epochs)
WinoGrande (80 epochs)
Full Params.
86.48
87.43
69.85
GaLore 85.81
84.89
86.79
68.51
GoLore@ 20%
86.88
68.51
Fine-tuning tasks on GLUE benchmark. We fine-tune pre-trained RoBERTa-Base Base model on the GLUE benchmark for 30 epochs on a single GeForce RTX 4090. Training details including batch size, learning rate, rank, scaling factor a and max sequence length are illustrated Table
F. Ablation studies
In this section, we conduct several ablation studies to provide a deeper understanding of the proposed GoLore algorithm.
Ablation on the switching point. By switching point, we mean the ratio of GaLore to GoLore during training; for instance, @50 indicates a switching point of 0.5. our experiments, we choose an earlier switching point we expect the algorithm to converge more quickly to the solution's 's neighborhood and a later one we anticipate slower convergence. To provide a broader guideline, we offer the following insights:
50

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Table 5. Hyperparameters used in fine-tuning pre-trained RoBERTa-Base model the GLUE henchmark.
Hyperparameter
CoLA
STS-B
MRPC
RTE
SST2
MNLI
QNLI
QQP
batch size
32
16
16
16
16
16
16
16
Learning Rate
2.5e-5
2.0e-5
3.5e-5
7.0e-6
1.0e-5
1.0e-5
1.0e-5
1.0e-5
Rank
4
GaLore's
4
4
4
FLORA'S
4
4
4
4
4
4
4
GoLore's
4
4
4
4
4
4
4
4
Frequency
500
500
500
500
500
500
500
500
Max Seq. Len.
512
512
512
512
512
512
512
512
Ablation on Switching point
Ablation on Frequency
92.8
F1-Score
F1-ScoP
92.6
96
92.4
94
0.0
0.2
0.4
0.6
0.8
50
100
200
500
1000
GoLore ratio
Frequency T
Figure 10. Ablation results on the switching point. We report the Fi-scores of fine-tuning the MRPC task in the GLUE benchmark with different GoLore ratios. A GoLore ratio of represents GaLore.
Figure 11. Ablation results on the subspace update frequency. We report the Fi-scores of fine-tuning on the MRPC task in GLUE benchmark with Gorore@00 20%% with different subspace update frequency r's.
If access to the true gradient is available, a reasonable switching point would be when gradient noise begins to dominate the true gradient.
If only stochastic gradients are available, and assuming the gradient noise has a roughly constant scale, this dominance can be estimated by monitoring whether the norm the stochastic gradients falls below certain threshold. This threshold serves hyperparameter that depends on both the training task and the batch size used in the algorithm.
The optimal switching point is task-dependent. Empirically, it is recommended switch when the rate of decrease in the loss curve starts to slow down.
Fig. 10 shows model performance across different switching points. Except for pure GaLore (switching point 0), GoLore achieves comparable performance at all other points.
Ablation on subspace update frequency. Consistent with Zhao et al. 2024), which reports stable performance for GaLore across 7 E [50, 1000), Fig. shows that GoLore 20% exhibits similar robustness to different 7 values in the same range.
Ablation on subspace sampling strategy. An important question is whether alternative non-greedy sampling strategies outperform GoLore. To explore this, we evaluate importance sampling- based method. Given stochastic gradient matrix G E m (m < n),, we first perform SVD to obtain G UEV following the procedure used in Gore However, instead of selecting the top-r columns of U as in GaLore, we sample columns with probabilities proportional to the corresponding singular values o,, As shown in Fig. 12 this sampling- bampling-based strategy achieves performance similar to GaLore, but is consistently outperformed by GoLore. This may be attributed to the fact that importance sampling does not yield unbiased projection matrices and remains susceptible to the bias introduced by stochastic gradient noise.
51

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Pre-training LLaMA-350M on C4
40
GaLore
38
GoLore@40%
I.S.@40%
Perplexitt
prppexity
34
Adam@40%
32
24.5
30
24.0
28
23.5
17.5
20
22.5
25
24
22
5.0
10.0
15.0
20.0
25.0
Iterations(x1000)
Figure 12. Additional results of pre-training LLaMA-350M on C4 dataset. "I.S." represents the alternative importance sampling strategy.
Gradient Error Norms
Gradient Error Norms
3.00
120
2.75
110
2.25
GoL 0ree%0%%%
Norm
GaLore
2.00
GaLore
GoLore@500%
80
1.50
70
1.25
60
1.00
250
500
750
1000
1250
1500
1750
2000
250
300
350
400
Iterations
Iterations
Figure 13. Illustration of gradient error norms when training the quadratic target problem with GaLore and GoLore @ 75% corresponding to Fig. (right).
Figure 14. Illustration of gradient error norms when fine- tuning with GaLore and GoLore@50% the MRPC task. Only 32 sequences are used for cheap truc- true-gradient evaluation.
Does GoLore's projection truly result in smaller compression errors? To assess whether GoLore achieves lower compression еттоr than GaLore due to its randomized projection strategy, we report the gradient approximation errоr (z) (xx(()) l2 in Fig 13 and Fig 14 where (z) denotes the approximated stochastic gradient computed using GaLore or GoLore. As shown, GoLore consistently produces more accurate gradient approximations than GaLore across training steps.
52

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm& Gal.re using large-batch stochastic gradients and MSGD with MP
Input: Initial point (0), data distribution D, learning rate 77, subspace changing frequency т, rank Nr momentum parameter 31, large batch size B.
Output: (x(())
Initialize optimizer state (M(-U) ( Nr. Mt=1 to zero;
for = 0, 1,... 1 do
if' t = 0 (mod then
Sample (c(1,)) 1==1
Lid. D;
else
Sample g(t) D: end if
for
1,2, , .n do
/ 0 (mod r) then
G/-) 2 ΣE g((tt))
U, V SVD(G)
if me < ne then
p(d + Ul: ri];
( + (1 101-30 (P)((P)))) ( (pp(pp10 p(--1) + )
X x((1)) x( - M
(t)
else
Q00) t Tel:
M (t) t (1 M (1) (t TQ + G +
x ((++) t x( M
(1) (Q [T)
end if
else
G {((()())(())
if mg < ne then
pl < p!t-!!
M (1) (1-3,)M; (t-1) (
x(+1) + x P ( (
else
((0) t Q (t-1),
M( (1 M &
x (1+1) < x (t) 11,, (Q!))
end if
end if
end for
end for
53

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm 5 GoLore using small-batch stochastic gradients and MSGD with MP
Input: Initial point (0) data distribution D, learning rate 1/, subspace changing frequency т, rank {re M momentum parameter 31.
Output: [o)
Initialize optimizer state (M/-1) No, T==1
to zero;
for t = 0, 11..... 1,, - do
Sample (1)) ~ D;
G( (z(( (()): for = 2, .Nr. do
if t = 0 (mod r) then me S ne then
Sample p(t) (Stmaree)
M (1)
(1 - (P)( ple ( ( T.
X (1))) - x (t) p (t) (
else
Sample @ ~ (St...rr)
M (8)
(1 31 M (1-1) QQ
(t- T ,
X (+1) X (t) nM (Q )T:
end if
else
if
me ne then
p(t) + p(t-1) 11
M (t) + (1 - (1-1) + (P())
((+1) t (( - PnPt M (t)
else
Q0 t Q( (t-l);
M (t) f (1 31) M
(t-1) + 3,G. Q."
(++1) < x { TM (Q( (
end if
end if
end for
end for
54

---

Subspace Optimization for Large Language Models with Convergence Guarantees
Algorithm 6 GaSare
GoSare algorithms using stochastic
deterministic
large-batch
gradients
Input:
Initial point (0)), data distribution D, learning rate 1), subspace changing frequency т, rank {re optimizer hyperparameters $1. $2, c, large batch size B.
Output: (o("))/=0
Initialize optimizer state {M for t = 0, ..., T do for 1,2, N₂ do
N Je and (V2 (V(--)) J to zero;
if (mod r) then
+ g((()())(0)) (stochastic)
G vef(=!))) (deterministic)
G + D vrF(x(() (large-batch)
1/0 Top: ) (GaSare)
Sample s u(Sp (GoSare)
else
veF(x(()g(0)) (stochastic)
G v)f(x(())) (deterministic)
G ; (large-batch)
0 s(--))
end if
R o(1) (
M + (1- (1- @ ( + R,
v( (1- B2)s(0) v (t-1) + R
if using Adam then
M (1) t ( /
-(1-)) H), v + 1
/(1 -3), N² t -, /// /(V v.(0 +e);
else if using MSGD then
NO0 + M 19
end if
x (++))
x - (( (()))
end for
end for
55


Reviews:
[{"review_id": "97g4CNjZWQ", "reviewer": "Reviewer_iLWQ", "summary": "The paper shows that the subspace projection of Galore can be biased when approaching to local minimizer, where the principle component of the projection matrix mainly capture the information of the stochastic noises. Built upon this insight, the paper proposes a method named Golore, which samples the projection matrix from stiefel manifold for ensuring the unbiasness of the gradient when the training is about to converge, i.e. close to local minimizer.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our theoretical results and experimental designs, as well as the detailed comments and suggestions. All questions have been clarified as best as we can, and we are glad to address any further comments or questions. We include all new experiments in this **[anonymous link](https://www.hostize.com/v/pcWmN50BVa)**.\n    \n- **Weakness 1. The paper does not provide a guideline on how to choose the switching point.**\n    \n    We appreciate the reviewer’s valuable feedback. In our experiments, we manually selected the switching points from $\\\\{20\\\\%,30\\\\%,40\\\\%,50\\\\%\\\\}$ based on intuition and prior experience. Specifically, we choose an earlier switching point if we expect the algorithm to converge more quickly to the solution's neighborhood and a later one if we anticipate slower convergence. To provide a broader guideline, we offer the following insights:\n\n    - If access to the true gradient is available, a reasonable switching point would be when gradient noise begins to dominate the true gradient.\n\n    - If only stochastic gradients are available, and assuming the gradient noise has a roughly constant scale, this dominance can be estimated by monitoring whether the norm of the stochastic gradients falls below a certain threshold. This threshold serves as a hyperparameter that depends on both the training task and the batch size used in the algorithm.\n\n    - The optimal switching point is task-dependent. Empirically, it is recommended to switch when the rate of decrease in the loss curve starts to slow down. \n        \n- **Weakness 2. The ablation study on the subspace update frequency is missing.**\n    \n    We appreciate the reviewer’s suggestion. We did not initially include an ablation study on the subspace update frequency $\\tau$ because the original GaLore paper (Zhao et al., 2024) states that values of $\\tau$ between 50 and 1000 have minimal impact on performance. Based on this, we set $\\tau=500$ to:\n    - Reduce computational overhead, and\n    - Ensure a sufficient number of GoLore projection steps to enhance performance.\n    \n    However, in response to the reviewer's concern, we have provided additional ablation results in Figure 3 in the anonymous link. These results confirm that varying $\\tau$ within the range of 50 to 1000 has negligible effect on performance.\n    \n- **Suggestion 1. It may be informative to plot the norm of gradient bias of both Galore and Golore.**\n    \n   We appreciate the reviewer’s valuable suggestion. In response, Figures 4 and 5 in the anonymous link have additionally plotted the gradient bias norms in our experiments, demonstrating that GoLore achieves a smaller gradient bias.\n    \nWe thank the reviewer again for the careful comments. We hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.", "claims_and_evidence": "Yes. The claims are supported by the proof and numerical results.", "methods_and_evaluation_criteria": "Yes, the C4 pretraining task and GLUE finetuning task are standard benchmarks for evaluating memory-efficient optimization algorithms.", "theoretical_claims": "I have not went through all the proofs, but I am farmiliar with the related techniques. The theorem make sense under the given assumptions.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper explains why Galore can be much slower than Adam in the late training stage from gradient bias perspective. Both theoretical researcher and practioners may find insight from this paper.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths**\n\n* The paper reveals that Galore's slow convergence in the late training stage is due to that priciple components are dominated by the stochastic noise. The results are justified by (non)-convergence results.\n\n* The proposed strategy for avoiding biasness is relatively easy to implement. Experiments on LLM's pre-training demonstrates that adding Golore phase exhibits faster convergence than running Galore alone.\n\n**Weaknesses**\n\n* The choice of switching point to Golore may have huge impact on the convergence. However, the paper does not provide guideline on how to choose this hyperparameter. The ablation study on the subspace update frequency $\\tau$ is missing as well.", "other_comments_or_suggestions": "It may be informative to plot the norm of gradient bias of both Galore and Golore (may be conducted under a relatively small dataset for cheap evaluation of full gradient).", "questions_for_authors": "N/A", "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": "MxJ8cZhUTM", "reviewer": "Reviewer_Eita", "summary": "This paper examines the convergence properties of subspace optimization algorithms for LLM, focusing on GaLore. GaLore is known for memory efficiency in pre-training and fine-tuning LLM, this paper shows that it does not always converge under standard stochastic optimization settings. The authors substantiate this claim with a counterexample and explore conditions for its convergence, such as large mini-batch sizes or deterministic gradients. To address the limitations of GaLore, the paper introduces a new algorithm called GoLore (Gradient random Low-rank projection). Unlike GaLore's SVD-based projections, GoLore uses random projections, enabling convergence even with small mini-batches in stochastic settings. Theoretical analysis demonstrates GoLore's superior convergence properties under general conditions.\n\n## Update after Rebuttal\nAs mentioned earlier, I maintained a positive score, and I hope the next revision will incorporate the discussed changes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our theoretical results and appreciate the efforts made to check our convergence proofs. All questions have been clarified as best as we can, and we are glad to address any further comments or questions. We include all new experiments in this **[anonymous link](https://www.hostize.com/v/pcWmN50BVa)**.\n    \n**Weakness 1. The dependence of the assumptions may limit broader applicability. In a noisy setup, a random projection may add more uncertainty in the final claims.**\n    \nWe respectfully disagree with the reviewer’s concern that GoLore's broader applicability is limited by the dependence on assumptions, particularly regarding the noise scale. While introducing random projection may add more uncertainty, we argue that such randomness is, in fact, essential to mitigate the impact of gradient noise in noisy settings.\n\nTo see it, we first consider the deterministic projection used by GaLore. Let $G=G_0+E$ represent the stochastic gradient, where $G_0$ is the true gradient and $E$ is the gradient noise. In noisy settings where $\\\\|E\\\\|\\gg\\\\|G_0\\\\|$, GaLore deterministically select the projection matrix $P$ using the information of $G\\approx E$. The noisier $E$ is, the noisier $P$ becomes. Moreover, GaLore's Top-K selection can degrade the unbiasedness of $E$, potentially leading to non-convergence.\n\nIn contrast, GoLore randomly samples $P$ from the same distribution, regardless of how noisy $E$ is. This approach shields $P$ from being influenced by the dominant gradient noise, ensuring its stability regardless of the noise level in $E$. Furthermore, GoLore's random projection maintains the unbiasedness in subspace selection, as shown by $\\mathbb{E}[PP^\\top]=\\frac{r}{m}\\cdot I$ in Lemma 5.\n\nAdditionally, the assumptions regarding gradient noise in our analysis are standard in stochastic optimization and are widely accepted in convergence studies. Therefore, we believe that our theoretical results are not unduly restricted by these assumptions and that random projection enhances the algorithm’s robustness in noisy settings.\n    \n**Question 1. Can a sampling based row rank approximation be used instead of random projection of GoLore or singular value decomposition of GaLore?**\n    \nThank you for the interesting question. To explore this, we have additionally evaluated the performance of a sampling-based method as follows:\n    \nLet $G\\in\\mathbb{R}^{m\\times n}\\ (m\\le n)$ be the stochastic gradient matrix. Similar to GaLore, we first compute SVD of $G$, obtaining $G=U\\Sigma V^\\top$. However, instead of selecting the first $r$ columns of $U$ as GaLore does, we  sample $r$ columns with probabilities proportional to the corresponding singular values $\\sigma_i$'s. As shown in Figure 1 in our anonymous link, the performance of this sampling-based strategy is similar to that of GaLore's, outperformed by our GoLore method. This is potentially because such an importance sampling strategy cannot lead to unbiased projection matrices, and still suffer from the bias induced by gradient noise.\n    \nWe thank the reviewer again for the careful comments and valuable suggestions. We hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.", "claims_and_evidence": "The claims in the paper regarding the non-convergence of GaLore and the convergence guarantees of GoLore is supported by a combination of theoretical analysis, illustrative counterexamples and empirical evaluation.", "methods_and_evaluation_criteria": "Yes it does.", "theoretical_claims": "I checked a few convergence theorems, such as theorem 10. 12 and 18, they look fine.", "experimental_designs_or_analyses": "The author provides a counter example for convergence guarantee, and they validate this with experiments in Figure 1.", "relation_to_broader_scientific_literature": "The paper addresses the issue of memory efficient training for LLM along with their guaranteed convergence.", "essential_references_not_discussed": "References seems to be well cited", "other_strengths_and_weaknesses": "Positives: The paper supports their claim with rigorous theoretical analysis. The paper is well presented. \n\nNegatives: The dependence of the assumptions may limit broader applicability. In a noisy setup, a random projection may add more uncertainty in the final claims.", "other_comments_or_suggestions": "As mentioned before that paper has been well presented and there are no major typos or inconsistencies there.", "questions_for_authors": "Can a sampling based row rank approximation be used instead of random projection of GOLORE or singular value decomposition of GALORE?", "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": "IDkqpgoYLt", "reviewer": "Reviewer_ZeQP", "summary": "The paper critically examines GaLore, highlighting its convergence limitations and proposing GoLore, a robust variant that ensures stochastic convergence. The findings contribute to improving memory-efficient subspace optimization methods for LLM training.\n\n## update after rebuttal\nMy concerns were addressed in the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our theoretical findings and for the valuable comments. All questions have been clarified as best as we can, and we are glad to address any further comments or questions. We include all new experiments in this **[anonymous link](https://www.hostize.com/v/pcWmN50BVa)**.\n    \n**Weakness 1. GaLore is mainly developed for (pre-)training, current experiments only considering fine-tuning are not enough.**\n    \nWe would like to respectfully remind the reviewer that we have already included a pre-training result in Figure 4, where the algorithms are applied to pre-train a LLaMA-60M model on the C4 dataset for 30K iterations. To further address this concern, we have conducted additional experiments on pre-training LLaMA-350M models, with results provided in the anonymous link (Figure 1). These results show that transitioning from GaLore to GoLore leads to a faster decrease in the loss curve, further demonstrating the effectiveness of GoLore in pre-training tasks.\n    \n**Weakness 2. The improvement in the fine-tuning task is minor.**\n    \nWe respectfully disagree with the reviewer’s assessment. Notably, in the GLUE benchmark, our method achieves an average score of **86.03**, compared to GaLore’s **85.77**. This represents a **threefold reduction** in the performance gap between GaLore and AdamW (86.15). We believe this result highlights the effectiveness of our method, demonstrating that a simple modification can significantly close the performance gap.\n    \n**Weakness 3. The proposed algorithm still relies on GaLore in the initial stage in the practical implementation.**\n    \nOur hybrid strategy, which relies on GaLore in the initial stage, aligns with our theoretical insights. The limitation of GaLore arises when anisotropic gradient noise starts to dominate the true gradient, which typically occurs **in the later stages of training**. In the early stage, when true gradients are dominant, GaLore’s greedy strategy remains effective, and no modification is necessary.\n    \nEmpirically, applying GoLore from the very beginning (i.e., GoLore@100%) results in performance similar to that of GaLore, likely due to a slower initial phase. Therefore, we believe the hybrid strategy is preferable, as it ensures both a fast initial convergence and higher accuracy in the later stages.\n    \n**Question 1. It would be better to include important parameters and discussion on these parameters in the main text.**\n    \nThe primary hyperparameter introduced beyond GaLore is the **switching point**, where we transition to GoLore. We kindly refer the reviewer to our rebuttal to **Reviewer iLWQ (Weakness 1 and 2)** for a detailed discussion, as well as to the **anonymous link (Figure 2 and 3)** for ablation results.\n    \n**Question 2. It seems that the analysis didn't consider momentum and Adam cases. It would be better to clarify this.**\n\nWe kindly remind the reviewer that GoLore's **convergence analysis** is based on **momentum SGD**, which explicitly accounts for momentum. Additionally, in our **non-convergence analysis**, Theorem 4 holds for **any optimizer $\\rho$**, including Adam, AdamW, and momentum SGD.\n\nHowever, we acknowledge that whether GoLore **converges under Adam** remains an open question. To clarify this, we will revise the conclusion section as follows:\n    \n>**Original:** A limitation of this paper is that recent GaLore variants, such as Fira, are not readily covered by our analysis framework.\n    \n>**Revised:** A limitation of this paper is that our convergence analysis framework has not readily covered the use of the Adam optimizer and recent GaLore variants such as Fira.\n\n**Question 3. In your counter example and proof, can we reduce the stationary gap via reducing the step size? Is it an issue faced by all stochastic algorithms?**\n\nWe cannot reduce the gap by decreasing step size. As demonstrated in **Theorem 4**, the non-convergence result holds for **any optimizer $\\rho$**, regardless of the algorithm framework or hyperparameters, including the step size. Therefore, the counterexample illustrates an issue that is inherent to **all stochastic algorithms**.\n\n**Question 4. If your claim that SVD decomposition biases the gradient holds, why does the deterministic GaLore converge (Theorem 5)?**\n\nIt may be more accurate to say that GaLore's greedy SVD projection biases the **stochastic gradient**, including the **gradient noise**. Intuitively, the bias introduced by gradient noise will not vanish as the gradient noise itself will not vanish.\n\nOn the other hand, the bias in the **true gradient** can be bounded, as shown in **Lemma 1**, and this bias vanishes as the true gradient approaches zero. This is why GaLore can still converge in the deterministic case, despite the bias in the gradient.\n\nWe hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.", "claims_and_evidence": "The authors claimed GaLore's limitation and provided theoretical justification.", "methods_and_evaluation_criteria": "The experiments mainly focus on fine-tuning the GLUE benchmark using pre-trained RoBERTa-Base. In the appendix, they also considers fine-tuning LLaMa 2-7B.", "theoretical_claims": "First, the authors argue that GaLore suffers from convergence issues under general conditions and provide theoretical evidence. Subsequently, they proved GaLore's convergence when the batch size increases in the order of $\\sqrt{T}$. Finally, they proposed their own algorithm, GoLore.", "experimental_designs_or_analyses": "I think the experiment is not enough. The improvement is minor.", "relation_to_broader_scientific_literature": "They show GaLore's limitation in theory, which is interesting to me.", "essential_references_not_discussed": "Reference is good.", "other_strengths_and_weaknesses": "Weakness:\n\nFrom my perspective, GaLore is mainly developed for the training of LLM. The current experiments only consider the fine-tuning, which may not be enough to support the effectiveness of this algorithm. \n\nIn the fine-tuning task, the improvement is minor, which weakens the contribution of this work.\n\nThe proposed algorithm still relies on GaLore in the initial stage in the practical implementation as mentioned by the authors. \n\nStrengths: \n\nThis paper proposed an algorithm for LLM training with convergence guarantee, which enjoys better theoretical properties.", "other_comments_or_suggestions": "No", "questions_for_authors": "It would be better to include important parameters and discussion on these parameters in the main text. \n\nIn your analysis, it seems that you didn't consider momentum and Adam cases. It would be better to clarify this.\n\nIn the conventional SGD algorithm, it relies on diminishing step size to eliminate the stationary gap. In your counter example and proof, can we reduce the stationary gap via reducing the step size? Is it an issue faced by all stochastic algorithms?\n\nIf your claim that SVD decomposition biases the gradient holds, why does the deterministic GaLore converge (Theorem 5)?", "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:

Meta-review: The paper studies the convergence of GaLore close to the local minima. The key insight is that at these later stages (closer to the local minima) the noise dominates and as a result GaLore may not converge, leading to poor performance. Based on this insight, the paper proposes a randomized projection strategy at the later stages. 

**Strengths**: While the gains are modest, this insight is fairly general and interesting and can be used by methods that leverage the low-rank property of the gradient. The paper is overall well-written, and the key insight is corroborated by empirical evaluations. 

**Weakness**: While the reviewers appreciated the theoretical analysis. Some parts can be made clearer to improve readability. For instance, in Thm. 4, the paper can be explicit regarding the significance of $\|\nabla f(\mathbf{x}^{(t)}\| \geq \epsilon_0$. That is, the paper can state that since the gradient does not go to zero, this shows nonconvergence of GaLore. This also goes to the proofs, where providing context for each step can further improve the paper and maximize its impact. 

The AC believes that these are minor issues which can be handled while preparing the final version of the paper. As a result, the AC recommends acceptance.
Decision: Accept (poster)