- 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 dependence of RR-SGD, against 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
-
The work provides the first proof covering convergence of Muon under RR, relying on standard assumptions.
-
The paper is relatively honest about the theory-practice gap. For example, it reports that the experimental lies outside the theorem conditions and that the proved frozen-noise reduction is only 3.71% there.
Critical weaknesses
-
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 , so for . In the authors' own pilot (Table 3), gives the worst training AUC at every learning rate (e.g., at learning rate 0.005 it gives 5.23, against 4.03 at ). 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.
-
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 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
-
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 -. The paper's own LM experiment uses , which is already beyond common practice. At those values the bounds in the main results say nothing. The theorems become informative only after about - epochs. The advertised versus 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?
-
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
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 is a fresh uniformly sampled component gradient and is the average component lower bound, component smoothness gives 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 and other nondegenerate problem constants, the sufficient component-gradient query budgets have accuracy dependence Here counts component-gradient evaluations and 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 cost. Against the original bounded-variance IID comparator, its leading terms cross at an accuracy scale proportional to 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- result neither removes the cost nor gives an 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 expected pre-update stationarity for exact polar without decay at fixed pass count , matrix shape and common . Here is component operator–nuclear smoothness, the initial gap to the average component lower bound, and the smaller matrix dimension. For , use and an explicit -dependent stepsize. Thus when . Initialization is deterministic, the buffer is zero and RR epochs are independent and uniform. Momentum varies with . This is not a vanishing rate at fixed .
A controlled nonconvex quadratic-plus-cosine example uses matrices, nonnegative components, globally unbounded component-gradient variance, classical exact polar and zero buffer.
| One-pass nuclear-gradient quantity | Value |
|---|---|
| Initial norm | |
| Expected pre-update mean, proved upper bound |
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 . The fixed-pass result (Theorem 3) has rate , 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
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 sufficient query budget, compared with the ε−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≤β<1, including 0.95, without N(1−β)≤1. Here N 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)=21(x+cj)2+2(1−cosx) with balanced cj=±0.01, x0=1 and N=1024. The components are nonnegative, globally smooth and nonconvex. With β=0.95, raw LR 0.0028 and zero buffer, five Jordan Newton–Schulz steps (NS5) with Nesterov momentum give these mean pre-update gradient-norm bounds
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.
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.01 for FW1, 0.005 for FW2/FW4 and 0.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, decay 0.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.