acceptodds
Under review as a conference paper at ICLR 2027

Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise

Abstract

Randomized-subspace methods use low-dimensional projected stochastic gradients, offering potential savings in directional-derivative queries and communication volume. However, theoretical guarantees for such methods under heavy-tailed noise remain limited. We propose randomized subspace normalized SGD (RS-NSGD), which normalizes using only the projected stochastic gradient and thereby preserves the low-dimensional update structure. Because the random subspace also enters the normalization denominator, existing analyses of randomized subspace SGD do not directly apply. We overcome this difficulty by exploiting distributional properties specific to Haar-random projections. Under a bounded -th-moment assumption commonly used in analyses of heavy-tailed stochastic-gradient noise, with , we establish convergence guarantees both in expectation and with high probability. Our oracle-complexity bounds characterize regimes in which RS-NSGD improves over full-dimensional normalized SGD.

Primary area:
optimization
Keywords:
randomized subspace methods, normalized SGD, heavy-tailed noise, nonconvex optimization, convergence analysis

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_4pNiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies nonconvex stochastic optimization in high-dimensional settings, where computing or communicating full-dimensional stochastic gradients can be expensive. Randomized subspace SGD reduces this cost by operating on low-dimensional projected gradients, but existing theoretical guarantees mainly rely on light-tailed noise assumptions such as bounded variance. In contrast, normalized SGD is known to admit convergence guarantees under the weaker bounded pp-th moment assumption, which allows heavy-tailed stochastic-gradient noise.

Motivated by this gap, the paper proposes Randomized Subspace Normalized SGD (RS-NSGD), which performs normalization using only the projected stochastic gradient. The authors develop new analysis based on properties of Haar-random projections and establish both in-expectation and high-probability convergence guarantees under heavy-tailed noise. They further derive oracle-complexity bounds and characterize regimes in which RS-NSGD can outperform full-dimensional NSGD. Synthetic experiments are designed to validate the predicted dependence on the effective rank, while language-modeling experiments demonstrate the empirical behavior under the oracle-call metric.

Critical strengths
  • The paper addresses an important optimization setting by combining randomized subspace updates with gradient normalization. The resulting method is not covered directly by existing analyses because the random projection appears nonlinearly. The paper develops a tailored Haar-projection analysis, including Proposition 4.1, which shows that the normalized projected direction remains exactly aligned with the full normalized direction in expectation. This leads to new convergence and oracle-complexity guarantees under heavy-tailed noise.

  • The synthetic experiments are well aligned with the theory. By explicitly varying the effective rank, they empirically reproduce the regimes predicted by the oracle-complexity analysis. The language-modeling experiments provide further empirical evidence that low-dimensional RS-NSGD can be competitive under the oracle-call metric.

Critical weaknesses
  • The high-probability results are substantially less favorable to RS-NSGD than the in-expectation results. In the parameter-aware regime, the derived high-probability oracle-complexity bound is minimized at r=dr=d, i.e. by full-dimensional NSGD. In the parameter-agnostic regime, RS-NSGD obtains an asymptotic r/dr/d improvement when p<2p<2, but the finite-order bound also contains unfavorable dimension/subspace-dependent terms (e.g., a d6/r5d^6/r^5 term), while the p=2p=2 comparison depends on problem parameters.

  • While the oracle-call model is well motivated for directional-derivative and communication settings, the empirical evidence does not fully establish that the claimed oracle-efficiency advantage translates to practical computational efficiency. In the main language-modeling trajectory experiments, the authors first compute the full minibatch gradient using reverse-mode AD and then project it, rather than computing only the rr directional derivatives assumed by the oracle model. A direct wall-clock/memory comparison in the intended implementation regime would strengthen the practical motivation. The real-data experiments also do not directly verify that the tested optimization trajectories operate in the heavy-tailed regime targeted by the theory.

