Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success
By Florian H\"ubler, Thomas Pethick, Suvrit Sra
This paper provides theoretical justification for the empirical success of non-Euclidean matrix optimizers like Muon, proving they achieve optimal sample complexity under heavy-tailed gradients while Euclidean methods incur dimension-dependent costs. It explains why Muon outperforms Adam-style methods for transformer training.