- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper analyzes convergence of the MUON optimizer. In particular it proves sample complexity / iteration rates required to achieve epsilon-stationarity (gradient is less then epsilon). This paper differentiates itself from other works by trying to extend previous analysis to more realistic settings, i.e. with muon with nesterov momentum and with inexact polar decomposition. They tackle the ladder by making an assumption on the error between the approximate polar decomposition and the true value and demonstrate that practically used approximation methods (polynomial iterations) can be covered by the assumption. They also do not strictly assume bounded variance but allow for heavy tailed noise. They also present a randomized projection version of the Muon optimizer that projects the matrix to a low dimensional subspace before performing the polynomial iterations in order to save compute. Their theorems cover this setting as well. Lastly some simulations are performed to demonstrate the effectiveness of both MUON and the randomized variation, in particular by comparing against other popular optimizers like Adam and SGD with various forms of momentum.
Critical strengths
This paper extends convergence guarantees to a more realistic setting that closely aligns with the MUON that is applied in practice. No existing work covers both nesterov momentum and approximate polar decomposition. This is a clear contribution. The main paper is also fairly easy to understand.
Critical weaknesses
The only real weakness I have to point out is with respect to the randomized projection version of the algorithm. The benefit of the projected version is scalability in terms of complexity in the size of the matrices. The experiments demonstrate that the cost in terms of accuracy is fairly small and that the savings in terms of GFLOPs (only for the update steps) is valuable. However, the latency is actually greater for this randomized version. There is no evidence of any practical use of the algorithm if its accuracy is worse and it is slower in practice (fixing some compute budget / memory). Perhaps if dramatically scaling weight matrices at some point the savings will kick in, but it does not seem so practical.
Questions for authors
Do you believe there is practicality of the randomized projection variation to muon in terms of cost efficiency / scaling up?
How similiar is the analysis to existing work? Given that the aspects emphasized here (heavy tailed noise, nesterov momentum and approximate polar decomposition) all exist in other works on their own and not together, it is not clear to me (someone unfamiliar with the existing work on muon convergence) how substantial the technical contribution is here.
some minor feedback:
Under main contributions there is the following quote: ‘To our knowledge, this is the first work that achieves optimal sample complexity for Muon with Nesterov momentum, even under bounded-variance assumption.’. The table shown says other work (yu et al [51]) has the same convergence rate and also considers nesterov momentum. Does this contradict the quote or is there something else I am missing?
is used in assuption 3.2 as existing values for the inequality but it is also used throughout for singular values. While it did not bother me I could see it perhaps being confusing particularly in the proofs section.
3 comments
How similiar is the analysis to existing work? Given that the aspects emphasized here (heavy tailed noise, nesterov momentum and approximate polar decomposition) all exist in other works on their own and not together, it is not clear to me (someone unfamiliar with the existing work on muon convergence) how substantial the technical contribution is here.
Thanks for the question. We detail the challenges for our analysis below
-
Here, we want to highlight that one of the main contributions of our work is the Assumption 2.1 to capture inexact polar decomposition. This assumption is novel and does not exist in the literature. Therefore, the analysis of Muon under this proposed assumption requires new proof techniques even if there are works on Nesterov momentum and heavy tailed noise.
-
Moreover, the analysis of stochastic algorithms under bounded variance is much simpler given the existing huge literature. However, the analysis becomes much more complicated when the gradient noise is heavy-tailed with (Assumption 3.2) and there is also stochasticity coming from randomized inexact polar decomposition.
-
Finally, we proved that the algorithms used in practice for Newton Schulz satisfy our proposed assumption 2.1. We hope this clarifies the difficulties of our analysis compared to the existing literature.
Under main contributions there is the following quote: ‘To our knowledge, this is the first work that achieves optimal sample complexity for Muon with Nesterov momentum, even under bounded-variance assumption.’. The table shown says other work (yu et al [51]) has the same convergence rate and also considers nesterov momentum. Does this contradict the quote or is there something else I am missing?
No, the statement is correct and doesn’t contradict the table. Yu et al [51] does not consider the inexact polar decomposition whereas we do in Theorem 3.5. Their analysis assumes is an orthogonal matrix which is not the case in practice when we use Newton Schulz to approximate the polar decomposition.
is used in assuption 3.2 as existing values for the inequality but it is also used throughout for singular values. While it did not bother me I could see it perhaps being confusing particularly in the proofs section.
Thanks for the pointer. We will definitely fix it in the updated version of the manuscript.
Thank you for the response, it is nice to see the crossover point at which savings kick in from the added experiment. I will maintain my positive score.
Thank you for the excellent suggestions. Your conjecture about scaling is what we find. We have a new timing experiment to support this, which we will add to the paper.
Training time. We timed one orthogonalization of a Gaussian random matrix for the two common matrix shapes of a transformer of width d: d x d (attention) and 4d x d (MLP). Note that d = 768 in our nanoGPT, and d = 4096 and 8192 are the widths of 7B and 70B models (e.g. Llama-2). Times are in ms on one H100 GPU, speed-up over Newton-Schulz in brackets:
At d = 768 and 2048, the randomized step is slower at each rank. This is the scenario of our benchmarks (the CIFAR-10 matrices are even smaller), which is why it does not improve training time. At the 26% rank ratio of our experiments, it becomes faster only at d = 8192, which is the scale of a 70B model. With a smaller rank (10% of d, or 256), it is already faster at d = 4096.
Setup. We also ran an experiment on the following matrix regression problem, to measure the end-to-end running time:
minX∈Rn×nf(X)=21∥AXB−C∥F2,A∈Rp×n, B∈Rn×p, C=AX⋆B+cE.
A and B are given data matrices. The ground truth X⋆ and the noise E have i.i.d. standard Gaussian entries.
The timings above are for a single orthogonalization. To check that the saving carries over to a complete optimization run, we ran Muon and Rand-Muon with Nesterov momentum for 20,000 iterations on the problem above with p=100, c=10−3 and the exact gradient ∇f(X)=A⊤(AXB−C)B⊤. As the table below shows, Rand-Muon is 10-13x faster at n = 8192. Both methods reach the same final gradient norm (about 6×10−8 of the initial gradient), and they need about the same number of iterations to reach a given gradient norm. The table reports, for each run, the total wall-clock time, the final gradient norm and the number of iterations needed to reach a gradient norm of 10−2, 10−3 and 10−5 (gradient norms are relative to the initial one):
Perplexity. The worse perplexity on nanoGPT (29.46 against 27.25) is the cost of rank 26% at d = 768. For this small-scale pretraining task, full Muon is the right choice when higher accuracy is the priority. Nevertheless, at larger scale, the proposed Rand-Muon can be much more efficient.