Questions for authors
  • The paper demonstrates favorable optimization performance mainly as a function of the directional-derivative oracle budget. However, in the main language-modeling experiments, the full stochastic gradient is first computed by reverse-mode AD and then projected. Could the authors clarify to what extent the observed oracle-efficiency gains are expected to translate into practical wall-clock or memory improvements over a standard reverse-mode implementation of NSGD? In particular, a direct wall-clock comparison between the intended JVP-based RS-NSGD implementation and reverse-mode NSGD would help clarify the practical significance of the proposed method.

  • The strongest high-probability advantage of RS-NSGD appears in the parameter-agnostic p<2p<2 regime, whereas in the parameter-aware regime the derived bound is minimized by r=dr=d. In practice, however, optimizer hyperparameters such as the stepsize and subspace dimension are typically tuned using validation performance, as is also done in the experiments in this paper. How should we interpret the distinction between the parameter-aware and parameter-agnostic theoretical regimes under such practical tuning? Can empirical tuning effectively adapt to the unknown problem/noise parameters and thereby reduce or eliminate the theoretical advantage of the parameter-agnostic RS-NSGD bound? It would also be useful to discuss whether the cost of tuning should be included in the oracle-complexity comparison.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 4pNi

Thank you for your careful assessment and for recognizing the technical contribution of the Haar-normalized analysis. Changes to the manuscript are shown in red in the revised PDF.

Critical weakness 1: Difference between in-expectation and high-probability bounds

In the in-expectation analysis, taking expectations over Haar-random subspaces allows us to exploit the effective-rank dependence of the smoothness matrix through Proposition 4.2. In contrast, our high-probability analysis does not use this effective-rank-dependent estimate, leading to the difference you point out.

Our work establishes both in-expectation and high-probability convergence guarantees for RS-NSGD under heavy-tailed noise, and identifies conditions under which oracle complexity can be improved. Although the high-probability oracle-complexity advantage is more restricted than in expectation, we believe this does not substantially weaken our overall contribution.

Critical Weakness 2 & Question 1: Oracle-cost interpretation, experimental implementation, and heavy-tailed noise

Revision to the manuscript. In response to your comments, we have further clarified the communication-cost interpretation of our oracle measure in Sections 2.1 and 5.2, in addition to the discussion already provided in the Introduction, Section 2.1, and Appendix A.1. We have also added citations to Li and Richtárik (2021) and Deng et al. (2025), in addition to the previously cited Li et al. (2020), and included an explanation of the concrete communication-bit accounting methods used in these studies in Appendix A.1.

As you note, directional derivatives and communication both motivate our oracle measure. In particular, each worker can compute a full gradient using reverse-mode AD and project it before communication, reducing communicated gradient scalars from dd to rr. Thus, the main experiments remain meaningful as optimization-performance comparisons in terms of gradient-communication cost. As already noted in Footnote 1 of Section 2.1, gradient-compression research uses similar communication-cost accounting. The revised manuscript further notes that Li and Richtárik (2021) and Deng et al. (2025), in addition to Li et al. (2020), use similar communication-bit accounting to evaluate experimental performance, supporting the communication-cost interpretation of our oracle-complexity measure.

Backpropagation was more efficient in our environment, but this does not imply that forward-mode AD is generally inferior elsewhere. Both implementations yield identical updates in exact arithmetic (Appendix F.3, Footnote 11). We therefore use backpropagation for optimization comparisons and separately report JVP-based forward-mode AD timings (Appendix F.3, Table 5), where measured time closely follows the oracle count in the tested setting.

Regarding heavy-tailed noise, verifying the tail properties of stochastic-gradient noise in real-data training is generally difficult. As already explained in Section 5.2, motivated by prior evidence of heavy-tailed stochastic gradients in language modeling (Zhang et al., 2020), we follow Hübler et al. (2025) and use language modeling. In contrast, Section 5.1 presents synthetic experiments with explicitly specified heavy-tailed noise.

Question 2: Parameter-aware versus parameter-agnostic settings and tuning costs

Revision to the manuscript. To address the distinction you raise between theoretical parameter knowledge and practical tuning, we have added a brief clarification to Appendix E.2, alongside the existing stepsize-tuning protocol.

