Subspace Optimiztion for Large Language Models with Convergence Guarantees

Question 1. I would like to know the authors' point of view on the following question. GaLore is a practice-oriented approach for memory efficiency of LLM training. The major application of GaLore is clearly a non-smooth optimization problem. That being said, both GoLore and GaLore do not have theoretical guarantees. How would the benefits of random projection proposed in this paper extend to non-smooth settings? As indicated in Figure 3, GoLore and GaLore share similar performance.

(1) Theoretical benefits of random projection in non-smooth settings

As established in our response to Weakness 1, Theorem 1 naturally extends to non-smooth settings, demonstrating that GaLore fails to converge to stationary solutions in such scenarios due to SVD projection. This SVD-induced error can be mitigated through random projection in non-smooth settings, as the error is independent of the cost function's smoothness properties. Consequently, we can safely claim that GoLore incurs less error than GaLore due to the benefits brought by random projection. Theoretically, we believe the most convincing approach to justify this statement is to provide a rigous proof of GoLore's convergence under non-smooth settings, which is an interesting open question that we leave as our future work.

We would like to emphasize that establishing convergence under the $L$-smoothness assumption is not a limitation unique to our work. Indeed, convergence guarantees for various optimization methods—including SGD, momentum SGD, adaptive SGD, and distributed SGD—are traditionally established under the standard $L$-smoothness assumption, yet these methods are widely applied to deep learning tasks with non-smooth activations. To our knowledge, it is uncommon in the literature to establish convergence analyses for momentum SGD and Adam have not been developed without the $L$-smoothness assumption. Our work follows this established convention.

(2) Empirical benefits of random projection in real-world applications

However, we can still validate the benefit of random projection through empirical results. The similar performance in Figure 3 is due to the insufficient number of tokens that the algorithms trained on, which we previously set following the setup in GaLore's paper. With insufficient training tokens, the algorithms have not reached the neighborhood of stationary solutions, where the gradients are less noise-dominated and random projection is less beneficial. In our revised manuscripts, we reproduced the experiment with more total training tokens, and GoLore shows clearer advantage in the results presented in Figure 7, Appendix E. Moreover, we have conducted new experiments to fine-tune OPT-13B on the BoolQ dataset. As shown in Table 4 of Appendix E, GoLore achieves an accuracy of 81.96%, notably higher than GaLore's accuracy of 79.79%.

We thank the reviewer again for his careful comments. We hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.

We thank the reviewer for the detailed comments. All questions have been clarified as best as we can, and we are glad to address further comments or questions.

Weakness 1. The non-convergence of GaLore is studied and addressed with the smooth optimization, which is not the major application of GaLore.

We appreciate the reviewer’s feedback and would like to clarify that our non-convergence result in Theorem 1 extends to the non-smooth setting. Specifically, our manuscript makes three assumptions: (A1) Lower boundedness, (A2) L-smoothness, and (A3) Stochastic gradients. Theorem 1 states:

"There exists a counter-example satisfying Assumptions A1, A2, and A3 for which GaLore cannot converge to a stationary solution."

Notably, any counter-example satisfying Assumptions A1, A2, and A3 inherently satisfies Assumptions A1 and A3. Thus, we can state the following:

"There exists a counter-example satisfying Assumptions A1 and A3 for which GaLore cannot converge to a stationary solution."

This revised theorem demonstrates that GaLore fails to converge even in non-smooth settings, addressing the reviewer’s concern directly.

Weakness 2. The random projection strategy may not be the best choice and the authors did not discuss other choices like using random $r$ singular vectors. Mixing GaLore with GoLore is evidence for possible inefficiency of GoLore.

(1) Seeking the best random projection is beyond the scope of our contribution

The reviewer may have misunderstood our contributions. Our primary contribution is to demonstrate that the SVD projection in GaLore leads to non-convergence and to propose a random projection as a solution to this issue. We do not aim to identify the optimal random projection. Besides, some properties of our random projection strategy, such as Lemma 5, are essential in the convergence proofs, whch may not be satisfied by other random strategies. While it is possible that a better random projection exists than the one we proposed, this does not undermine our contribution of introducing the first random projection strategy that ensures GaLore’s convergence with theoretical guarantees.

