- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The authors give a general regret bound for momentum updates with smooth spectral maps, such as finite Newton-Schulz, to characterize the tradeoff between polar-approximation accuracy and update stability and derive stationarity guarantees for nonsmooth nonconvex optimization. They show that iterations is sufficient for expected relaxed -stationary on nonsmooth nonconvex objectives with complexit as . Additionally, they recover optimal accuracy dependence for smooth deterministic and stochastic optimization. In other words, they show that the analyzed algorithm achieves the optimal deterministic and stochastic gradient-oracle dependence, up to problem dependent factors for smooth objectives.
Critical strengths
-
The paper introduces a smoothing mechanism, which explains how finite Newton–Schulz implicitly regularizes the update and shows that more iterations improve the polar approximation while making updates more sensitive to changes in momentum (Theorem 5.3 and Lemma 5.2). This explains why stopping Newton-Schulz early can help Muon.
-
The analysis of this paper covers a broad class of Lipschitz spectral maps and shows that logarithmic Newton–Schulz depth suffices for nonsmooth stationarity guarantees. The proposed mechanism yields concrete guarantees and extends beyond a single polynomial or a synthetic observation, providing a foundation for further optimizer analysis.
Critical weaknesses
-
The version of Muon used to prove convergence has several differences from its practical implementations. Theorems 5.4 and 5.7 analyze Algorithm 1 within the randomized O2NC protocol of Algorithm 2. This setup uses a known fixed normalization bound (Assumption 2.3), classical Newton–Schulz coefficients (lines 206 - 209), randomized gradient queries, and an averaged output (lines 235 - 251). The authors acknowledge several differences from practical Muon in the conclusion section. Existing guarantees remain insufficient to show whether this mechanism guarantees convergence under the practical normalization, coefficient, and gradient evaluation configurations of Muon.
-
The empirical results are not clearly sufficient to demonstrate the practical importance of the Newton–Schulz depth tradeoff. First, this paper does not include many experimental results. Second, Appendix H reports one synthetic problem instance and two learning rates. It uses current-iterate gradients rather than the analyzed O2NC protocol (lines 1517 - 1521), and Figure 3 reports loss curves without directly evaluating the theorem’s stationarity criterion. Additionally, increasing the Newton–Schulz depth can make updates both larger and more sensitive to changes in momentum, since for small . Comparing depths at the same learning rate also compares different update sizes.
Questions for authors
Refer to the weaknesses:
- Can the authors clarify and explain the differences between the version of Muon used to prove convergence and its practical implementations? And what prevents extending the guarantees to practical Muon implementations?
- Can the authors explain the second weakness: the empirical results are not clearly sufficient to demonstrate the practical importance of the Newton–Schulz depth tradeoff?
2 comments
Thank the authors for their detailed responses, solves my quesitons. I will maintain my score.
Thank you for your time and thoughtful comments on our work.
The analyzed algorithm differs from practical Muon in its Newton–Schulz coefficients, normalization, gradient query points, and output rule. We think these differences largely arise from the difficulty of obtaining convergence guarantees in the nonsmooth nonconvex setting.
The classical Newton–Schulz coefficients obtained from a Taylor expansion give a nondecreasing singular-value map (see Assumption 4.1). This nondecreasing property allows us to construct a convex potential. The empirically tuned coefficients used in practical Muon do not satisfy this property, so our proof does not directly apply to them.
Fixed normalization satisfies the condition Ct+1≥βCt needed in our proof (see Lemma 4.7). Momentum-dependent normalization does not generally satisfy this condition and is therefore not covered by our analysis.
Randomized queries are motivated by the fact that deterministic local algorithms can require exponentially many queries in the dimension to find Goldstein stationary points in the nonsmooth nonconvex setting ([1], Theorem 3.1). We also use relaxed stationarity and output rule because ordinary approximate stationarity cannot in general be guaranteed in finite time in this setting ([2], Theorem 5).
Thank you for this suggestion. We have added experiments to Appendix H of the revised paper and marked the additions in red. Figures 4–5 report stationarity measurements, Figure 6 shows how they depend on Newton–Schulz depth and learning rate, and Figures 7–8 present experiments with O2NC randomized query points.
We agree that equal learning rates do not imply equal update sizes. However, the example of Parshakova et al. [3] shows that exact polar can fail regardless of the learning rate. On this example, our experiments show that finite Newton–Schulz makes progress while exact polar remains away from stationarity.
References
[1] Guy Kornowski. The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization. arXiv:2609.23837, 2026.
[2] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of Finding Stationary Points of Nonconvex Nonsmooth Functions. ICML, 2020.
[3] Tetiana Parshakova, Ahmed Khaled, Michael Crawshaw, Guillaume Garrigos, and Robert M. Gower. Muon Does Not Converge on Convex Lipschitz Functions. arXiv:2605.08980, 2026.