arXiv paper: Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback

A new paper examines extremely low-bandwidth compression for the Muon optimizer. SignMuon compresses the update to a single bit per parameter by taking its elementwise sign, allowing matrix-aware optimization under severe communication constraints. The authors find SignMuon performs well in practice but can diverge even on simple linear problems due to biased compression. They test three placements for the sign operation—after the Linear Minimization Oracle (SignMuon), before it (MuonUSign), and both before and after (MuonSign)—and construct examples where all three ascend rather than descend. Traditional error feedback applied to Muon's output fails to fix this for any smoothness constant, step size, or momentum setting. However, error feedback applied to the gradient (EF21-MuonUSign, EF21-MuonSign) yields the standard convergence rate on smooth nonconvex problems. Experiments on centralized CIFAR-10, federated CIFAR-10, and nanoGPT contradict the theory: sign-after-the-LMO (SignMuon), which the paper proves divergent, consistently outperforms the provably convergent variants, suggesting the heuristic compression placement matters more at scale than theoretical guarantees.