AI summaryⓘ
The authors study a way to compress updates in an optimization algorithm called Muon by only keeping the sign (positive or negative) of each parameter update, reducing communication to just one bit per parameter. They find that simply changing where the sign is applied around a certain step (the Linear Minimization Oracle) doesn't fix issues with the method sometimes increasing rather than decreasing the objective. They show that a common fix called error feedback doesn't help when applied directly to the compressed output, but does work when applied earlier in the process. In experiments, a heuristic method that applies the sign after the oracle performs better in practice, even though the authors prove it can fail theoretically. Overall, their results highlight a gap between theoretical guarantees and practical performance in compressed optimization methods.
Muon optimizersign compressionLinear Minimization Oracle (LMO)error feedbackbiased compressornonconvex optimizationgradient descentcommunication compressionfederated learningconvergence rate
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.