Fresh Sketches Beat Power Iteration in Randomized Low-Rank Muon
Randomized low-rank variants of Muon orthogonalize a Gaussian sketch of the momentum and, following randomized linear algebra, sharpen it with a power iteration. In language-model pretraining at high momentum, we show that this step makes training worse, give a partial account of why, and remove the wall-clock overhead of randomized Muon on nanoGPT. (1) Removing power iteration improves training. On nanoGPT (80M parameters in the Muon-updated matrices, three seeds) the final perplexity drops from 29.43 to 28.67 with fewer matrix products; in a separate reimplementation on the GPT-2 Medium track (about 200M, two seeds) against a numerically exact h = 1 (subspace iteration in FP32), h = 0 is again better, by 0.018 and 0.020 in final validation loss (pre-registered). On nanoGPT and in one toy setting, a wider sketch is a better use of the same compute. (2) About half of the 80M gap is bf16 rounding. The rest is not a per-step effect: in exact arithmetic, power iteration always improves the single-step alignment of the update with the momentum. (3) We propose an account based on the update averaged over fresh sketches, a diagonal spectral filter that power iteration makes less flat (proved for one sketch column and rank two; certified by interval arithmetic in a deterministic-equivalent model). Consistent with it, freezing the sketch reverses the ranking (three seeds) and averaging each update over sketches favours no power iteration in 31 of 32 toy settings; but a mean-field toy favours power iteration, so flatness alone does not decide the winner. (4) The overhead comes from batched Householder QR of the sketch; a compiled, shifted CholeskyQR3 removes about 100 ms per step. On nanoGPT the link between flatness and loss is correlational, and why the advantage persists at low momentum is open.
Authors
- 創規 福田
Institutions
- The University of Tokyo (JP)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24182873
- Primary Topic
- Stochastic Gradient Optimization Techniques
- Type
- preprint