acceptodds
Under review as a conference paper at ICLR 2027

Accelerating Stochastic Schatten Momentum Descent Against Unbounded Gradient Noise

Abstract

Matrix optimizers which exploit the spectral geometry are increasingly getting adopted for training large transformer based models. Inspired by these successes we seek to build foundations for these novel ML algorithms. Thus we are led to study a notion of stochastic Schatten momentum descent with Exponential Moving Average (EMA) and Momentum Variance Reduction (MVR). We introduce a generalized notion of smoothness and an affinely growing bound on the variance of stochastic gradient differences, both defined in the Schatten norm. Under these relaxed conditions of gradient smoothness and unbounded gradient noise, we prove (a) an optimal convergence rate for the variance reduced form of our algorithm by exploiting the aforementioned control on stochastic gradient differences and (b) a rate for the EMA variant. We further extend the EMA guarantee to Polyak's heavy-ball momentum, and thus getting new guarantees on the idealized stochastic Muon algorithm.

Primary area:
optimization
Keywords:
Optimization, Convergence Analysis

Reviews

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

The paper studies stochastic momentum methods that choose update directions from Schatten norm balls, including an idealized Muon direction as a special case. It proves an O(T−1/3)O(T^{-1/3}) bound on the average expected gradient norm for a momentum variance reduction (MVR) method under generalized smoothness, gradient dependent noise, and a centered gradient difference condition. EMA and heavy ball momentum obtain an O(T−1/4)O(T^{-1/4}) bound without the gradient difference condition. Experiments compare MVR and EMA on DeiT-Tiny and GPT-2. MVR performs better in some runs using theorem-scaled parameters, whereas EMA generally reaches a lower final loss with the empirical settings.

Overall, I find the extension to gradient dependent noise technically interesting, but I am not yet convinced that the paper makes a strong enough case for acceptance. Related MVR methods already obtain the O(T−1/3)O(T^{-1/3}) rate in arbitrary norm settings, so the value of this paper rests largely on the scope of its new assumptions. I would like to see a concrete problem where those assumptions hold together, and a comparison that accounts for MVR’s two gradient evaluations per step. I am currently on the borderline ( leaning reject), but could revise my assessment if the authors address these points.

Critical strengths
  1. The paper addresses a useful limitation of existing analyses: gradient noise need not have uniformly bounded variance. The centered gradient difference condition also targets the quantity used by the MVR proof.
  2. The average-iterate guarantee is a meaningful part of the result. Together with the treatment of different Schatten norms, it makes the theoretical contribution more specific than the headline rate alone suggests.
  3. The experiments report cases where EMA outperforms MVR. This helps readers distinguish the convergence guarantee from the observed training performance.
Critical weaknesses

My main question is how often the assumptions behind the MVR result hold in the intended applications. Assumption 4 places a particular It is hard to assess the reach of the main theorem without a worked learning problem satisfying the smoothness, affine noise, and centered gradient difference assumptions together. In particular, an example where bounded variance fails would make the gain over earlier analyses much more concrete.

The empirical comparisons are plotted against updates, although MVR evaluates a fresh sample’s gradient at two parameter values per update. A comparison by gradient evaluations or wall-clock time could change the practical interpretation.

The GPT-2 empirical runs use approximate matrix directions and AdamW for the remaining parameters, while the theorem analyzes exact Schatten directions. The paper should be clearer about what these runs illustrate. The single-seed DeiT-Tiny and empirical GPT-2 results also make small differences difficult to judge.

Questions for authors
  1. Can the authors give a concrete stochastic learning model satisfying Assumptions 3–5 in which gradient-noise variance is unbounded?
  2. How do MVR and EMA compare at equal gradient-evaluation or wall-clock budgets, with variability across seeds?
  3. How sensitive are the GPT-2 results to the accuracy of the power-iteration and Newton–Schulz directions?
1 comment

We thank the reviewer for taking the time to review our work and for their helpful feedback. We address the weaknesses and questions:

W1/Q1. An example where bounded variance fails. Appendix B of the revision gives an example with a quadratic population objective that satisfies Assumptions 3-5. Its single-point gradient-noise variance is unbounded, and its centered same-sample gradient-difference second moment grows without bound even when the two query points stay a fixed distance apart. Thus, the example violates both the commonly used uniform variance bound and the constant-coefficient centered gradient-difference bound while satisfying the general conditions introduced and used in this work.

W2/Q2. Additional experimental comparison.

We have added three-seed comparisons on two related tasks, ResNet-32 on CIFAR-10 and GPT-2 small on Tiny Shakespeare. The curves report the mean and min-max range across seeds (Figure 1-2 in Section 4). We now also report learning curves for MVR and EMA under the same budget of minibatch-gradient evaluations (Figure 11 in Appendix E.3 and Figure 12 in Appendix E.4).

Our available compute limits the number of seeds for the original DeiT-Tiny and empirical GPT-2 runs.

On CIFAR-10, EMA achieves lower mean test loss for p=1p=1 and p=∞p=\infty, while the two methods have nearly identical test loss for p=2p=2 (0.4480.448 for MVR and 0.4460.446 for EMA).

On Tiny Shakespeare, EMA achieves lower final training and validation losses for all three values of pp at batch size 1616.

These results are qualitatively consistent with the original experiments under empirical settings, where EMA generally achieved comparable or lower held-out loss. Our theoretical rate concerns first-order stationarity of the population objective, whereas these experiments probe an aspect outside the ambit of our theory i.e comparing held-out loss within a finite training budget.

W3/Q3. Approximate Schatten directions and sensitivity in GPT-2. Muon-style language model training commonly uses Newton--Schulz iterations to compute updates for hidden weight matrices and AdamW for the remaining parameters, including embeddings and normalization parameters. Power iteration is also used to approximate leading singular directions of gradient matrices in neural network training. Computing a full SVD for every matrix block at every update would substantially increase the cost of our GPT-2 runs, so we use iterative approximations for p=1p=1 and p=∞p=\infty.

The GPT-2 experiments is to compare MVR and EMA as two ways of forming the momentum estimate used in the Schatten update. For each pp, we apply the same direction solver to the two momentum estimates and use a single iteration count shared by both methods when the solver is approximate. Both methods use identical AdamW settings for the remaining parameters.

Reviewer_gHnJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The manuscript accelerating stochastic Schatten momentum descent against unbounded gradient noise studies the convergence of Stochastic Schatten Momentum Descent (SSMD) under affine noise. The authors study SSMD with different momentum, and show that under certain assumptions, the convergence of SSMD with Exponential Moving Average momentum is O(\eps^{-4}) and of SSMD with Momentum Variance Reduction (MVR) is O(\eps^{-3}). Experiments on image classification and LLM pretraining are used to compare proposed methods.

Critical strengths
  1. The theorems are interesting. To the best of my knowledge the theorems are new.

  2. Most assumptions are reasonable.

Critical weaknesses
  1. The numerical experiments and the theory seem somewhat disconnected. Most assumptions and convergence results were not empirically verified. The proposed MVR algorithm seems not practical in large-scale learning due to the requirement of one extra gradient on the same batch.
Questions for authors
  1. I am not an expert on this specific topic so I could not tell if the proofs really involve some innovative strategies or are just incremental.

    • If the proofs are already strong enough, the current experiments seem unnecessary. I think they mostly suggest limited practical value of the algorithms rather than supporting the theorems.
    • Otherwise, adding some empirical experiments on the assumptions (like assumption 4) and noise behavior on real problems would be very interesting.
  2. Other small issues could be checked and fixed. For example Table 5 lists lr=0.02 for GPT-2 but the search range is {0.01,0.03,0.05,0.07,0.1}.

3 comments

We appreciate the reviewer's thoughtful comments and suggestions. We address the weaknesses and questions:

W1.Theory and Practical Gap. Since earlier works like in NSVRG it has been known that variance reduction mechanism can reduce performance in terms of accuracy and loss [1]. At equal wall-clock time, uniform-sampling SGD outperformed SVRG and related methods on CIFAR-10 and CIFAR-100 [2]. A related MVR result comes from ViT training on Tiny-ImageNet, where Muon++ achieved 43.62%. validation top-1 accuracy versus 47.87% for Muon, and took 9 min 54 s to reach the target loss versus 7 min 6 s for Muon [3, Tables 4–5].

Thus, our experiments comparing MVR and EMA are align with what classically known about variance reduction hurting performance while having theoretically optimal convergence speed. Though we do report a couple of cases where MVR outperforms EMA - as summarized on page 4.

Q1. What is new in the proof, and what evidence supports the relaxed noise assumptions? We note that in Section 1.1 (Table 1) we have pointed out how our Theorem 3 achieves the optimal O(T−1/3)O(T^{-1/3}) stationarity rate and Theorem 4 achieves the O(T−1/4)O(T^{-1/4}) stationarity rate under strictly weaker assumptions on the stochastic gradient noise among all other works on Schatten momentum. Thus our key contribution is the introduction of the unbounded variance stochastic oracles under which Schatten momentum based algorithms continue to converge at optimal rates - thus elucidating the noise robustness of this framework that is increasingly getting deployed.

Appendix B of the revision gives an example with a quadratic population objective that satisfies Assumptions 3-5. Its single-point gradient-noise variance is unbounded, and its centered same-sample gradient-difference second moment grows without bound even when the two query points stay a fixed distance apart. Thus, the example violates both the commonly used uniform variance bound and the constant-coefficient centered gradient-difference bound while satisfying the new relaxed assumptions introduced.

Q2. GPT-2 learning-rate mismatch between Table5 and the search list. The original draft omitted the 0.020.02 peak learning rate reported in Table~5 from the search list. We have corrected the list in the revision to include 0.020.02.

[1] Defazio and Bottou. On the Ineffectiveness of Variance Reduced Optimization for Deep Learning. NeurIPS 2019.

[2] Katharopoulos and Fleuret. Not All Samples Are Created Equal. ICML 2018.

[3] Huang et al. LiMuon: Light and Fast Muon Optimizer for Large Models. ICML 2026.

Thank you to the authors for the response and clarification. However, some of the responses did not directly address my comments. The demonstrated practical value remains limited, and the added example does not empirically examine the assumptions or noise behavior on real problems. Therefore, I keep my score unchanged.

AuthorsOpenReview ↗

Clarifications

Kindly note that the demonstrations are a minor and insignificant part of this paper. The experiments are designed as just a sanity check about how close MVR gets to EMA in these modern optimizer setups applied to these modern transformer based architectures.

Please also note that both MVR and EMA are our algorithms and our key theory proves convergence for both of them in this generalized Schatten geometry assumptions and unbounded noise - a first of its kind setting.

Since the earliest papers in 2017, it is well known that variance reduction hurts performance while giving optimal convergence speeds. So the experimental fact that MVR lags EMA in performance is entirely unsurprising and was entirely expected by us before we did the experiments. But it's of interest that in some of our cases MVR does outcompete EMA.

Research into variance reduction based training algorithms is rarely motivated by practical deployment. Thats why we show proofs for MVR as well as EMA, the later being deployable for performance benefit.

We request that our paper by judged as pure theory/maths paper whose contribution lies in doing these sophisticated convergence analysis in this setting which is significantly weakly constrained compared to all other concurrent literature on Muon-type algorithms.

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

The paper extends analyses of momentum-based approaches under Schatten geometries, relevant to Muon (a recent optimizer). It analyzes two momentum variants, EMA and MVR, under extended noise and smoothness assumptions. Specifically, it assumes affine stochastic noise rather than uniformly bounded variance, and δ0,δ1\delta_0, \delta_1-smoothness not only at the objective level but also at the sample level. It also provides convergence results of O(T1/3)O(T^{1/3}) for MVR and O(T1/4)O(T^{1/4}) for EMA. It also includes experiments on CIFAR-100 and GPT-2.