An important benefit of the parameter-agnostic regime is that its convergence guarantees remain applicable without prior knowledge of the tail index pp or problem-dependent parameters. Moreover, as shown in Section 4, RS-NSGD can achieve a favorable in-expectation oracle-complexity bound over NSGD even in the parameter-aware regime. On the other hand, empirical hyperparameter tuning differs from the theoretical settings. As described in Appendix E.2, we tune the stepsize for each method and subspace dimension using a common procedure. Such tuning may empirically adapt to unknown parameters, but it does not necessarily reproduce the parameter-aware theoretical parameter choices or the corresponding convergence guarantees. Furthermore, even if the parameter-aware regime were available, RS-NSGD could still have a theoretical advantage in expectation, as noted above.

Although tuning costs matter for total practical optimization cost, our focus is on how random subspace projection affects oracle complexity, so we exclude them from comparisons. We also note that, in our experiments, we apply the same stepsize-search procedure with the same oracle-budget ceiling to each method and subspace dimension. We therefore expect that the performance rankings would generally remain unchanged even if tuning costs were included when comparing individual methods.

Thank you for your response. Most of my concerns have been addressed, and I will therefore maintain my original positive assessment.

Reviewer_QXL1OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper studies the convergence of 'RS-NSGD' meaning random subspace normalized SGD. The algorithm in question is essentially computing the gradient among a random (uniformly chosen) subset of dimensions (haar random subspace) and dividing the update step by the norm of the random subset gradient. Two main theorems prove convergence of the the norm of the gradient towards 0 over the course of running the algorithm both in expectation and with high probability. Their results generalize existing results for full dimension normalized SGD. They demonstrate that when a certain inequality holds, which they argue is likely, the 'oracle complexity' (defined as the sample complexity times the number of coordinates the gradient is computed for) is lower under the random subspace normalized SGD compared to full normalized SGD.

They evaluate their proposed algorithm on a few tasks including one synthetic and one 'language modelling' task.

Critical strengths

The strengths of the paper are that they prove a new result which generalizes previous work and gives interesting insight into the capabilities of random subspace normalized SGD and how this compares to full normalized SGD. The results suggest that under the 'oracle complexity' measurement, RS-NSGD is more efficient than NSGD in reaching convergence.

I do think the notion of efficiency of information for informing weight updates under random subspace sampling is interesting but I am not sure the efficiency is easily interpretable under the oracle complexity measure.

Critical weaknesses

