Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback
AuthorsMaria Smirnova, Alexey Kravatskiy
Resources
This paper shows that compressing Muon to signs can break its theory, yet the seemingly unsafe version often works best in real-world training.
Key results
SignMuon, MuonUSign, and MuonSign transmit one bit per parameter on the uplink; SignMuon and MuonSign also use one bit per parameter downlink.
Theorem 1 constructs a linear-objective ascent example for SignMuon.
Theorems 2 and 3 use a shared 5×5 linear-objective ascent instance.
Test accuracy on CIFAR-10 with ResNet-18 after 75 epochs.
Accuracy-point spread among the after, before, and both-sides sign placements on federated CIFAR-10 with 11 clients.
FineWeb tokens processed in the nanoGPT speedrun on 8 NVIDIA H100 GPUs.
What the paper found
Maria Smirnova and Alexey Kravatskiy of MIRIAI examine whether Muon’s matrix-aware spectral geometry can survive extreme sign compression at one bit per parameter. They compare SignMuon, which signs after Muon’s linear minimization oracle, MuonUSign, which signs before it, and MuonSign, which signs on both sides. The central theoretical result is negative: all three can turn a descent step into ascent on linear objectives, with explicit counterexamples in 4×4 for SignMuon and 5×5 for MuonUSign and MuonSign, regardless of step size or momentum. Error feedback applied to the Muon output also fails in general, while EF21-MuonUSign and bidirectional EF21-MuonSign restore the standard O(T^-1/2) nonconvex convergence rate by compressing gradients or residuals instead. Experiments reveal a sharp theory–practice gap. On centralized CIFAR-10 with ResNet-18, SignMuon reached 94.60% test accuracy versus 94.35% for full-precision Muon and 93.37% for SignSGD; on federated CIFAR-10 with 11 clients, it achieved 85.72%, while the three sign placements differed by 2.8 accuracy points. In the nanoGPT speedrun, trained on 611M FineWeb tokens across 8 NVIDIA H100 GPUs, SignMuon and EF21-SignMuon came within 0.01 validation-loss points of Muon. The authors conclude that sign-after-the-LMO is the strongest practical heuristic despite lacking a general guarantee, whereas the provably convergent alternatives pay an empirical performance cost.
Original abstract
SignMuon compresses the Muon update to one bit per parameter by taking its elementwise sign, providing the most direct way to run a matrix-aware optimizer under an extremely low communication budget. It outperforms SignSGD in practice, yet it can ascend even on a linear function. Signing the gradient before the Linear Minimization Oracle (LMO), rather than after, does not repair this: we construct a small explicit instance on which sign-before (MuonUSign) and sign-on-both-sides (MuonSign) ascend as well, so no placement of the sign around the oracle descends in general. Error feedback, the standard remedy for a biased compressor, does not rescue SignMuon: when applied to Muon's output, error feedback can fail for every smoothness constant, step size, and momentum. Applied to the gradient, error feedback does work, and EF21-MuonUSign and EF21-MuonSign attain the standard $\mathcal{O}(T^{-1/2})$ rate for the squared gradient norm on smooth nonconvex problems, the latter at one bit in each direction. Experiments then reverse the ordering: across centralized CIFAR-10, federated CIFAR-10, and the nanoGPT speedrun, the strongest compressed method is consistently sign-after-the-LMO, precisely the placement we prove divergent, with the provably convergent variants trailing it. Compressing after the LMO, a heuristic, matters more at these scales than the guarantee does.
Read the original paperMore in Optimization
Browse all 36 papers →An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
This work proves that stochastic bilevel optimization fundamentally requires up to epsilon^{-6} oracle queries, showing existing methods are asymptotically optimal.
Hyper Algorithm Design Agent: Evolving Learnable Optimizer from Zero
Zipei Yu, Yue-Jiao Gong, Zeyuan Ma, Yuncheng Jiang, Zhiguang Cao
A pair of self-improving coding agents evolves new learnable optimization algorithms from a simple template, reducing the need for handcrafted optimizer design.
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Shinsaku Sakaue
A new multiscale matrix-weights algorithm learns hidden linear preferences online with provably optimal dimension-dependent regret.