Critical strengths
  • The paper extends existing non-convex analysis to extended noise and sample-level smoothness assumptions while retaining known iteration complexity.
  • The paper provides empirical evaluation on complex setups.
Critical weaknesses
  • I would appreciate a clearer explanation of the novelty and contribution of this work. Since Qian et al. (2025, Theorem 2) already established the same rate for MVR under (L0,L1)(L_0,L_1)-smoothness, it would be helpful to clarify the significance of the sample-level (δ0,δ1)(\delta_0,\delta_1)-smoothness assumption and the additional analytical challenges introduced by affine variance. This would help me better assess the advance over existing results.
  • It's also important to show that, when δ1=σ1=0\delta_1=\sigma_1=0, Theorems 3 and 4 recover the previous results with matched dimension (rr) comparison. Could the authors compare their results to Theorem 2 in Qian et al. (2025)?
  • The experiments do not reflect the MVR improvement in contrast to theory, which I think is also in contrast to existing MVR empirical results; can the authors explain why?
  • The experiments were run on one seed, which can be less reliable in language tasks.
Questions for authors

see weaknesses above

3 comments

We thank the reviewer for their careful reading and constructive feedback. We address the weaknesses and questions:

W1. Explanation of the contribution. We note that in Section 1.1 (Table 1) we have pointed out how our Theorem 3 achieves the optimal O(T−1/3)O(T^{-1/3}) stationarity rate and Theorem 4 achieves the O(T−1/4)O(T^{-1/4}) stationarity rate under strictly weaker assumptions on the stochastic gradient noise among all other works on Schatten momentum. Thus our key contribution is the introduction of the unbounded variance stochastic oracles under which Schatten momentum based algorithms continue to converge at optimal rates - thus elucidating the noise robustness of this framework that is increasingly getting deployed.

The paragraph following Assumption 4 in Section 3 states the difference in the centered gradient-difference condition. Qian et al. (2025, Theorem 2) establish an O(T−1/3)O(T^{-1/3}) stationarity rate for Gluon-MVR under a uniform bound on the stochastic-gradient variance and a constant coefficient in the same-sample centered gradient-difference bound (their Assumptions 6 and 8).

In the single-block Schatten setting, their variance bound corresponds to our Assumption 5 with σ1=0\sigma_1=0, and their gradient-difference bound corresponds to our Assumption 4 with δ1=0\delta_1=0 after converting between the Frobenius and Schatten-qq norms. Our Assumption 4 allows the coefficient in the RMS bound to grow affinely with the largest population-gradient norm along the segment between the two query points. Assumption 5 allows the single-point variance bound to grow affinely with ∥∇F(W)∥Sq2\|\nabla F(W)\|_{S_q}^2.

The newly added example in Appendix B has a quadratic population objective and satisfies both the affinely bounded noise variance conditions we introduce while violating the constant bounds that are conventionally used.

W2. When δ1=σ1=0\delta_1 = \sigma_1 = 0, Theorems 3 and 4 recover the previous results. In the common single-block setting, let ρq=rmax⁡{1/q−1/2,0}\rho_q=r^{\max\{1/q-1/2,0\}}. Qian et al.'s Frobenius difference bound with coefficient δQ\delta_{\mathrm Q} implies our Assumption 4 with δ0=ρqδQ\delta_0=\rho_q\delta_{\mathrm Q} and δ1=0\delta_1=0. Their single-point variance bound gives σ1=0\sigma_1=0. Under their unclipped SpS_p-to-SqS_q smoothness condition, using the Frobenius difference bound directly in the constant-noise tracking recursion gives the same single ρq\rho_q factor in the stochastic terms. The rates are O(T−1/3)O(T^{-1/3}) for MVR and O(T−1/4)O(T^{-1/4}) for EMA, matching their Theorems 2 and 6, respectively. Our general clipped bounds carry additional norm-conversion factors and control the average expected gradient norm, while Qian et al. bound the minimum over iterations.

Thus our results subsume the reported rates of Qian et. al. as special cases.