The measure 'oracle complexity' is somewhat contrived to make the algorithm appear favourable. In terms of sample complexity the algorithm would be far worse since it requires many more iterations than full NSGD to converge and each iteration corresponds to a sample unless one considers some sort of sample re-use (multiple epoch) type analysis. Especially in the experiments where loss is plotted against oracle complexity, it is not so clear if the benefit does not just come from exposing the algorithm to orders of magnitude more data. Oracle complexity is also practically irrelevant and the 'efficiency' one would be after (if not in terms of data / sample complexity' would be in terms of compute or memory. But there is no theoretical or practical comparison of latency, required computation or memory (latency or compute is not clear since again more iterates are required to achieve the same number of 'oracle queries').

The experiments are concerning for a few reasons:

The synthetic one is a known setting where the non-normalized versions fail and again its not so clear by any reasonable metric that RS-NSGD is doing better then NSGD since the normalization part is what causes convergence here. The 'real world' experiment is strange in that it is a very toy version of a language modelling task although it seems this was adopted based on existing work. It seems comparisons to more standardly used algorithms (like adam, etc) exists but is in the appendix and is still not very interpretable since oracle complexity is questionable and the task used is also somewhat impractical.

The part that I find very distressing about the experiments is that the real world example is applied to a setting where backprop is used to compute gradients which as noted in the paper is not relevant at all as any real savings would only exist in forward mode AD if they exist at all. It seems even in this setting it was more efficient to perform backprop, throwing away the full gradient than to do forward mode. Not being relevant to backprop significantly diminishes the value of the algorithm but if the authors believe forward mode AD is practical enough for some settings to warrant this algorithm than the examples should be on tasks where forward mode AD is more relevant.

Questions for authors

Can you give some examples of specific problems where forward mode AD is preferred over backprop? As a follow up why not evaluate on these applications instead of a back-prop based example?

Why do you think that the random subsampling can make NSGD more efficient to converge? Do you think it could have to do with the model being exposed to more data through a greater number of iterations?

7 comments
AuthorsOpenReview ↗

Response to Reviewer QXL1 (1/2)

Thank you for your consideration of our theoretical results and experiments. We would like to clarify the meaning and practical relevance of our oracle-cost measure. Changes to the manuscript are shown in red in the revised PDF.

Critical weakness 1: Oracle complexity, sample accesses, and practical cost

We thank the reviewer for the opportunity to further clarify the motivation and practical relevance of our oracle-complexity measure.

Revision to the manuscript. In response to your comments, we have further clarified the communication-cost interpretation of our oracle measure in Sections 2.1 and 5.2, in addition to the discussion already provided in the Introduction, Section 2.1, and Appendix A.1. We have also added citations to Li and Richtárik (2021) and Deng et al. (2025), in addition to the previously cited Li et al. (2020), and included an explanation of the concrete communication-bit accounting methods used in these studies in Appendix A.1.

Our oracle-complexity measure was not introduced merely to favor RS-NSGD. An important point is that the oracle measure used in this paper corresponds not only to directional-derivative queries in forward-mode AD but also to the number of communicated gradient scalars in distributed optimization. In particular, each worker can compute a full gradient using reverse-mode AD and then project it before communication, thereby reducing the number of communicated gradient scalars from dd to rr. As already noted in Footnote 1 of Section 2.1, gradient-compression research also uses communication-cost accounting of the same kind as our oracle-complexity measure. We have further noted in the revised manuscript that Li and Richtárik (2021) and Deng et al. (2025), in addition to Li et al. (2020), use similar communication-bit accounting and evaluate experimental performance in terms of communication bits. Thus, the communication-cost interpretation of our oracle-complexity measure is grounded in established communication-cost measures used in gradient-compression research. Accordingly, the main experiments can also be interpreted as comparisons against cumulative communication bits, rather than only as directional-derivative-query plots.

Regarding sample complexity, RS-NSGD faces a natural trade-off, as do randomized subspace gradient methods, including standard randomized coordinate gradient methods: using less gradient information per iteration reduces the per-iteration cost but may require more iterations than full-gradient methods to reach the same accuracy, and consequently more sample accesses. We do not claim that RS-NSGD reduces sample complexity. Our work evaluates the total oracle complexity, accounting for both the reduction in the per-iteration cost of obtaining or communicating gradient information and the accompanying increase in the number of iterations. Under the same oracle budget, RS-NSGD indeed performs more iterations and accesses more samples than NSGD in our experiments. However, even if this increased sample exposure contributes to the observed performance advantage, that does not invalidate the oracle-complexity comparison; rather, it is precisely the lower per-iteration oracle cost, achieved by using less gradient information, that makes this possible.

Regarding wall-clock time, actual total training time depends heavily on the computational environment, implementation, and other factors. In this work, we evaluate efficiency in terms of oracle complexity, separately from such setting-dependent total training time. Nevertheless, we have not entirely omitted actual computational measurements. Appendix F.3, Table 5 provides timing measurements for a JVP-based forward-mode implementation and confirms that measured time closely follows directional-query count in the tested setting.

Critical weakness 2: Synthetic and language-modeling experiments

Please see our response to Critical weakness 1 for the justification and interpretation of our oracle-complexity measure and the clarifications we have added to the manuscript.

Regarding the synthetic experiments, normalization alone does not account for the advantage of RS-NSGD. In Section 5.1, RS-NSGD performs better than NSGD in terms of oracle complexity for ρ∈{4,20}\rho \in \lbrace 4,20 \rbrace, whereas NSGD is favored for ρ=100\rho=100. Since both methods use normalization, this difference cannot be explained by normalization alone and is compatible with the theoretical predictions concerning effective rank.

Regarding language modeling, in addition to PTB and WikiText-2, we also conduct experiments on WikiText-103, enwik8, and text8 in Appendix F. We also report comparisons with Adam, AdaGrad, AdamW, and Muon in Appendix F. The meaning of the oracle-complexity measure is also important for interpreting these comparisons, and we refer you to our response to Critical Weakness 1 on this point.

AuthorsOpenReview ↗

Response to Reviewer QXL1 (2/2)

Critical weakness 3 & Question 1: Reverse-mode AD versus forward-mode AD and experimental implementation

Revision to the manuscript. We have added clarifications to Sections 2.1 and 5.2 so that the implementation and its communication relevance are explicit in the main text, supplementing the explanation already given in Appendix F.3, Footnote 11. In response to your request for specific applications, we have also added concrete examples to the discussion of memory-constrained optimization already included in Appendix A.1.

The benefits of RS-NSGD are not restricted to forward-mode AD. Even when a full-dimensional gradient is computed using reverse-mode AD, it can be projected before communication, reducing the number of communicated gradient scalars from dd to rr. Thus, using backpropagation does not eliminate the communication benefit of RS-NSGD. The language-modeling experiments can also be interpreted as optimization-performance comparisons in terms of gradient-communication cost, even though gradients were computed by backpropagation. Please see our response to Critical weakness 1 for a more detailed explanation, including related work in gradient compression that evaluates experimental performance using similar communication-cost measures.

Appendix A.1 already discusses problem settings where forward-mode AD can be useful, including cases where reverse-mode AD has substantial memory requirements. We have added concrete examples from the works cited there: PDE-constrained shape optimization (Kozak et al., 2021) and long-horizon recurrent neural network optimization for neuroscience (Yu et al., 2024).

Regarding our experimental choice, backpropagation was more efficient in our experimental environment, but this does not imply that forward-mode AD is generally inferior in other environments. Moreover, the two implementations produce mathematically identical updates, as explained in Appendix F.3, Footnote 11. Therefore, we compare optimization performance using the backpropagation-based implementation, while separately providing supplementary timing measurements for a JVP-based forward-mode AD implementation in Appendix F.3, Table 5.

Question 2: Why can random subsampling improve efficiency? Is exposure to more data responsible?

We interpret “random subsampling” as referring to the random-subspace projection used in RS-NSGD. Please let us know if this interpretation is incorrect. Random subspace updates can improve efficiency because the reduction in per-iteration cost can outweigh the increase in the number of iterations caused by using less gradient information. Indeed, Section 4 analyzes the effect of random subspaces on convergence and shows that the resulting total oracle-complexity bound can be smaller than that of NSGD.

Under the same oracle budget, RS-NSGD can perform more iterations and access more samples than NSGD. Even if this increased sample exposure contributes to its performance, it is precisely one of the benefits enabled by RS-NSGD’s lower per-iteration cost. We discuss this in more detail in our response to Critical Weakness 1.

Thank you for the response. I do have a slightly better understanding for the motivation of the metric now. Although I still feel that the experiments are very unconvincing. Given that the use cases for the algorithm feel fairly niche, I think the experiments serve as an obvious opportunity to demonstrate the actual advantages of the algorithm for the use cases in which the advantages would arrive. If there are additional problems which you added as examples of when this algorithm would be applicable, why not include an experiment that uses one of these algorithms? Also if the value of the metric you propose is in terms of the 'constrained bit communication' framing from the gradient compression literature then would it not be a more relevant comparison to evaluate your algorithm against methods from this field which attempt to address the same problem as you?

Would you consider the contribution of this work to be primarily in terms of understanding (solely a theory work) or is part of the contribution in proposing a new algorithm which you suspect will have practical relevance? I think the burden of proof for this work depends on the answer to this and I was somewhat confused by the experiments. If the work is just theoretical and wants to demonstrate some toy models for the sake of having some experiments such as the synthetic problems then I think it is sufficient to include the toy problems. If the paper is proposing the algorithm as a competitive choice for practice, then I think the experiments are insufficient and should cover more practical use cases and compare against more significant competitors. It is my opinion that if the contribution is just theoretical, than the character level language modelling example should be removed. I understand that a common critique of theory papers is to include more 'real world examples' but in this case I feel the 'real world example' is uncommitting and doesn't demonstrate the relevance of your algorithm and thus serves to distract and leave the reader to question if there is indeed any practical relevance if the chosen example to demonstrate it is so unconvincing.

Reviewer_S1n8OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work presents a randomized subspace SGD algorithm with normalization of the projected minibatch gradient. The low-dimensional random projection is chosen using the standard Haar measure. The authors provide convergence analysis for this method when the gradients are corrupted by heavy-tailed noise, meaning we only have a bound on the pth moment for some p between 1 and 2. The “statistical rate” in these convergence bounds depends on p, getting faster as p gets larger.

Critical strengths

The results fill a gap in the literature, as to my knowledge the combination of normalized gradients, subspace projection, and heavy-tailed noise has not been previously analyzed

The central theorem illuminates what is important in this problem. The overall mathematical analysis appears sound. The reduction in directional derivative complexity in section 4.1 is supported by a favorable directional derivative complexity behavior shown in section 5 under the proposed cost metrics.

The paper is well-written in general, with both the contributions and the methods explained clearly.

Critical weaknesses

-- The contribution fills a small (but well-defined) niche. The authors do not spend much time motivating the study. It would be good to hear about applications that benefit from random projections (of which I am sure there are many) but suffer from heavy-tailed noise (which could use some explanation).

-- The improvement in calculation for directional derivative complexity is not sufficiently linked to practical savings for a full training algorithm. The main training curves use full minibatch gradients followed by projection onto sampled Haar subspaces, while Table 5 times a forward-mode implementation that computes the projected gradients directly through directional derivatives. These implementations produce equivalent updates, and Table 5 supports lower update costs within the tested forward-mode setting. However, the plotted oracle counts are not direct wall-clock measurements, and Table 5 does not compare against standard reverse-mode NSGD or an experiment in a regime where the cost model in this work is real.

-- A wall-clock convergence comparison against that baseline towards the same metric (say, the same target loss) would clarify whether the savings extend to ordinary backpropagation-based training. Preferably, the evaluation can be over a larger training horizon. From the captions in Figure 3, I noticed that with B‾=128\overline{B} = 128, the full iteration gradient update baseline received about 19 iterations on the PTB benchmark and about 1 iteration on WikiText 103 (same math applies from the caption in Figure 11). Therefore, stronger full gradient update baseline models seem not sufficiently trained but their test and validation performances are still within about 2020\\% of the RS-NSGD in a lot of figures in appendix F2. The oracle-axis curve compares optimizers of iteration counts that are substantially different.

Questions for authors
  1. How does heavy-tailed noise arise in machine learning or other scientific computing applications?

  2. As the effective rank ρ\rho is a tunable hyperparameter the synthetic experiments and it alters the optimization problem by changing the condition number. It could also change the error and gradient norm at initialization. How were the initialization quantities controlled in the ρ\rho sweep, and how to interpret the ρ\rho sweep given the simultaneous changing quantities?

  3. How was the directional derivative budget selected for non-synthetic experiments? In addition to my concern that the full gradient update models can be undertrained, are the subspace methods sufficiently trained? Would a longer training change the rankings of the presented methods?

2 comments
AuthorsOpenReview ↗

Response to Reviewer S1n8 (1/2)

Thank you for your careful review and constructive feedback. We appreciate your positive comments on the theoretical analysis and the clarity of the presentation. Changes to the manuscript are shown in red in the revised PDF.

W1 & Q1: Motivation and applications under heavy-tailed noise

Revision to the manuscript. In response to your question about how heavy-tailed noise can arise, we have added the two concrete machine-learning examples to Appendix A.2 of the revised manuscript, with a pointer from Section 2.3, and included Sugiyama et al. (2007) and Wang et al. (2021) as new references.

We thank the reviewer for the opportunity to further clarify our motivation. The motivation for considering heavy-tailed stochastic-gradient noise is already discussed in the Introduction, Appendix A.2, and Section 5.2 of the submitted manuscript, citing, for example, Şimşekli et al. (2019), Nguyen et al. (2019), Hodgkinson & Mahoney (2021), and Zhang et al. (2020).

In distributed optimization settings involving heavy-tailed stochastic-gradient noise, randomized subspace methods can reduce the number of communicated gradient scalars, as explained in the Introduction, Section 2.1, and Appendix A.1. Communication-efficient stochastic optimization under heavy-tailed noise has also been studied by Chen et al. (2024) and Kornilov et al. (2025). Appendix A.4 discusses the advantages of our guarantees over these results, including the subspace-dimension restrictions in Chen et al. and the unfavorable dimensional dependence in Kornilov et al.

Furthermore, the motivation is not limited to distributed optimization. For example, heavy-tailed stochastic-gradient noise has been observed in deep neural network training (Şimşekli et al., 2019). When storing intermediate activations for backpropagation becomes a memory bottleneck in such settings, forward-mode AD can be useful.

Beyond these motivations, we have added two concrete machine-learning examples to Appendix A.2 of the revised manuscript to illustrate how heavy-tailed stochastic-gradient noise can arise under the assumptions of our analysis. The examples are importance-weighted logistic classification under Gaussian covariate shift and a misspecified regularized GLM. Both examples satisfy the bounded pp-th-moment assumption (Assumption 2.4) but not the bounded-variance assumption (Assumption C.2), while also satisfying the other assumptions of our analysis; see Appendix A.2 of the revised manuscript for details.

AuthorsOpenReview ↗

Response to Reviewer S1n8 (2/2)

Critical weaknesses 2–3: Practical meaning of the oracle budget, implementation, and training horizon

Thank you for examining the distinction between our experimental implementation and the oracle-cost model.

Revision to the manuscript. In response to your comments, we have further clarified the communication-cost interpretation of our oracle measure in Sections 2.1 and 5.2, in addition to the discussion already provided in the Introduction, Section 2.1, and Appendix A.1. We have also added citations to Li and Richtárik (2021) and Deng et al. (2025), in addition to the previously cited Li et al. (2020), and included an explanation of the concrete communication-bit accounting methods used in these studies in Appendix A.1.

Importantly, our oracle measure corresponds to both directional-derivative queries in forward-mode AD and communicated gradient scalars in distributed optimization. In particular, each worker can compute a full gradient using reverse-mode AD and project it before communication, reducing communicated gradient scalars from dd to rr. As already noted in Footnote 1 of Section 2.1, gradient-compression research also uses communication-cost accounting of the same kind as our oracle-complexity measure. The revised manuscript adds that Li and Richtárik (2021) and Deng et al. (2025), like Li et al. (2020), evaluate experiments using similar communication-bit accounting. Thus, the main experiments can also be interpreted as comparisons against cumulative communication bits, rather than only as directional-derivative-query plots. We computed full gradients by reverse-mode AD before projecting them in the character-level language-modeling experiments, as it was more efficient in our environment. This was already explained in Appendix F.3, Footnote 11; we have now made the implementation explicit in Section 5.2. This was an implementation choice for the present experiments and does not rule out a potential advantage of using forward-mode AD in other environments.

Regarding the oracle budget, for the main language-modeling experiments, we chose Bˉ×105=128×105\bar B\times10^5=128\times10^5 oracle calls, using the minibatch size Bˉ=128\bar B=128 as the reference and considering powers-of-ten multiples. This allowed training progress within realistic computation time. The experiments already averaged about six wall-clock hours per dataset (Appendix F.4). Thus, the budget balanced experimental scale and computation time. As with randomized subspace gradient methods, including standard randomized coordinate gradient methods, RS-NSGD faces a natural trade-off: using less gradient information per iteration reduces the per-iteration cost but may require more iterations than full-gradient methods to reach the same accuracy. Therefore, it is important to compare methods based on their total cost rather than focusing solely on reductions in per-iteration cost. Our oracle measure provides a way to compare these information costs independently of specific implementations and computing environments. Fewer iterations by full-gradient methods under the same oracle budget do not invalidate our comparison. Rather, this highlights an advantage of randomized subspace methods: lower per-iteration cost allows more iterations within the same budget. This reflects the trade-off evaluated in our study.

Question 2: Initialization quantities and interpretation of the effective-rank sweep

Regarding the initial point, all methods start from the same initialization for each seed, as described in Appendix E.1. We also use the same seed-generated initial point across different values of ρ\rho.

As you correctly observe, changing ρ\rho changes the objective itself, so the condition number, initial objective value, and initial gradient norm can also change. However, our experiments are not designed to directly compare the performance of the same method across problems with different values of ρ\rho. Instead, for each fixed ρ\rho, we compare the relative performance of RS-NSGD, NSGD and the other methods. Section 5.1 reports such within-problem comparisons: RS-NSGD outperforms NSGD in oracle complexity for ρ∈{4,20}\rho\in\lbrace4,20\rbrace, whereas NSGD is favored for ρ=100\rho=100. The aim of this experiment is to show that this trend in relative performance is compatible with our theory.

Please let us know if we have misunderstood your concern.

Question 3: Budget selection, iteration counts, and longer horizons

Please see our combined response to Critical weaknesses 2–3 for the budget selection and the interpretation of the differing iteration counts. You are right that extending the training horizon could change the methods’ relative rankings. Since stability across all training horizons is generally difficult to guarantee, we make no such claim. For the reasons explained in our combined response to Critical Weaknesses 2–3, the experiments in the main paper compare optimization performance under the chosen common oracle budget.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Additional Experimental Results

Revision to the manuscript. We have added an experiment comparing the modeled times required for RS-NSGD, full-dimensional NSGD, and majority-vote signSGD to reach common loss targets, using measured computation and modeled communication times (Section 5.2, Table 3; Appendix G, Tables 7–8). A related theoretical comparison with sign-based methods under heavy-tailed noise is already provided in Appendix A.4. We have also added citations to Agarwal et al. (2022) and Duan et al. (2023), which use a similar evaluation approach, in Section 5.2 and Appendix G. The new additions are highlighted in blue in the revised manuscript.

This experiment was motivated primarily by Reviewer QXL1's concerns about practical relevance and comparisons with communication-efficient optimization methods. However, we believe the results may also be useful to the other reviewers and area chairs, so we would like to briefly share them here. We evaluate RS-NSGD on PTB and WikiText-2 by combining measured single-GPU computation times with modeled four-worker communication times. Further experimental details are provided in Appendix G.

Comparison with full-dimensional NSGD. As shown in Table 3, with r=50r=50, RS-NSGD reaches the same loss target in less modeled total time than full-dimensional NSGD across all six tested bandwidths on both datasets. At 10 Mbps, the speedups are 5.77-fold on PTB and 27.23-fold on WikiText-2. At 1 Mbps, they increase to 27.77-fold and 142.12-fold, respectively. These results demonstrate that communication savings can more than compensate for the additional computation and iterations associated with subspace updates.

Comparison with majority-vote signSGD. As shown in Table 3, RS-NSGD also achieves meaningful efficiency gains over majority-vote signSGD, which communicates one bit per gradient coordinate. With r=50r=50, the speedup on WikiText-2 increases from 1.65-fold at 10 Mbps to 8.56-fold at 0.001 Mbps. On PTB, RS-NSGD becomes faster at bandwidths of 1 Mbps and below, achieving a 1.59-fold speedup at 0.001 Mbps.

Further experimental results are provided in Appendix G.

In these comparisons, as in the existing papers (Agarwal et al., 2022; Duan et al., 2023), we combine measured computation times with modeled communication times (rather than physically measured ones). They provide concrete empirical evidence that the reduction in communicated gradient information can translate into meaningful efficiency gains over both full-dimensional NSGD and one-bit majority-vote signSGD.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.