(2) Mixing GaLore with GoLore is a carefully designed solution

The hybrid of GaLore and GoLore reflects a carefully crafted algorithmic design based on a deep understanding of their respective properties. According to our theoretical analysis, the SVD projection in GaLore is more effective at capturing the true gradient component in the early stages of pretraining, where the true gradient dominates the gradient noise.

However, in the later stages of training, where gradient noise becomes more prominent, the random projection approach in GoLore demonstrates its advantage. In essence, the SVD projection accelerates convergence during the initial training stages, while random projections enable more accurate convergence in later stages. This insight naturally leads to the hybrid GaLore + GoLore approach, leveraging the strengths of both methods for optimal performance across different training phases.

Based on our experiences, SVD projection in the early stage outperforms any shape of random projection due to its efficiency in capturing the main gradient component. Consequently, we believe that combining SVD and random projections is consistently the superior choice for achieving both efficiency and accuracy throughout the training process.

Weakness 3. The numerical benefit is not very obvious. The comparison with Flora is missing.

(1) Numerical results

Since the main contribution of this paper lies in establishing convergence guarantees for memory-efficient algorithms, we believe our experimental results have validated our theoretical findings. Please refer to our response to Point 3 in the global response for further details.

In particular, we have conducted new experiments to fine-tune OPT-13B on the BoolQ dataset. As shown in Table 4 of Appendix E, GoLore achieves an accuracy of 81.96%, notably higher than GaLore's accuracy of 79.79%.

Furthermore, we would like to emphasize that GoLore retains the algorithmic structure of GaLore, differing only in replacing the SVD projection with a random projection during the later phase of pre-training. This simple modification introduces no additional computational overhead while providing strong convergence guarantees and consistently improved performance. Given these advantages, we believe random projection is a valuable technique with both theoretical benefits and practical utility.

(2) Comparison with Flora

We have conducted additional experiments on Flora and added the results in Table 2, where Flora does not perform better than GaLore.

Weakness 4. Typo in the title: 'optimiztion' -> 'optimization'

We thank the reviewer for pointing out this serious problem and have corrected the typos in our revised manuscripts.

We thank the reviewer for the detailed comments. First of all, we would like to clarify that we fully acknowledge the value of the GaLore method. In our view, GaLore is an excellent algorithm with novel insights and strong empirical performance. This inspired us to investigate and establish convergence guarantees for the great algorithm. However, in the proving process, we identified several aspects of its algorithmic structure that may hinder convergence. For this reason, we have clarified several conditions under which GaLore can converge and proposed a simple random projection technique to address its convergence issues. We believe our work strengthens the theoretical foundation and practical applicability of GaLore.

All questions raised by the reviewers have been clarified. We are glad to address any further comments or questions.

Weakness 1. The reasoning for why GaLore fails to converge seems flawed as in general, for any form of SGD, the gradient noise will dominate the function gradient near a first-order stationary point.

We respectfully note that the reviewer's interpretation of GaLore's failure to converge to a stationary solution requires clarification. While it is true that the gradient noise dominates the true gradient near a first-order stationary point in any SGD variant, this phenomenon is not the primary cause of non-convergence in GaLore. Rather, the non-convergence stems from the SVD projection inherent to GaLore's methodology. Specifically, it is using SVD projection in the noise-dominant scenario that prevents GaLore from achieving convergence.

In particular, as the algorithm approaches the stationary solution and gradient noise begins to dominate the true gradient, the SVD-derived subspace may exclusively capture the noise component (particularly when selecting a sufficiently small $r$) and completely discard the true gradient information. Consequently, when no meaningful gradient information can be utilized, GaLore naturally fails to converge. This is the primary intuition underlying our counter-example presented in Equation (1).

In contrast, our proposed random projection consistently captures the true gradient information in expectation, regardless of whether the gradient noise dominates the true gradient or how small $r$ is chosen. To see it, let $G$ denote the true gradient and $\epsilon$ represent the zero-mean random gradient noise. Additionally, we assume the random projection $P$ is independent of the gradient noise. By applying Lemma 5 in our manuscript, the gradient estimate satisfies