W3. Theory and Practical Gap. Since the earliest works like in NSVRG [1] it has been known that variance reduction mechanism can reduce performance in terms of accuracy and loss [2]. At equal wall-clock time, uniform-sampling SGD outperformed SVRG and related methods on CIFAR-10 and CIFAR-100 [3]. A related variance reduction based result comes from ViT training on Tiny-ImageNet, where Muon++ achieved 43.62%. validation top-1 accuracy versus 47.87% for Muon, and took 9 min 54 s to reach the target loss versus 7 min 6 s for Muon [4, Tables 4–5].

Thus, our experiments comparing MVR and EMA are aligned with what is classically known about variance reduction hurting performance while having theoretically optimal convergence speed. Though we do report a couple of cases where MVR outperforms EMA - as summarized on page 4.

W4. Additional experiment We added three-seed comparisons for ResNet-32 on CIFAR-10 (Fig. 1 in Sec. 4) and GPT-2 on Tiny Shakespeare (Fig. 2 in Sec. 4) and under a common budget of 1,000 minibatch-gradient evaluations (Fig. 11 and 12 in Appendix E.4). The curves show the mean and min–max range across seeds. At the reported endpoints, EMA achieves comparable or lower mean held-out loss, consistent with the original empirical results. Compute constraints have made us limit the original DeiT-Tiny runs (Figs. 3–4 in Appendix E.1) and empirical FineWeb runs (Fig. 8 in Appendix E.2) to one seed per configuration.

[1] Reddi et al. Stochastic Variance Reduction for Nonconvex Optimization. ICML 2016.

[2] Defazio and Bottou. On the Ineffectiveness of Variance Reduced Optimization for Deep Learning. NeurIPS 2019.

[3] Katharopoulos and Fleuret. Not All Samples Are Created Equal. ICML 2018.

[4] Huang et al. LiMuon: Light and Fast Muon Optimizer for Large Models. ICML 2026.

Thank you for the clarification and the additional experiments. However, the wall-clock comparisons do not explain the results in Figure 1, where the methods use the same number of epochs and optimizer updates. MVR generally has a higher training loss under the same number of training steps. I will therefore keep my score unchanged.

AuthorsOpenReview ↗

Clarifications

Kindly note that the demonstrations are a minor and insignificant part of this paper. The experiments are designed as just a sanity check about how close MVR gets to EMA in these modern optimizer setups applied to these modern transformer based architectures.

Please also note that both MVR and EMA are our algorithms and our key theory proves convergence for both of them in this generalized Schatten geometry assumptions and unbounded noise - a first of its kind setting.

Since the earliest papers in 2017, it is well known that variance reduction hurts performance while giving optimal convergence speeds. So the experimental fact that MVR lags EMA in performance is entirely unsurprising and was entirely expected by us before we did the experiments. But it's of interest that in some of our cases MVR does outcompete EMA.

Research into variance reduction based training algorithms is rarely motivated by practical deployment. Thats why we show proofs for MVR as well as EMA, the later being deployable for performance benefit.

We request that our paper by judged as pure theory/maths paper whose contribution lies in doing these sophisticated convergence analysis in this setting which is significantly weakly constrained compared to all other concurrent literature on Muon-type algorithms.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Our Main Contribution

We would like to clarify that our main contribution is to obtain the optimal rate O(T−1/3)O(T^{-1/3}) of first-order stationarity guarantee for Schatten momentum descent (which generalizes the Muon algorithm) despite relaxing the gradient noise assumptions to allow unbounded variance for it --- a first-of-its-kind result demonstrating the significant noise robustness of Schatten norm based training algorithms, which are rapidly becoming popular in practice.

In particular, the MVR algorithm in the text uses Assumptions 4 and 5 and implements a variance reduction strategy to obtain this novel convergence. Assumption 4 allows the coefficient in the root-mean-square bound on centered same-sample gradient differences to grow affinely with the largest population-gradient norm along the segment between the two query points. Assumption 5 allows the single-point variance bound to grow affinely with the squared population-gradient norm. Also our proof works in clipped-Schatten smoothness setting which always defaults to the weakest assumption.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.