acceptodds
Under review as a conference paper at ICLR 2027

Convergence of Muon under Random Reshuffling

Abstract

Muon, an optimizer that orthogonalizes its momentum matrix, is increasingly used to train large models, often with several passes over a fixed data pool under random reshuffling (RR), which visits every example once per pass. For stochastic gradient descent, the number of gradient evaluations needed for gradient norm at most scales as under sampling with replacement (IID) and as under reshuffling. Whether this gain carries over to Muon's nonlinear update was open, since RR proofs need updates linear in the sampled gradients and Muon's existing rates assume IID sampling. We give, to our knowledge, the first finite-horizon stationarity guarantee for Muon under RR on smooth nonconvex finite sums, assuming only that each component is smooth and bounded below. The sufficient query budget retains the dependence of reshuffled SGD. The proof tracks the momentum buffer before orthogonalization, where sampling noise cancels over each pass, and a potential-function argument controls the changing spread of the component gradients. In language-model training on a fixed data pool, RR reaches lower training and validation loss than IID after the same number of updates.

Primary area:
optimization
Keywords:
Muon, random reshuffling, nonconvex finite-sum optimization

Reviews

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

The paper analyzes Muon (with exact polar factor and classical momentum) under random reshuffling (RR) on smooth nonconvex finite sums. Theorem 1 gives a finite-horizon bound on the expected nuclear norm of the gradient under the assumption of component smoothness in the operator-nuclear norm pair and component lower bounds, with no uniform variance assumption. The budget retains the ε−3\varepsilon^{-3} dependence of RR-SGD, against ε−4\varepsilon^{-4} for an IID Muon bound.

Validation consists of a 124M-parameter language model trained on a fixed pool of 16.8M tokens (RR vs IID, five paired seeds, with replicated list controls), plus a small synthetic check of the buffer-tracking mechanism.

Critical strengths
  1. The work provides the first proof covering convergence of Muon under RR, relying on standard assumptions.

  2. The paper is relatively honest about the theory-practice gap. For example, it reports that the experimental β\beta lies outside the theorem conditions and that the proved frozen-noise reduction is only 3.71% there.

Critical weaknesses
  1. The theory and the experiments do not meet, and the bound is uninformative at practical horizons. The theorem's regime is the worst-performing one in practice. It needs N(1−β)≤1N(1-\beta) \leq 1, so β≥0.99902\beta \geq 0.99902 for N=1024N = 1024. In the authors' own pilot (Table 3), β=0.9995\beta = 0.9995 gives the worst training AUC at every learning rate (e.g., at learning rate 0.005 it gives 5.23, against 4.03 at β=0.95\beta = 0.95). Moreover, the bound is uninformative for realistic K (see the section below). Overall, the theory does not explain the observed RR gains, and the experiments do not test the theorem. Presenting them as mutually supporting overstates the case.

  2. The reshuffling advantage carrying over to Muon is not established. Section 4.3 compares upper bounds under different assumptions. The RR bound uses component smoothness and lower bounds and has a N\sqrt{N} factor, so it beats the IID bound only below an accuracy threshold. The IID bound uses a uniform variance bound and is the authors' re-derivation of prior results (Prop. 5). Section 4.3 and Appendix F do state that this is no lower-bound separation though.