$$\mathbb{E}[PP^T (G + \epsilon)] = \mathbb{E}[PP^T] G + \mathbb{E}[PP^T] \mathbb{E}[\epsilon] = \mathbb{E}[PP^T] G = \frac{r}{m} G.$$

This derivation demonstrates that random projection consistently preserves gradient information, even in regimes where $\epsilon$ dominates $G$. In contrast, SVD projection fails to achieve this preservation property.

Weakness 2. A lack of discussion on other conditions that could ensure the convergence of GaLore.

Given that GaLore's non-convergence arises from employing the greedy SVD strategy in noise-dominated scenarios, the most natural solutions are either to avoid using the greedy SVD strategy or to reduce the noise scale, both of which are covered in our discussion. Additionally, the strong counter-example constructed in Theorem 1 rules out alternative approaches, such as introducing a "bounded gradient" assumption, modifying the optimizer $\rho$, or adjusting hyperparameters such as the learning rate $\eta$, momentum parameter $\beta_1$, or subspace update frequency $\tau$. While we agree that exploring other conditions under which GaLore can converge is an interesting open question, it is beyond the scope of this paper and could be left to future work.

Weakness 3. The improvement in Table 2 is minor. Using GaLore for the majority process is not consistent with the theory.

(1) Results in Table 2

We respectfully disagree that the improvement in Table 2 is minor. Though our methods present a 0.26 higher score than GaLore, it's worth noting that the performance gap between GaLore and full-parameter training is only 0.38. Regarding full-parameter training as the performance limitation, we have a 3 times smaller performance gap, which should not be regarded as minor. Please refer to our response to Point 3 in the global response for further details.

In particular, we have conducted new experiments to fine-tune OPT-13B on the BoolQ dataset. As shown in Table 4 of Appendix E, GoLore achieves an accuracy of 81.96%, notably higher than GaLore's accuracy of 79.79%.

Furthermore, we would like to emphasize that GoLore retains the algorithmic structure of GaLore, differing only in replacing the SVD projection with a random projection during the later phase of pre-training. This simple modification introduces no additional computational overhead while providing strong convergence guarantees and consistently improved performance. Given these advantages, we believe random projection is a valuable technique with both theoretical benefits and practical utility.

(2) The hybrid of GaLore and GoLore is derived from our theory

The hybrid of GaLore and GoLore does not contradict our theoretical findings regarding GaLore's non-convergence and GoLore's convergence. According to our theories, the SVD projection in GaLore is more efficient than the random projection in capturing the true gradient component in the early stages of pre-training, where the true gradient dominates the gradient noise. The advantage of using random projection becomes evident in the later stages of training, where the gradient noise dominates the true gradient. In short, the SVD projection enables faster convergence in the initial training stages, while random projections facilitate more accurate convergence in the later stages. This naturally leads to the hybrid GaLore + GoLore approach.

Weakness 4. Suggestions on improving the language and presentation, including:

a) The term “stationary solutions” is frequently used and appears to refer to first-order stationary points.

We thank the reviewer for the suggestion. In order to avoid ambiguity, we included the following clarification: "By stationary solutions, we refer to first-order stationary points $x\in\mathbb{R}^d$ such that $\nabla f(x)=0$ for objective function $f:\mathbb{R}^d\rightarrow\mathbb{R}$."

b) Figure 1 is shown on page 2 but isn’t introduced until the end of page 5, and the y-axis label seems intended to represent log(f) in Equation (1) but is labeled simply as “Loss.”

The y-axis label is exactly the function value $f$ and is negative only because the global minimum of the qradratic function $f$ is negative. We have changed the y-axis to "$f(x)-f_{\min}$" to avoid ambiguity and added detailed descriptions in the caption of Figure 1.

c) At the top of page 4, GaLore is described as a “subspace learning algorithm,” which is inaccurate.

