- 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 -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 , i.e. by full-dimensional NSGD. In the parameter-agnostic regime, RS-NSGD obtains an asymptotic improvement when , but the finite-order bound also contains unfavorable dimension/subspace-dependent terms (e.g., a term), while the 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 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 regime, whereas in the parameter-aware regime the derived bound is minimized by . 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
Thank you for your response. Most of my concerns have been addressed, and I will therefore maintain my original positive assessment.
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 d to r. 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 p 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.