Questions for authors
  1. As I understand current practice, LLM pretraining is mostly at most 1 pass, and fine-tuning usually runs 1-3 epochs. Even data-constrained pretraining is useful up to a few passes. So realistic values are K≈1K \approx 1-44. The paper's own LM experiment uses K=8K = 8, which is already beyond common practice. At those values the bounds in the main results say nothing. The theorems become informative only after about 10510^5-10610^6 epochs. The advertised ε−3\varepsilon^{-3} versus ε−4\varepsilon^{-4} gap likewise sits in the limit of many passes. The motivating story therefore does not match the result. The introduction cites fine-tuning and data-constrained pretraining, which have a handful of passes. The analysis describes what happens after thousands. Given this, could the authors provide some examples of when the theoretical results of the paper are useful?

  2. Novelty seems to be very incremental. The proof ingredients are standard (Mishchenko et al.'s RR identity and self-bound, EMA unrolling, first-moment tracking of Cutkosky-Mehta, and a potential with a self-bounding variance of Shulgin et al.). Given this and the point above, could the authors explain the motivation behind the analysis?

4 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for your careful review and for recognizing the first RR convergence proof and our effort to state its limits clearly. We address practical momentum, informative few-pass bounds and training evidence here. Our second comment covers the RR–IID comparison, the proof contribution and an additional fixed-pass guarantee.

RR convergence beyond few-pass LLM training

Usefulness beyond few-pass LLM training. Our theorem concerns repeated-pass RR optimization of general smooth nonconvex finite sums, including learning problems beyond language models. Repeated data reuse over many epochs is part of this setting. At fixed component count and problem constants, the ε−3\varepsilon^{-3} sufficient query budget, compared with the ε−4\varepsilon^{-4} IID bound under the stated assumptions, describes the cost of reaching tighter stationarity targets. We added a 20-epoch ViT experiment alongside the short LM runs. The explicit bounds below separately answer your request for numerically informative few-pass bounds.

Momentum restriction and practical training. We give a priori finite-horizon residual bounds at every fixed 0≤β<10\le\beta<1, including 0.950.95, without N(1−β)≤1N(1-\beta)\le1. Here NN counts finite-sum components. The bounds track moving gradients under component operator–nuclear smoothness and lower bounds, without uniform variance. They assume deterministic initialization, zero buffer and independent uniform RR epochs, without decay.

The 3.71% frozen squared-noise reduction holds at fixed weights, so it does not bound training-loss gains. The horizon-dependent momentum optimizes a worst-case guarantee, whereas the pilot compares finite-budget loss. The pilot therefore addresses a different question from the worst-case guarantee.

Informative theoretical bounds at one to four passes. Take fj(x)=12(x+cj)2+2(1−cos⁡x)f_j(x)=\tfrac12(x+c_j)^2+2(1-\cos x) with balanced cj=±0.01c_j=\pm0.01, x0=1x_0=1 and N=1024N=1024. The components are nonnegative, globally smooth and nonconvex. With β=0.95\beta=0.95, raw LR 0.00280.0028 and zero buffer, five Jordan Newton–Schulz steps (NS5) with Nesterov momentum give these mean pre-update gradient-norm bounds

PassesProved upper bound
11.678
21.219
31.065
40.989

All are below the initial norm greater than 2.68. This example additionally requires bounded component-gradient deviations, exact zero-guard Frobenius normalization and no decay or stabilizer. The bound holds for every ordering, so it is not an RR–IID separation.

Independent experiments across training budgets. Positive IID−RR differences in normalized full-pool train CE AUC favor RR.

SettingMean AUC gain ± paired SDRR wins
FineWeb-Edu, 1 pass0.021563 ± 0.0044825/5
FineWeb-Edu, 2 passes0.020817 ± 0.0031675/5
FineWeb-Edu, 4 passes0.011861 ± 0.0016165/5
CIFAR-10 ViT, 20 epochs0.043569 ± 0.0047555/5

Each arm selects LR on two development seeds with equal tuning budgets, then uses five fresh paired confirmation seeds per setting. Both select LR 0.010.01 for FW1, 0.0050.005 for FW2/FW4 and 0.0006250.000625 for ViT. FW2 has its own tuning and 2,048-update horizon, not a FW4 prefix. Each FW pass uses 32,768 sequences, context 512 and 1,024 updates. All use NS5-Nesterov, β=0.95\beta=0.95, decay 0.10.1 and side AdamW. ViT trains for 7,000 updates without augmentation or dropout. Held-out and confirmation results never select LR. AUC includes initialization with five equally spaced LM evaluations or 21 ViT epoch boundaries. SD is paired sample SD, not a confidence interval.

The ViT result extends the practical evidence beyond short LM runs. These loss comparisons do not certify neural-network stationarity or the causal share of gains due to buffer cancellation. The horizons are separate experiments, not paired interventions on pass count.

Proofs for the residual and scalar bounds are in revised Appendices K–L. Protocols and seed records are in O.1 and the supplementary materials.

AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Thank you also for asking us to clarify the RR–IID comparison and the motivation for the analysis. Below we clarify the comparison and proof contribution, then give the additional fixed-pass result.

RR–IID comparison, proof contribution and additional theory

RR and IID under compatible assumptions. The same component assumptions also permit an IID comparison without uniform variance. If g(W)g(W) is a fresh uniformly sampled component gradient and ℓˉ\bar\ell is the average component lower bound, component smoothness gives E∥g(W)∥F2≤2L(f(W)−ℓˉ).\mathbb E\lVert g(W)\rVert_F^2\le2L\bigl(f(W)-\bar\ell\bigr). Thus the sampled second moment is controlled by the current objective gap. This is the condition used by the IID momentum-LMO analysis of [2].

At fixed component count NN and other nondegenerate problem constants, the sufficient component-gradient query budgets have accuracy dependence TRR=O(ϵ−3),TIID=O(ϵ−4).T_{\rm RR}=O(\epsilon^{-3}),\qquad T_{\rm IID}=O(\epsilon^{-4}). Here TT counts component-gradient evaluations and ϵ\epsilon is the target expected nuclear-gradient norm of an independently uniform pre-update output. We also rederive the credited bounded-variance IID Muon rate [1], without claiming it as new.

The conclusion is an improved accuracy exponent for a sufficient guarantee. The RR budget retains its N\sqrt N cost. Against the original bounded-variance IID comparator, its leading terms cross at an accuracy scale proportional to r/N\sqrt{r/N} when the other positive constants are fixed. The shared-component comparison has the same accuracy exponents with its own moment constants. The separate fixed-pass, growing-NN result neither removes the cost nor gives an ϵ−3\epsilon^{-3} few-pass complexity guarantee. A matching RR–IID lower-bound separation remains a separate theoretical question.

Why the analysis is needed and which step is new. The aim is to establish convergence for Muon under reshuffling with momentum carried across passes, a setting not covered by its IID analyses. An RR identity alone controls cancellation before orthogonalization. It does not show that Muon's nonlinear direction still gives descent when both the parameters and component-gradient spread change within a pass.

Our analysis supplies that connection. A potential with coefficients matched to momentum contraction controls the incoming buffer error together with the objective gap and gradient spread. This preserves the cancellation benefit through the nonlinear update without resetting momentum, adding full-gradient anchors or caching gradients. Treating the correlated samples as fresh IID noise would lose the extra cancellation factor.

We use the RR identities and component self-bounds of [3], the first-moment momentum tracking of [4], and the self-bounding linear-minimization-oracle tools of [2]. The contribution is the argument that makes these controls work together for RR Muon while retaining that factor. The exact-polar proof separates this difficulty from approximate orthogonalization, and direct direction-alignment bounds extend the argument to the specified Newton–Schulz variants.

Additional fixed-pass guarantees. We also prove O(N−1/4)O(N^{-1/4}) expected pre-update stationarity for exact polar without decay at fixed pass count KK, matrix shape and common L,HL,H. Here LL is component operator–nuclear smoothness, HH the initial gap to the average component lower bound, and rr the smaller matrix dimension. For N≥max⁡{2,rK}N\ge\max\lbrace2,rK\rbrace, use β=1−(rKN)−1/2\beta=1-(rKN)^{-1/2} and an explicit H,LH,L-dependent stepsize. Thus N(1−β)>1N(1-\beta)>1 when N>rKN>rK. Initialization is deterministic, the buffer is zero and RR epochs are independent and uniform. Momentum varies with NN. This is not a vanishing rate at fixed β=0.95\beta=0.95.

A controlled nonconvex quadratic-plus-cosine example uses 16×816\times8 matrices, N=222N=2^{22} nonnegative components, globally unbounded component-gradient variance, classical exact polar and zero buffer.

One-pass nuclear-gradient quantityValue
Initial norm≈31.23\approx31.23
Expected pre-update mean, proved upper bound≤26.62\le26.62

The initial norm is rounded. The bound is rounded upward. This is a theoretical guarantee, not an RR–IID comparison.

Full statements and proofs are in revised Section 4.4 and Appendices E–F, I–J and N. The matrix certificate and its arithmetic checks are in O.3 and the supplementary materials.

References

[1] Kim and Oh (2026). Convergence of Muon with Newton-Schulz. ICLR.

[2] Shulgin et al. (2026). General Analysis of LMO-based Optimizers: Beyond Bounded Variance. ICML.

[3] Mishchenko et al. (2020). Random Reshuffling: Simple Analysis with Vast Improvements. NeurIPS.

[4] Cutkosky and Mehta (2020). Momentum Improves Normalized SGD. ICML.

Thank you for the detailed rebuttal and the additional results.

My main concern, however, remains. Theorem 1 is still uninformative at the small numbers of passes used in practice, and the new results do not change this. The one-to-four-pass certificate is for a scalar, essentially deterministic problem under an additional bounded-deviation assumption, and it holds for any ordering, so it does not concern reshuffling. The fixed-momentum bounds (Appendix K) are residual bounds that do not vanish with KK. The fixed-pass result (Theorem 3) has rate N−1/4N^{-1/4}, the same order as the IID bound at the same number of queries. Taken together, these results seem to confirm that the theory does not explain the gains seen in practice. The new experiments strengthen the empirical comparison between RR and IID, but this advantage has already been widely observed for SGD and was already shown for Muon in your main experiment. They do not address my question.

I therefore keep my score.

Dear Reviewer 1Ltf,

Thank you for clarifying your concern about whether the theory explains the gains observed in few-pass language-model training. This setting is one motivation for our work. Our main result establishes a stationarity guarantee for Muon under random reshuffling over repeated passes through a fixed dataset.

The known reshuffling results for SGD do not directly yield this guarantee because Muon applies a nonlinear polar map to momentum carried across passes. Our proof tracks the partial cancellation of sampling noise in the buffer before orthogonalization. By jointly controlling the objective gap and the buffer error, we show how this cancellation sharpens the descent bound for Muon’s nonlinear update.

We would be grateful if you would weigh this theoretical contribution alongside your concern about few-pass training in your final assessment. Thank you again for your careful review.

Sincerely,
The authors

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

The paper studies Muon with a momentum buffer carried across epochs under random reshuffling of a fixed finite sum. Under componentwise operator–nuclear smoothness and lower bounds, it proves an expected nuclear-gradient stationarity bound of order LH[K−1/2+r1/6K−1/3N−1/6]\sqrt{LH}[K^{-1/2}+r^{1/6}K^{-1/3}N^{-1/6}] for horizon-dependent momentum and stepsize choices, where K counts epochs, N counts fixed components, r is the smaller matrix dimension, and H is the initial gap above the average component lower bound. The analysis preserves cancellation in the unorthogonalized buffer and controls changing gradient heterogeneity through a joint objective-gap and buffer-error potential, without a uniform variance assumption. It also gives an exact-arithmetic fixed-depth Jordan-quintic extension and a self-contained IID comparison. Language-model experiments report lower losses under reshuffling at matched update budgets, while a synthetic study measures the buffer-tracking mechanism.

Critical strengths
  • The combination of endpoint noise cancellation and joint stability is a consequential theoretical contribution. Corollary 1 gives a frozen-noise coefficient of order λ4/N\lambda^4/N, and Lemmas 8–10 preserve its benefit through carried momentum while controlling heterogeneity from component lower bounds. This supports a finite-horizon ε−3\varepsilon^{-3} sufficient query bound at fixed positive problem parameters for the nonlinear polar method without resets or extra gradient corrections.

  • The empirical comparison includes a separate pilot, five paired confirmation seeds and replicated-list controls at matched budgets. Reporting these controls alongside intermediate reversals, validation minima and timing limits makes the practical evidence useful and strengthens the case that sampling deserves attention beyond the theorem's setting.

Critical weaknesses
  • The theoretical mechanism has limited explanatory reach for the principal training experiment. The schedule requires N(1−β)≤1N(1-\beta)\le 1 and momentum chosen from the horizon, whereas the selected experiment has N=1024N=1024 and β=0.95\beta=0.95, giving N(1−β)=51.2N(1-\beta)=51.2; its frozen squared-noise coefficient is only about 4% smaller than IID's (Appendix D.2).

  • The dimension benefit is conditional on the smoothness geometry. At fixed Frobenius smoothness LFL_F, the general substitution L=rLFL=rL_F changes the slow term's rank dependence from r1/6r^{1/6} to r2/3r^{2/3} (Appendix C.1). The paper states this convention explicitly, so this is a limitation of the result's general comparative advantage rather than an omitted assumption.

Questions for authors
  • Beyond the frozen coefficient in Appendix D.2, do the existing tracking inequalities yield any informative finite-horizon residual bound when N(1−β)>1N(1-\beta)>1?
4 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for the careful review and for recognizing the contribution of buffer cancellation and joint stability, as well as the value of the paired experiments and controls. Your questions led us to derive fixed-momentum bounds and sharpen the Frobenius dimension dependence. We present those results here and discuss the practical training evidence in our second comment.

Fixed-momentum bounds and sharper dimension dependence

A finite-horizon bound beyond the original momentum range. Yes. We extended the tracking analysis to every fixed 0≤β<10\le\beta<1, including 0.950.95, while accounting for gradients changing as the parameters move. The result does not require N(1−β)≤1N(1-\beta)\le1. At N=1024N=1024, β=0.95\beta=0.95 and K=8K=8, a balanced-quadratic example gives a bound below 0.722, compared with initial gradient norm 1.

For classical exact-polar Muon at N=1024N=1024 and β=0.95\beta=0.95, a slightly looser, simpler bound is

+0.04\frac{\rho_1}{K} +0.32\sqrt r\thinspace \bar\sigma_K+2085L\eta.$$ The coefficients are rounded upward for readability. Here $N$ is the component count. $\mathcal G_{\rm in}$ is the mean expected nuclear-gradient norm before updates, $\eta$ the stepsize, $K$ the number of passes, and $r$ the smaller matrix dimension. $D$ is the initial objective gap, $\rho_1$ the initial nuclear-gradient norm, and $\bar\sigma_K$ the pass-averaged expected RMS Frobenius deviation of component gradients from the full gradient at pass starts. $L$ is the component operator-nuclear smoothness constant. For balanced $f_j(x)=(x\pm 0.01)^2/2$, $x_0=1$, $\eta=0.00017$ and $K=8$, we have $L=r=\rho_1=1$, $D=0.5$ and $\bar\sigma_K=0.01$. Substitution in the displayed bound gives **less than 0.722**. Component smoothness and lower bounds control the gradient spread through the objective gap. A coupled gap-and-tracking estimate closes the residual a priori, without uniform variance. The analysis assumes deterministic initialization, zero buffer and independent uniform RR passes, with no decay or stabilizer. The same method gives the no-decay Nesterov residual for five Jordan Newton–Schulz steps (NS5) in exact arithmetic with zero-guard Frobenius normalization, and additional normalization-error terms for positive input stabilization. These are residual bounds, not general vanishing-rate guarantees. **A vanishing rate beyond the original restriction.** We additionally prove **$O(N^{-1/4})$** expected pre-update stationarity for exact-polar RR at fixed $K$ and matrix shape. Under common smoothness and initial component-gap constants $L,H$, it uses $N\ge\max\lbrace 2,rK\rbrace$, $\beta=1-(rKN)^{-1/2}$ and an explicit $H,L$-dependent stepsize, of order $\sqrt{H/L}N^{-3/4}$ at fixed $K$ and shape. Here $H$ is the initial gap to the average component lower bound. Thus $N(1-\beta)=\sqrt{N/(rK)}>1$ when $N>rK$. This rate varies momentum with $N$. The fixed-$0.95$ result above is a residual bound. **Sharper dependence under Frobenius smoothness.** We improve the rank dependence from **$r^{2/3}$ to $r^{1/2}$** under component Frobenius smoothness and lower bounds. Separating parameter drift from gradient spread, with a new stepsize and momentum prescription, gives the improvement. Nesterov shares the rate, while NS5 adds dimension-dependent alignment constants and a constant stepsize rescaling. The original norm conversion remains valid. The new result sharpens the RR bound without asserting a dimension advantage over IID in every smoothness geometry. The full statements, exact coefficients, parameter choices and proofs are in revised Appendices I.2, K–K.1 and N.
AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Thank you also for asking how the noise calculation relates to the practical training results.

Practical training and the meaning of the noise bound

Practical momentum at one, two and four passes. The new FineWeb-Edu experiments improve the registered primary training-loss AUC at β=0.95\beta=0.95 for all three horizons. They use five Newton–Schulz steps with Nesterov momentum, matrix decay 0.10.1 and side AdamW. This directly adds loss evidence at the momentum used in practice, alongside the new bounds valid beyond the original momentum restriction.

FineWeb-Edu 124M settingMean IID−RR AUC improvement ± paired SDRR wins / pairs
1 pass0.021563 ± 0.0044825/5
2 passes0.020817 ± 0.0031675/5
4 passes0.011861 ± 0.0016165/5

Positive differences favor RR. The primary outcome is normalized full-pool training cross-entropy (CE) AUC, measured at five equally spaced evaluations including initialization. SD is the sample SD of paired differences, not a confidence interval.

Each pass contains 1,024 updates over 32,768 sequences. Each sampler selects its own learning rate using two development seeds and an equal tuning budget, then uses five new paired confirmation seeds. Both select LR 0.010.01 for one pass and 0.0050.005 for two and four passes. The two-pass result is an independent 2,048-update campaign with its own tuning and confirmation, not a four-pass prefix. Held-out and confirmation results never select the learning rate.

Frozen-noise reduction and training-loss gains. The 3.71% frozen squared-noise reduction is not a ceiling on training-loss gains. It holds at fixed weights, whereas the extended analysis tracks gradients and their changing spread as parameters move. The residual covers the original fixed-component setting N=1024N=1024, β=0.95\beta=0.95, where N(1−β)=51.2N(1-\beta)=51.2.

The horizon-dependent momentum prescription optimizes a worst-case guarantee. It does not predict the momentum that minimizes finite-budget training loss. The poorer high-momentum pilot therefore does not contradict the theorem. The added experiments establish practical loss improvements, while the theory supplies guarantees for the stated dynamics. Neither provides a useful numerical stationarity certificate for the actual 124M trajectory or identifies the fraction of its RR gain caused by buffer cancellation.

Complete residual proofs are in revised Appendix K. Detailed protocols and seed records are in Appendix O.1 and the supplementary materials.

Dear Reviewer i4qR,

Thank you again for your thoughtful review and positive assessment of the paper’s theoretical contribution. As the discussion period approaches its close, we would like to briefly summarize the additions prompted by your questions.

  • Practical momentum. We derived finite-horizon residual bounds for every fixed 0≤β<10\leq\beta<1, including β=0.95\beta=0.95, without requiring N(1−β)≤1N(1-\beta)\leq1. The controlled example in our response gives a bound below 0.7220.722, compared with an initial gradient norm of 11.
  • Dimension dependence. We sharpened the RR rank dependence under Frobenius smoothness from r2/3r^{2/3} to r1/2r^{1/2}.
  • Practical evidence. We added independently tuned one-, two- and four-pass language-model comparisons at practical momentum, with five fresh paired seeds for each setting.

We have also clarified that the fixed-momentum results are residual guarantees and do not provide a numerical stationarity certificate for the practical language model.

If these additions strengthen your assessment of the paper, we would be grateful if you could consider whether the revised submission warrants a stronger recommendation. We remain happy to address any outstanding questions.

Thank you again for your time and helpful feedback.

Sincerely,
The authors

I thank the authors for their response. They have mostly address my concerns. I will maintain my positive score.

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

This work studies the convergence of Muon under random reshuffling and establishes convergence guarantees for both exact orthogonalization and approximate orthogonalization using the Newton–Schulz iterations. The authors also present experiments on language model training, comparing Muon under random reshuffling and IID sampling.

Critical strengths
  • This work provides convergence guarantees for Muon under random reshuffling, which is the sampling scheme commonly used in practical machine learning training. This is a meaningful contribution, as existing convergence analyses of Muon primarily consider IID sampling.
Critical weaknesses
  • In the theoretical guarantees, the stepsize η\eta depends on HH, which requires knowledge of the minima of the individual component objectives. Although the authors mention that HH can be replaced by a known positive deterministic quantity, it would be nice to present the main result with parameter choices that do not depend on problem-dependent quantities.
  • The convergence guarantees do not cover Nesterov momentum and decoupled weight decay, which are commonly used in practical implementations of Muon. Extending the analysis to incorporate these components would strengthen the theoretical result.
  • The experimental results are somewhat limited, as the main results are based on a single language-model training setup.
  • I think that it would be better to present the convergence guarantee for Muon with Newton–Schulz orthogonalization in the main text rather than in the appendix, since this setting is closer to the practical implementation of Muon. The main theoretical result is somewhat limited in scope, and highlighting the Newton–Schulz guarantee would strengthen the presentation of the paper's contributions.
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for the careful review and for recognizing the importance of an RR convergence guarantee for Muon. We also appreciate your positive assessment of the paper’s soundness. Your suggestions led us to add parameter choices without unknown objective constants, extend the analysis to practical variants, broaden the experiments, and bring the Newton–Schulz guarantee into the main text.

RR convergence and practical Muon guarantees

Parameter choices without unknown objective constants. The new choices require neither component minima nor unknown smoothness or objective-gap constants. This directly addresses the implementability of the original prescription. For classical exact-polar Muon without decay, we choose momentum β=1−λ/N\beta=1-\lambda/N and stepsize η=(a/N)min⁡{λ,λ/K}\eta=(a/N)\min\lbrace \lambda,\sqrt{\lambda/K}\rbrace, with λ\lambda defined below, and obtain

\lambda=\min\lbrace 1,(N/(rK))^{1/3}\rbrace.$$ Here $N\ge2$ is the component count, $K$ the epoch count, $r$ the smaller matrix dimension, and $a>0$ a user-chosen scale. $\mathcal G$ is the larger mean expected nuclear-gradient norm over pre-update iterates and epoch starts. $L$ is component operator–nuclear smoothness, and $H$ is the initial objective gap above the average component lower bound. The bound depends on $L,H$, but the algorithm does not need their values. Valid component lower bounds suffice. Exact minima are not required. This guarantee assumes deterministic initialization, a zero initial buffer and independent uniform RR epochs. **Nesterov momentum and decoupled decay under RR.** Our main contribution is an RR convergence guarantee for Muon with carried momentum and nonlinear orthogonalization. We first analyze classical momentum and exact polar to isolate the dependence created by RR, without a uniform variance assumption. Following your suggestion, we have also extended the analysis to Nesterov momentum and decoupled weight decay. For Nesterov, we track the carried buffer combined with the current gradient before orthogonalization. This gives a vanishing gradient-norm bound of order $1/\sqrt{K\lambda}$ for five Jordan Newton–Schulz steps (NS5), with dimension-dependent alignment constants. It uses exact arithmetic, zero-guard Frobenius normalization, no decay or stabilizer, and the preceding stepsize divided by $1.25$. For decay coefficient $\kappa>0$, we write the update as a convex combination inside the spectral ball of radius $1/\kappa$ [2]. Its stationarity gap is the maximum linearized improvement toward any point in that ball. Exact polar, including Nesterov, gives a gap bound of order $1/\sqrt{K\lambda}$ when $\lVert W_0\rVert_{\rm op}\le1/\kappa$, $0<\kappa\eta\le1$, and the preceding step uses $a=\sqrt{H/L}/100$. With NS5, Nesterov and decay together, the ball radius becomes $1.25/\kappa$. We obtain an explicit residual retaining tracking error and the NS direction's shortfall from ideal spectral-ball linear minimization. These extensions strengthen the RR theory beyond the unbiased, bounded-variance setting of [1]. Side AdamW and finite precision remain outside the guarantees. **Newton–Schulz guarantee in the main text.** We have moved the fixed-depth NS guarantee into the main text. With classical carried momentum and exact arithmetic, it gives an **$O(K^{-1/3})$** expected nuclear-gradient bound at fixed $N$ and matrix shape, for any fixed positive number of Jordan steps. It normalizes the buffer by $\max\lbrace 1,\lVert M\rVert_F\rbrace$, uses the preceding step with $a=\sqrt{H/L}/100$ divided by $1.21$, and requires no lower singular-value bound. Exact polar isolates the RR difficulty, while the NS result transfers the descent argument to approximate orthogonalization. Prior IID guarantees [3] do not alone establish that RR step. Full statements and proofs are in revised Appendices I, J and M. The moved NS guarantee is Proposition 1 in Section 4.2, with its proof in E.3. **References** [1] Sato, Naganuma and Iiduka (2025). Convergence Bound and Critical Batch Size of Muon Optimizer. arXiv 2507.01598. [2] Chen, Li and Liu (2025). Muon Optimizes Under Spectral Norm Constraints. arXiv 2506.15054. [3] Kim and Oh (2026). Convergence of Muon with Newton-Schulz. ICLR.
AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Thank you also for pointing out the need for a broader empirical evaluation.

Independent language-model and vision evidence

Experiments beyond a single language-model setting. We added independent experiments on FineWeb-Edu, WikiText-103 and CIFAR-10. This addresses the original evaluation's limited scope with two language-model datasets and a vision model. RR improves the registered primary outcome in all five new seed pairs in each setting.

The primary outcome is normalized full-pool training cross-entropy (CE) AUC. Positive IID−RR differences favor RR. Entries show the mean paired improvement ± paired sample SD, with five pairs per setting.

SettingAUC improvement ± paired SDRR wins
FineWeb 1-pass0.021563 ± 0.0044825/5
FineWeb 2-pass0.020817 ± 0.0031675/5
FineWeb 4-pass0.011861 ± 0.0016165/5
WikiText 1-pass0.023577 ± 0.0070625/5
CIFAR-10 ViT, 20 passes0.043569 ± 0.0047555/5

Independent learning-rate selection and confirmation. Each sampler selects its LR independently from a common grid using two development seeds, then uses five new paired confirmation seeds. Held-out and confirmation outcomes do not select LR. The FineWeb 2-pass result is a separate 2,048-update campaign with horizon-specific tuning, not a prefix of a 4-pass run.

FineWeb-Edu and WikiText-103. The 124M decoder uses five Newton–Schulz steps, Nesterov momentum with coefficient 0.950.95, matrix decay 0.10.1 and side AdamW. Each pass has 1,024 updates over 32,768 sequences. Both samplers select LR 0.010.01 for FineWeb 1-pass and WikiText, and 0.0050.005 for FineWeb 2- and 4-pass. WikiText uses fixed train/validation/test subsets of 32,768/256/256 sequences, so these are subset results rather than full-benchmark scores.

CIFAR-10. The 3.18M ViT trains for 20 passes/7,000 updates without augmentation or dropout. Both samplers select LR 0.0006250.000625 from a common ten-rate grid. Test accuracy improves by +0.624 percentage points, paired SD 0.2935 pp, with 5/5 wins. Secondary CE results are

IID−RR CE improvementMeanPaired SDPairs
Validation+0.0074480.0428485
Test+0.0077960.0276245

The CE means favor RR, while individual paired effects vary. SD is a sample SD, not a confidence interval.

LM AUC uses five equally spaced full-pool evaluations including initialization. ViT uses 21 epoch boundaries. These independently tuned comparisons broaden the practical evidence, without implying universal endpoint or momentum benefits, a stationarity certificate, or wall-clock speedup. Different horizons are separate experiments, not a paired causal comparison of pass counts.

Detailed protocols and all seed records for the reported outcomes are provided in revised Appendix O.1 and the accompanying supplementary materials.

Dear Reviewer N8Br,

As the discussion period draws to a close, we would like to thank you again for your careful review and constructive suggestions. Your feedback helped us strengthen the paper in several concrete ways.

  • Parameter choices. We added a prescription for classical exact-polar Muon that does not require knowledge of component minima or unknown smoothness and objective-gap constants.
  • Practical variants. We extended the analysis to Nesterov momentum and decoupled weight decay, explicitly stating the applicable guarantees and remaining implementation limitations.
  • Broader evaluation. We added FineWeb-Edu, WikiText-103 and CIFAR-10 ViT experiments, with separate learning-rate selection and five fresh paired confirmation seeds per setting.
  • Presentation. We moved the fixed-depth Newton–Schulz guarantee into the main text as Proposition 1.

We hope these revisions address the main concerns underlying your assessment. If, after considering our responses and the revised manuscript, you feel that the paper merits a more favorable evaluation, we would be very grateful if you could reconsider your rating.

We would also welcome any remaining questions. Thank you again for your time and thoughtful consideration.

Sincerely,
The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.