We refer to GaLore as a "subspace learning algorithm" because it trains LLMs by projecting gradients into subspaces, maintaining optimizer states within subspaces, and accumulating updates in subspaces. If the reviewer has specific concerns or suggestions about why it may not be accurately described as a "subspace learning algorithm," we would be happy to revise our terminology based on the feedback.

d) In the statement of Theorem 2, the use of the term MSGD and the expected value is confusing, as the source of stochasticity is unclear when the gradients are deterministic.

We thank the reviewer for the insightful suggestion. There is no stochasticity in this setting and we have removed the expectation, including those in the results or proofs related to deterministic GaLore/GaSare. The term MSGD used is consistent with Algorithm 1 and it might be wordy to use a new term like "MGD" instead, hence we remarked below Theorem 2 to avoid any possible ambiguity: "In fact, MSGD here reduces to momentum gradient descent by using deterministic gradients".

e) There are numerous typos that need correction, especially the spelling of “Optimization” in the title.

We sincerely apologize for all the typos which may bring the reviewer a poor reading experience, and had made our best to fix these typos in our revised manuscripts.

Question 1. Whether other mild conditions are sufficient to prove the convergence of GaLore in the stochastic setting, e.g., a sufficiently small gradient norm, assuming the gradient noise is isotropic.

We greatly appreciate the reviewer’s insightful comments on isotropic noise. While conditions such as a bounded gradient norm or tuned hyperparameters may seem promising, they are insufficient to resolve the convergence issue, as our counter-example remains valid even under these settings.

Assuming isotropic gradient noise is an intriguing perspective, and indeed, it provides a defense against our counter-example. This opens an interesting direction for future research—whether GaLore converges under isotropic noise remains an open question. However, it is widely recognized within the community that gradient noise in SGD is typically anisotropic, as evidenced by studies such as [arXiv:1803.00195], [arXiv:2006.08680], [arXiv:2105.09557], [arXiv:2207.02628], and [arXiv:2310.00692]. This raises a concern about the practical relevance of studying GaLore’s convergence under the isotropic noise assumption.

On the other hand, our proposed solution—using random projections—addresses GaLore's convergence issue in both isotropic and anisotropic noise settings. This approach provides a more robust and broadly applicable solution to the problem.

Question 2. Is the GoLore projection contractive according to the definition in Section 2 of (Fatkhullin et al., 2024)? Also, how does the empirical performance of running only GaLore compare to running only GoLore?

(1) Contractive property

The contractive property only holds for $\tau\mid t$ and does not hold for $\tau\nmid t$. This is because the reused projection matrices are no longer random given the filtration at iteration $t$ $(\tau\nmid t)$.

(2) GoLore@100%

In most of our experiments, we find that GoLore@100% is not comparable to GaLore. However, this does not contradict our theoretical findings regarding GaLore's non-convergence and GoLore's convergence. According to our theories, the SVD projection in GaLore is more efficient than the random projection in capturing the true gradient component in the early stages of pre-training, where the true gradient dominates the gradient noise. The advantage of using random projection becomes evident in the later stages of training, where the gradient noise dominates the true gradient. In short, the SVD projection enables faster convergence in the initial training stages, while random projections facilitate more accurate convergence in the later stages. This naturally leads to the hybrid GaLore + GoLore approach. This further explains why GoLore@100% fails to surpass GaLore in performance. The slower convergence of GoLore@100%, particularly during the initial training stages, adversely affects its fine-tuning performance.

Comments. While the paper’s motivation is intriguing, the narrative feels somewhat misguided. The claim that GaLore is unsatisfactory lacks strong support from both theoretical and experimental perspectives. The most compelling results are the positive convergence findings for GaLore in the deterministic and large-batch settings. The paper would be significantly improved by focusing on analyzing conditions under which GaLore converges with mild assumptions, rather than asserting that GaLore has fundamental flaws. Investigating the computational interplay between subspace update frequency, gradient noise, and step size would add valuable insights.

First of all, we would like to clarify that we fully acknowledge the value of the GaLore method. In our view, GaLore is an excellent algorithm with novel insights and strong empirical performance. This inspired us to investigate and establish convergence guarantees for the great algorithm. However, in the proving process, we identified several aspects of its algorithmic structure that may hinder convergence. For this reason, we have clarified several conditions under which GaLore can converge and proposed a simple random projection technique to address its convergence issues. We believe our work strengthens the theoretical foundation and practical applicability of GaLore.

Second, we respectfully disagree with the claim that our theoretical results are misguided. Both our theoretical analysis and experimental evidence clearly demonstrate that GaLore lacks convergence guarantees under standard assumptions. By “standard assumptions,” we refer to the conditions typically required for vanilla SGD to ensure convergence. Our results show that there exist scenarios where vanilla SGD converges, but GaLore does not. This highlights a theoretical limitation of the GaLore algorithm.

Third, we have already provided conditions under which GaLore can converge. However, the strong counter-example constructed in Theorem 1 rules out alternative approaches, such as introducing a "bounded gradient" assumption, modifying the optimizer $\rho$, or adjusting hyperparameters such as the learning rate $\eta$, momentum parameter $\beta_1$, or subspace update frequency $\tau$.

Finally, we believe that identifying simple yet effective modifications to GaLore is an important contribution to addressing its non-convergence issues. GoLore, as a direct variant of GaLore, remains within the same algorithmic family. The proposed random projection technique, which introduces no additional computational overhead, provides robust convergence guarantees and consistently improves performance. We view these adjustments as crucial for enhancing the practical and theoretical robustness of the GaLore framework.

We thank the reviewer again for his careful comments. We hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.

Weakness 3. GoLore@100% is assumed to be not comparable with GaLore according to the intuition, which seems contradictory with GaLore's non-convergence and GoLore's convergence.

In most of our experiments, we find that GoLore@100% is not comparable to GaLore. However, this does not contradict our theoretical findings regarding GaLore's non-convergence and GoLore's convergence. According to our theories, the SVD projection in GaLore is more efficient than the random projection in capturing the true gradient component in the early stages of pre-training, where the true gradient dominates the gradient noise. The advantage of using random projection becomes evident in the later stages of training, where the gradient noise dominates the true gradient. In short, the SVD projection enables faster convergence in the initial training stages, while random projections facilitate more accurate convergence in the later stages. This naturally leads to the hybrid GaLore + GoLore approach. This further explains why GaLore@100% fails to surpass GaLore in performance. The slower convergence of GaLore@100%, particularly during the initial training stages, adversely affects its fine-tuning performance.

Weakness 4. It is better to also include comparisons with zero-th order or gradient sketching methods.

(1) Connection with zero-th order methods.

Zero-th order methods (Malladi et al., 2023; Zhang et al., 2023; Chen et al., 2024) are another line of works on memory-efficient training. While these algorithms randomly select a direction to estimate the directional derivatives by finite difference, GoLore computes subspace gradients via back propagation. The descent directions used in zero-th order methods change every iteration, while GoLore applies a more lazily strategy changing its subspace every $\tau$ iterations.

(2) Connection with gradient sketching methods.

Gradient sketching methods like Hanzely et al.(2018) and Wang et al. (2024) uses gradient sketches in algorithm iterates. These methods recover gradient estimates from projected gradients and retains full-size gradients and optimizer states. In comparison, GoLore directly updates with projected gradients and retains compressed gradients and optimizer states, which is more memory-efficient.

Following the reviewer’s valuable suggestion, we have incorporated the related discussions into Appendix F in our revised manuscript.

Weaknesss 5. The models in the experiments are not "large". Improvement in Table 2 is marginal. Accuracy for Figure 4 is missing.

(1) Models are not "large".

Given our limited computing resources, we were unable to conduct experiments on very large language models. The model sizes we tested are common in the literature. For instance, GaLore (ICML 2024 Oral) and Flora (ICML 2024) both report empirical results using 60M models. While GaLore and our paper use a 7B model as the largest size, Flora only mentions the memory usage for 7B models, noting that "the training takes months to complete." To further address the reviewer's concerns, we conducted additional experiments on the OPT-13B model, and the results can be found in Appendix E, Table 4, of our revised manuscript.

(2) Improvement in Table 2.

Since the main contribution of this paper lies in establishing convergence guarantees for memory-efficient algorithms, we believe our experimental results have validated our theoretical findings. Please refer to our response to Point 3 in the global response for further details.

In particular, we have conducted new experiments to fine-tune OPT-13B on the BoolQ dataset. As shown in Table 4 of Appendix E, GoLore achieves an accuracy of 81.96%, notably higher than GaLore's accuracy of 79.79%.

Furthermore, we would like to emphasize that GoLore retains the algorithmic structure of GaLore, differing only in replacing the SVD projection with a random projection during the later phase of pre-training. This simple modification introduces no additional computational overhead while providing strong convergence guarantees and consistently improved performance. Given these advantages, we believe random projection is a valuable technique with both theoretical benefits and practical utility.

Question 1. What does $\rho$ mean in Theorem 1? Can $\rho$ just map $P^\top G$ to $G$ so that the algorithm can still converge?

We thank the reviewer for raising this valuable question. In our previous definition, we defined $\rho$ following the convention of the GaLore's paper as a stateful entry-wise gradient operator. This means that, the inputs and outputs of $\rho$ are in the $\mathbb{R}^{r_{\ell} \times n_{\ell}}$ subspace. Mapping $P^\top G$ to $G$ would violate the dimensions and lead to illegal operations within the GaLore algorithm. For the rigor of Theorem 1, we have clarified this point by adding the following: "... subspace optimizer $\rho$ takes as input the subspace gradient of shape $r_{\ell} \times n_{\ell}$ and outputs the subspace update direction of shape $r_{\ell} \times n_{\ell}$..."

Question 2. Convergence results related to other $\beta_1$ and $\eta$.

We have established convergence guarantees for a broad range of $\beta_1$ and $\eta$, as detailed in Theorem 6, Theorem 7 and Theorem 8 in Appendix B.2, B.3, B.4, respectively. Please also refer to our response to Weakness 2 raised by you, where we establish convergence for the following conditions: $0 < \beta_1 \le 1$, $\tau \ge \frac{64}{3 \beta_1 \underline{\delta}}$, and 0 < \eta \le \min\left\\{\frac{1}{4L}, \sqrt{\frac{3 \underline{\delta} \beta_1^2}{80 L^2}}, \sqrt{\frac{\underline{\delta}}{40 \tau^2 L^2}}, \sqrt{\frac{3 \beta_1}{32 \tau L^2}}\right\\}.

Question 3. The loss in LLMs training is usually very noisy. Are the curves in Figures 3 and 4 already smoothed?

The curves in Figure 3 are smooth because we only present the validation loss, which is computed every 500 iterations. It is true that we smoothed the curves in Figure 4 by averaging every 15 consecutive loss values for better presentation.

Question 4. What are the batch sizes used in Figure 1 for all four different algorithms?

We use a batch size of 128 for large-batch GaLore and a batch size of 1 for the other algorithms, including GaLore, GoLore, and full-parameter training. We thank the reviewer for pointing out this issue and have addressed it in our updated manuscript.

We thank the reviewer once again for their valuable comments. We hope that these responses help clarify the reviewer's questions, and we are happy to address any further comments or inquiries.

We thank the reviewer for careful and valuable comments. All questions have been addressed as best as we can, and we are glad to address further comments or questions.

Weakness 1. Typos 'optimiztion', 'effiicent', 'pretraining', Algorithm 1 and whether we can apply projection to second-order momentum $V$.

(1) Clarification on typos

We thank the reviewer for identifying these spelling errors, which we have corrected accordingly. Additionally, we have followed the suggestion to provide more details about Figure 1 in its captions. We sincerely appreciate the reviewer’s thorough and thoughtful review.

However, the equation on line 347 in Algorithm 1 is not a typo. In the large-batch scenario, the large-batch gradient is used solely to compute a precise SVD projection matrix, as shown in lines 338–340. Once the SVD projection matrix is computed, the large-batch gradient is no longer required. Instead, we use the standard stochastic gradient (line 347) to accumulate momentum and update the model. Since the gradients used in lines 338 and 347 differ, we have placed them in separate if-else blocks for clarity.

Since the above questions are only three spelling mistakes, we wish the reviewer could trust our sense of responsibility on the quality and rigor of our results, and we are open to answer any related questions.

(2) Project second-order momentum $V$ into low-rank subspace

We thank the reviewer for the insightful question. While it is feasible to project the second-order momentum $V$ into a low-rank subspace in practical experiments, establishing convergence guarantees for such an approach presents significant challenges, particularly when the projection matrix is updated lazily. We consider this an important direction for future work and aim to develop convergence guarantees for algorithms that project the second-order momentum $V$ into a low-rank subspace.

Weakness 2. Is there any condition, threshold, or phase transition for $B$ such that anything smaller leads to divergence and anything larger leads to convergence.

(1) Large-batch GaLore can converge with any batch-size $\mathcal{B}\sim T^{a}, a > 0$

In Theorem 7 in Appendix B.4, we provide the convergence rates of the large-batch GaLore with any batch-size $\mathcal{B}$:

Theorem 7. Given any $0<\beta\_1\le1$, $\tau\ge\frac{64}{3\beta\_1\underline{\delta}}$ and 0<\eta\le\min\left\\{\frac{1}{4L},\sqrt{\frac{3\underline{\delta}\beta\_1^2}{80L^2}},\sqrt{\frac{\underline{\delta}}{40\tau^2L^2}},\sqrt{\frac{3\beta\_1}{32\tau L^2}}\right\\}, large-batch GaLore converges as $\frac{1}{K\tau}\sum\_{t=0}^{K\tau-1}\mathbb{E}[\\|\nabla f(x^{(t)})\\|\_2^2]\le\frac{16\Delta}{\underline{\delta}\eta K\tau}+\left(\frac{160}{3\beta\_1\underline{\delta}\tau\mathcal{B}}+\frac{352}{3\underline{\delta}^2\mathcal{B}}+\frac{32\beta\_1}{3\underline{\delta}}\right)\sigma^2.$

According to Theorem 7, when we choose hyper-parameters as $\mathcal{B}\sim T^{a}$, $\tau\sim T^{b}$, $\beta\_1\sim T^{-b}$ for any $a>0$ and $0<b<1$, large-batch GaLore can converge to the solution at the convergence rate of $\mathcal{O}(\frac{1}{T^{\min\\{a,b,1-b\\}}})$. This result implies that large-batch GaLore can converge for any batch size satisfying $\mathcal{B} \sim T^a$ with any positive $a$, provided the other hyperparameters $\tau$, $\beta_1$, and $b$ are chosen appropriately.

In the main body of our manuscript, we presented the convergence results for $\mathcal{B} \sim \sqrt{T}$ because: a) Setting $\mathcal{B}, \tau \sim \sqrt{T}$ and $\beta_1 \sim 1/\sqrt{T}$ achieves the optimal convergence rate of $\mathcal{O}(1/\sqrt{T})$. Setting other values of $\mathcal{B}$ would result in a theoretically slower convergence rate. b) The total computational complexity with $\mathcal{B} \sim \sqrt{T}$ is $\Theta(1)$ per iteration, as it is utilized only every $\tau \sim \sqrt{T}$ iterations. This complexity is no higher than that achieved with $\mathcal{B} \sim T^a$ for smaller $a$.

(2) Large-batch GaLore cannot converge with batch-size $\mathcal{B}=\mathcal{O}(1)$

On the other hand, large-batch GaLore with any constant batch size $\mathcal{B} = \mathcal{O}(1)$ is not guaranteed to converge. Specifically, Theorem 1 establishes the non-convergence property of GaLore under an arbitrary constant gradient variance $\sigma^2$. While using a constant batch size $\mathcal{B} = \mathcal{O}(1)$ reduces the variance $\sigma^2$ to $\sigma^2 / \mathcal{B}$, this remains a constant variance, and Theorem 1 confirms that this does not ensure convergence for any constant $\mathcal{B}$.

We thank the reviewer for the detailed comments. All questions have been clarified as best as we can, and we are glad to address any further comments or questions.

Weakness 1. The marginal advantages of GoLore and whether the inability of GaLore is common in real-world scenarios.

(1) The marginal advantages of GoLore

For experimental comparisons between GaLore and GoLore, please check our response in Point 3 of the global response. In particular, we have added new expriments to fine-tune OPT-13B on the BoolQ dataset. It shows in Table 4 Appendix E that GoLare achieves an accuracy of 81.96%, notably higher than GaLore's accuracy of 79.79%.

Furthermore, we would like to emphasize that GoLore retains the algorithmic structure of GaLore, differing only in replacing the SVD projection with a random projection during the later phase of pre-training. This simple modification introduces no additional computational overhead while providing strong convergence guarantees and consistently improved performance. Given these advantages, we believe random projection is a valuable technique with both theoretical benefits and practical utility.

(2) Non-convergence of GaLore is common in real-world scenarios

In real-world scenarios, GaLore often produces suboptimal results across various tasks. For instance, during LLaMA pre-training on the C4 dataset, GaLore exhibits a consistent performance gap of 0.08–0.82 compared to full-parameter training, as reported in its original paper. Similarly, fine-tuning RoBERTa on GLUE yields comparable outcomes, with GaLore's score being 0.36–0.41 lower than that of full-parameter fine-tuning. However, in our experiments, we observed that by incorporating random projection, GoLore can significantly reduce the performance gap to 0.12, demonstrating its effectiveness to improve the performance.

Weakness 2. Whether other memory-efficient fine-tuning algorithms also struggle with convergence.

Thank you for this insightful question! To the best of our knowledge, no existing memory-efficient pre-training or fine-tuning algorithms, including LoRA, DoRA, ReLoRA, SLTrain, Flora, ETHER+, and others, have theoretical convergence guarantees. It is not clear in the literature whether these algorithms encounter convergence issues. This underscores the contribution of our work, as we establish the first convergence guarantees for a memory-efficient algorithm.

In our manuscript, we focus solely on GaLore and GoLore because: a) GaLore is a strong baseline algorithm in this field, and b) the only difference between GaLore and GoLore is the use of random projection. Therefore, it is natural to compare GaLore and GoLore in order to validate the effectiveness of the random projection.

Weakness 3. A more intuitive explanation of why random projection works and whether it is quicker than SVD.

(1) Intuition behind random projection

Thanks for raising this question. We are happy to clarify it. The stochastic gradient matrix consists of two components: the true gradient and the gradient noise, as illustrated in Fig. 2. When the true gradient significantly outweighs the gradient noise, typically at the start of training, the low-rank subspace obtained via SVD effectively preserves the true gradient information. This is why the reviewer believes the SVD projection is beneficial. However, as training progresses toward the stationary solution, the true gradient diminishes to zero while the stochastic gradient noise persists. In this scenario, where the gradient noise dominates the true gradient, SVD can only capture the noise information and may entirely miss the true gradient. This is the fundamental reason why GaLore with SVD fails to converge to the desired solution.

In contrast to the SVD projection, our proposed random projection consistently captures the true gradient information in expectation, regardless of whether the gradient noise dominates the true gradient or how small the value of $r$ is chosen. This explains why random projection outperforms SVD projection in the later stages of the pre-training phase. For further details, please refer to our response in Point 3 of the global response.

(2) Is random projection quicker than SVD projection?

Using random projections instead of SVD may not result in faster computation, as the subspace projection matrix is computed every $\tau$ iterations, making the overhead of SVD relatively minor on average. We did not observe any speedup in our experiments.

We thank the reviewer again for his careful comments. We hope these responses can clarify the reviewer's questions and are more than happy to address any further comments or questions.

4. New experiments.

In our revised manuscripts, we have added more experiments to respond to reviewer's concerns, including:

a) Figure 7 in Appendix E: pre-training tasks with more tokens;

b) Table 2 in Section 7: fine-tuning RoBERTa-base on GLUE with Flora.

c) Table 4 in Appendix E: fine-tuning OPT-13B on BoolQ with GaLore and GoLore@30%.

We sincerely thank all reviewers for their valuable comments and are happy to address any further questions or concerns.