Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback Maria Smirnova∗ , Alexey Kravatskiy∗ MIRIAI Moscow, Russia [email protected], [email protected]
arXiv:2607.29674v1 [math.OC] 31 Jul 2026
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-bothsides (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 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.
1
Introduction
Training a deep network across clients consumes bandwidth as well as computation: every round each client transmits a full update, and under a limited link those updates dominate the wall-clock cost. Compression is the standard remedy (Bernstein et al. 2018, 2019; Beznosikov et al. 2023), and SignSGD is its extreme point: one bit per coordinate, at slight cost in accuracy. SignSGD, however, flattens each weight matrix into a vector, discarding structure that other optimizers exploit. Muon exploits precisely that structure, orthonormalizing the momentum matrix before stepping, and in several settings surpasses tuned adaptive methods (Jordan et al. 2024b; Bernstein and Newhouse 2024; Shah et al. 2025). What it transmits, however, is a dense matrix at full precision: thirty-two bits per parameter where the budget allows one. Matrix geometry and a one-bit budget are therefore difficult to obtain together. ∗
These authors contributed equally.
We study the natural ways to combine sign compression with the Muon LMO at one bit per parameter: SignMuon, which signs after the LMO, sign(LMO(·)); MuonUSign, which signs before, LMO(sign(·)); and MuonSign, which signs on both sides and, like SignMuon, emits a ±1-valued step, so that uplink and downlink alike cost one bit. All three build Muon’s matrix-aware geometry into the step without preserving it intact, and they are not interchangeable: on federated CIFAR-10 (Table 2) they span 2.8 accuracy points, in the order after, before, both sides, and only sign-after matches full-precision Muon. None of them, however, descends in general. We prove that each can ascend on a linear objective, the simplest smooth function there is, at every step size and every momentum: SignMuon on a 4 × 4 gradient (Theorem 1), MuonUSign and MuonSign on a single 5 × 5 one (Theorems 2–3), both shapes minimal. The standard repair for a biased compressor is error feedback, and for sign-after it is unavailable: applied to the oracle’s output it fails for every triple (L, η, µ): there is then an L-smooth objective on which the method diverges (Theorem 4), so no step-size rule built from the smoothness and momentum constants can save it. What error feedback does repair is the placement that compresses the gradient instead. Adapting EF21-Muon (Gruntkowska et al. 2025) to sign compression gives EF21MuonUSign, which drives mint≤T E∥∇f (Xt )∥2∗ to zero at the standard O(T −1/2 ) rate for smooth nonconvex problems, at a one-bit uplink, and EF21-MuonSign, which adds a second error-feedback loop on the downlink so that both channels carry one bit for little further cost. Both descend on the counterexamples above. To our knowledge the signbefore and both-sides placements are new, as are the two error-feedback methods; SignMuon itself was proposed concurrently by Mishra, Trivedi, and Kumar (2026), whose guarantee is proved for the gradient-sign oracle and not for SignMuon (Appendix A.7). We evaluate all six against Muon, SignSGD, SGD and Adam on centralized CIFAR-10 with a ResNet-18, federated CIFAR-10 at N = 11 clients, the nanoGPT speedrun, and a synthetic convex quadratic on which the quantity the counterexamples attack can be measured directly. Theory and experiment then disagree. On random quadratics the gradient/step alignment that Theorems 1–3 drive negative stays positive for all three placements, so the constructions
describe a worst case that ordinary data does not produce; and on all three networks the best compressed method is sign-after, exactly the placement we prove unrepairable, the two provably convergent variants trailing it by several seed spreads. At these scales, compressing only after the oracle outweighs the guarantee. A tuned five-seed federated comparison establishes that ordering. Proofs and every result cited but not stated here are in the appendix, which continues this numbering.
2
Related Work
Sign compression. The sign is the most widely used compressor in this literature (Alistarh et al. 2017; Horváth et al. 2023; Beznosikov et al. 2023): one bit per coordinate, no index set or scale sent beside it, and a majority vote of signs that is again a sign, so both directions stay at one bit (Bernstein et al. 2019). Its theory is correspondingly well developed. SignSGD (Bernstein et al. 2018) needs growing batches to converge; its bias is otherwise repaired by error feedback (Seide et al. 2014; Karimireddy et al. 2019), sharpened into EF21 (Richtárik, Sokolov, and Fatkhullin 2021), by momentum (Cutkosky and Mehta 2020; Sun et al. 2023), or by randomizing the sign operator (Chen et al. 2020; Safaryan and Richtárik 2021; Jin et al. 2025). LMO optimizers. Muon (Jordan et al. 2024b) is the spectral-norm instance of a norm-constrained LMO step (Bernstein and Newhouse 2024; Pethick et al. 2025a), analysed by Li and Hong (2025) and Kovalev (2025), then generalized to arbitrary layer norms by Gluon (Riabinin et al. 2025). Compressed and federated Muon. Gruntkowska et al. (2025) give the error-feedback framework for bidirectionally compressed Muon/Gluon that EF21-MuonUSign and EF21MuonSign instantiate. Around it: Qian et al. (2026) compress Gluon with SARAH-type variance reduction; Takezawa et al. (2026) and Zhang and Gao (2025) study federated LMO steps without compression; Ahn et al. (2025) make the orthonormalization low-rank with error feedback, Gupta et al. (2025) quantize Muon’s optimizer states, Thérien et al. (2025) quantize the delta of DiLoCo’s Muon inner loop (Douillard et al. 2023) to two bits at next to no loss. Concurrently, Mishra, Trivedi, and √ Kumar (2026) proposed plain SignMuon with an O(1/ T ) guarantee, which Appendix A.7 shows to be a guarantee for a different method: the rate is proved only for the gradient-sign oracle, which is SignSGD’s update and invokes no polar factor, while the one bound covering the polar-sign update carries an unestimated residual that exceeds the bounded quantity exactly where the expected step ascends, as it does throughout the instance of Theorem 1. Two further methods relate sign descent to Muon differently. Bolatov et al. (2026) alternate spectral and sign steps rather than composing them; Kravatskiy et al. (2025) mix the geometries inside the oracle, so S-Muon stays an LMO for an explicit norm, with the attendant theory. Our placements put the sign around the oracle, where it is a compressor and not a geometry, so the counterexamples below bear on neither (Appendix A.8).
3
Problem Statement
We consider the stochastic optimization problem min {f (X) := Eξ∼D [f (X; ξ)]},
X∈X
(1)
where X is the parameter space (e.g., Rd or Rm×n ) and f (· ; ξ) : X → R is continuously differentiable and possibly non-convex: f (X; ξ) is the loss of a model X at a data point ξ ∼ D. In the federated setting the data are split across clients, and the training problem becomes n o PN min f (X) := N1 j=1 fj (X) , (2) X∈X
where N ≥ 1 is the number of clients and fj (X) = Eξj ∼Dj [fj (X; ξj )] is the loss on the data Dj held by client j ∈ [N ] := {1, . . . , N }. The model is a tuple of layers X = [X1 , . . . , Xp ], Xi ∈ Rmi ×ni with mi , ni ≥ 1, with ∇i the gradient block of layer i; iterates carry a time index, Xt , and Xt,i is layer i of iterate t. This is Gluon’s parameter space (Riabinin et al. 2025) under a single geometry: each layer carries the spectral norm ∥ · ∥2→2 , whose dual P is the nuclear norm ∥ · ∥∗ , and we define ∥∇f (X)∥2∗ := i ∥∇i f (X)∥2∗ ; a single matrix parameter is the case p = 1. A vector parameter is a block of width one, on which the spectral norm is Euclidean and the oracle only normalizes, so all three methods of Section 4 coincide with SignSGD there and the divergence results below need min(mi , ni ) ≥ 2 (Appendix A.2). Two assumptions run through the paper. Assumption 1 (Lower boundedness) f (X) ≥ f ∗ for all X; where explicitly invoked, each local fj ≥ fj∗ as well. Assumption 2 (Layer-wise smoothness) For every layer i and all X, Y, ∥∇i g(X) − ∇i g(Y)∥∗ ≤ Lgi ∥Xi − Yi ∥2→2
(3)
for g = f (constant Li ) and g = fj (constant Li,j ). A weaker layer-wise (L0 , L1 ) form, stated in Appendix A.1, is used only in Corollary 2 (Appendix A.10). Both forms are quantified over arbitrary X, Y, as in Gruntkowska et al. (2025); Appendix A.1 records what that strength implies. A Linear Minimization Oracle (LMO) minimizes the firstorder model of the objective over the unit ball of a norm, returning the steepest-descent direction in that norm (Appendix A.1). Muon is the oracle of the spectral norm fixed above: writing M = UΣV⊤ for the rank-r singular value decomposition of M ∈ Rm×n , the LMO direction is A(M) = −UV⊤ ∈ Rm×n ,
polar(M) := −A(M), (4) an orthogonalization, punscaled. Muon’s reference implementation rescales it by max(1, m/n) (Jordan et al. p 2024b) and the RMS→RMS reading of the layer norm by m/n: positive per-layer constants, invisible to sign(·), which we carry in the step size (7) and not in the geometry (Appendix A.1). In practice the oracle is applied to a momentum estimate rather than to a gradient; (5) below gives the full iteration. What Muon must transmit is that dense direction, precisely what a bandwidth-limited link cannot accommodate; our object is therefore its matrix-aware geometry at a one-bit budget.
4
Theory
From SignSGD to Sign A. SignSGD was introduced as a compressed SGD: a convergent method, of which only the sign of the update is transmitted. Nothing in that construction is specific to SGD, so one may apply it to any optimizer that emits a direction, expecting the compressed method to inherit what the direction contributed. LMO-based optimizers give grounds for that expectation, their theory being uniform in the geometry: one analysis covers every norm, which enters only through its oracle and a pair of norm-equivalence constants (Pethick et al. 2025a; Kovalev 2025; Riabinin et al. 2025). Were signing a direction harmless, it would be harmless across that family, and the member one seeks to compress is Muon. The second ground for the expectation is where it fails. The sign step is itself an LMO, steepest descent in ℓ∞ (Bernstein and Newhouse 2024), so signing a Muon direction composes two oracles, each sound alone. The composition is an LMO for no norm. An oracle for a norm ∥ · ∥ returns D = −A(G) with ⟨G, D⟩ = max∥Y∥≤1 ⟨G, Y⟩ = ∥G∥dual , nonnegative since 0 is feasible; Theorem 1 provides a gradient on which the composition drives that inner product strictly negative. The guarantee is forfeited in the composition, not in either factor. The Sign A family. Let A be any optimizer built on LMO directions. A Sign A method initializes M0 = 0 and at each iteration t ≥ 1 performs Mt = µMt−1 + (1 − µ) Gt , M̃t = Mt or (1 − µ)Gt + µMt (Nesterov),
(5) Dt = −A(M̃t ), st = sign(Dt ) ∈ {±1}m×n , Xt = Xt−1 − ηt st , where Xt ∈ Rm×n is the parameter matrix, Gt = ∇f (Xt−1 ; ξt ) the stochastic gradient at the current iterate, µ ∈ [0, 1) the momentum coefficient and ηt the learning rate; A(·) is the LMO, and sign(·) acts element-wise on the structured direction Dt , with sign(0) resolved to an independent random ±1 so that the transmitted alphabet stays binary. Momentum is in exponential-moving-average form throughout; the heavy-ball form differs by the positive factor 1/(1 − µ), which sign(·) and the LMO both absorb, so no result below distinguishes them. Three placements of the sign. Of the three, only SignMuon is a Sign A method. All three keep the momentum of (5) and the update Xt = Xt−1 − ηt st , and differ only in where the sign acts on M̃t : (SignMuon: after), sign polar(M̃t ) st = polar sign(M̃t ) (MuonUSign: before), sign polar(sign(M̃t )) (MuonSign: both). (6) The three are Algorithms 2, 4 and 5 (Appendix A.18), all transmitting one bit per matrix parameter on the uplink. On the downlink SignMuon and MuonSign distribute a ±1-valued object and so cost one bit each way, whereas MuonUSign’s server-side polar(·) is dense and goes at full precision.
4.1
Centralized Learning
Centrally, SignMuon is applied to the matrix-valued parameters (ndim ≥ 2), while vector parameters (biases, BatchNorm) and the final classification layer are trained with AdamW, the design of Jordan et al. (2024b), whose LMO branch is what Li and Hong (2025) and Riabinin et al. (2025) analyse. We approximate polar(·) by a 5th-order Newton– Schulz iteration rather than a full SVD (Algorithm 1). One further implementation choice has consequences for every experiment below. Per-layer step sizes: the unit-gain heuristic. Write Pℓ for the matrix a method applies to layer ℓ, of shape m×n (output × input dimension). It belongs to one of two families, each of exactly known Frobenius norm: Pℓ = UV⊤ with ∥Pℓ ∥F = √ r, r = min(m, n), for the lmo-terminated methods, and √ Pℓ = sℓ ∈ {±1}m×n with ∥Pℓ ∥F = mn for the signterminated ones. The two scale differently with layer shape, so no single global η is appropriate for both families, or across layers within one. We fix the shape dependence a priori and tune only a shape-free base rate η0 , giving layer ℓ the step size ηℓ = η0 λℓ with ( p √ λlmo = max(1, m/n), m ℓ λℓ = (7) =⇒ √ ∥Pℓ ∥F λsign = 1/ n. ℓ The criterion is that every layer’s update have the same rootmean-square input–output gain, the average-case form of the spectral scaling condition (Yang, Simon, and Bernstein 2023; Large et al. 2024), so that η0 is the per-step RMS gain. Its lmo branch is not new: it reproduces the aspect-ratio factor that the reference Muon implementation already applies (Jordan et al. 2024b). That agreement is the external check we rely on, and it is what licenses applying the same criterion to the sign family, for which no such convention exists. We treat (7) as a heuristic and apply it uniformly. Appendix A.17 gives the derivation and the measurement selecting the exponent 1 sign = n−a over µP’s 1 (Yang et al. 2021). 2 in λℓ
4.2
Divergence of the Three Sign Placements
The descent property of the Muon LMO direction is lost under sign compression, before or after the oracle: in each of the three placements the compressed step can become an ascent direction on a smooth objective. We refute the descent property on linear objectives, the simplest smooth functions: f (X) = ⟨G, X⟩ = Tr(G⊤ X),
∇f (X) ≡ G.
(8)
Gradient descent and full-precision Muon drive f → −∞ here, so a rule that instead drives f → +∞ is unambiguously ascending (Remark 1 in Appendix A.9 restores Assumption 1 without moving any trajectory below). On (8) the step is the constant matrix s(G) whatever the momentum, so momentum affects neither convergence nor divergence (Proposition 1, Appendix A.3) and f (Xt ) − f (Xt−1 ) = −ηt G, s(G)
(9)
for every µ ∈ [0, 1) and either momentum rule. A single G with ⟨G, s(G)⟩ < 0 therefore makes f increase at every step, and such a G exists for each placement at small size.
SignMuon ↑
f(W) = Tr(G ⊤ W)
10 −50
6 MuonSign ↑
−100
−10
−150
−20
MuonUSign ↑
0
20
40
60
0
20
iteration SignMuon
EF21-SignMuon
2
0
−30
−200
EF21-SignMuon ↑
4
0
f(Xt )
20
0
40
60
0
20
iteration MuonUSign
MuonSign
40
60
SignSGD
Muon
iteration
EF21-MuonUSign
EF21-MuonSign
Figure 1: All eight methods on the three counterexample instances; the ascending method is drawn heavy and named in each panel. Left: SignMuon, 4 × 4 (Theorem 1). Centre: MuonUSign and MuonSign on their shared 5 × 5 instance (Theorems 2–3); both panels plot (8). Right: EF21-SignMuon, 2 × 2 (Theorem 4), normalized units at η = 1. Trajectories are momentum-free without loss (Proposition 1; Lemma 4 for EF21-SignMuon). Theorems 1–3 (summary). There exists G ∈ R4×4 with ⟨G, s(G)⟩ < 0 for SignMuon, and G ∈ R5×5 with ⟨G, s(G)⟩ < 0 for MuonUSign and for MuonSign simultaneously. On the corresponding objective (8) each method ascends at every iteration, for every ηt > 0, every µ ∈ [0, 1) and either momentum rule, and f (Xt ) → +∞ whenever P t ηt = ∞. Both instances are explicit and both inner products exact rationals; Appendices A.4–A.6 state the theorems, prove them, and bound the two shapes from below. Figure 1 (left, centre) demonstrates the ascents. Negative results of this kind exist for uncompressed Muon as well: Parshakova et al. (2026) show that it need not converge on convex Lipschitz problems. Ours are due to the compressor rather than the geometry, and hold on a smooth objective.
4.3
Centralized Error Feedback: EF21-SignMuon
Theorems 1–3 rule out all three placements of the sign around the oracle. The classical remedy for a biased compressor is error feedback: keep what the compressor discarded and fold it into the next message (Seide et al. 2014; Karimireddy et al. 2019). We work throughout in its EF21 form (Richtárik, Sokolov, and Fatkhullin 2021), which stores an estimator and compresses the difference to it, and so needs no boundedgradient assumption. Its most direct use for SignMuon keeps the geometry, the sign after the LMO, and applies error feedback to the oracle’s output. The resulting method, EF21SignMuon (Algorithm 3), tracks an estimate dest t of the polar factor Dt = polar(M̃t ), updated by a scaled sign of the residual, est est dest t = dt−1 + αt sign Dt − dt−1 , (10) αt = mean Dt − dest t−1 , and steps Xt = Xt−1 − ηt dest t .
Error feedback does not repair this placement: for every step size and momentum setting there is a smooth objective on which EF21-SignMuon diverges. Theorem 4 (Divergence of EF21-SignMuon) For every L > 0, step size η > 0, momentum coefficient µ ∈ [0, 1), and either momentum variant, there is an L-smooth (Assumption 2), bounded-below (Assumption 1) function f : R2×2 → R on which EF21-SignMuon started at X0 = 0 diverges: for an explicit constant c = c(f ) > 0, f (Xt+2 ) − f (Xt ) = c Lη 2 > 0
(t ≥ 3),
(11)
so f (Xt ) → +∞. In particular, no step-size rule η = η(L, µ) using only the smoothness and momentum constants can make the method convergent. The construction (Appendix A.9) turns the shared magnitude against the method. Its 2 × 2 LMO target has a large off-diagonal that reverses sign every step, holding the residual, and with it αt , at Θ(1), and a small constant on the diagonal, which that magnitude overshoots at every step; the diagonal estimate settles into a period-two cycle whose average has the wrong sign, and the coordinate it drives diverges. The objective is not convex, unlike the linear ones of Theorems 1–3: sustaining the cycle requires a target sequence that never settles, which here a bounded periodic field supplies. Dimension is not implicated, 2 × 2 being where the scaled sign’s worst-case contraction 1/d is most favourable, nor is momentum: Figure 5 (Appendix A.9) records the same rate for every µ and both variants.
4.4
Centralized Error Feedback: EF21-MuonUSign and EF21-MuonSign
The shared magnitude αt is not itself the defect: the two methods below couple all coordinates through the same scalar and converge. What fails is the target. Error feedback needs an estimator whose target varies with the step size, and the
polar factor polar(M̃t ) is not one: it is not Lipschitz in its argument, so it can move by Θ(1) between consecutive rounds however small η is. Compressing the gradient in its place restores that dependence, and the mechanism is then EF21-Muon (Gruntkowska et al. 2025), the framework within which we apply sign compression. That framework compresses the two directions of the link separately, through a pair (C ↑ , C ↓ ) of contractive compressors. In both directions we take the scaled sign C(Y) = mean |Y| sign(Y): one bit per parameter, plus one scalar per layer. EF21-MuonUSign takes the pair (C, I), a compressed uplink and a full-precision model back, the appropriate allocation when only the uplink is constrained. It maintains a gradient estimator gtest , updated from the residual est ∆t = M̃t − gt−1 : αt = mean(|∆t |),
est gtest = gt−1 + αt sign(∆t ),
(12)
and takes the step Xt = Xt−1 − ηt Dt with Dt = −A(gtest ) ≈ Ut Vt⊤ , the polar factor of the estimator gtest rather than of ∇f . The sign in (12) acts on the internal compression residual alone, so the uplink stays at one bit per parameter (Algorithm 6). EF21-MuonSign takes the pair (C, C): one bit in each direction. Its downlink compressor is a second error-feedback loop, on the model rather than the gradient, and it splits the method into two iterates: Xt = Xt−1 − ηt Dt Wt = Wt−1 + αt↓ sign(Xt − Wt−1 )
(server model),
(broadcast model), (13) with Dt = −A(gtest ) as before, and αt↓ = mean |Xt − Wt−1 |. The server model X takes the exact LMO step and never leaves the server; what crosses the downlink is the one-bit update of W, the only model the rest of the method observes, since gradients, momentum and the uplink residual are all computed there, whereas the guarantee bounds the gradient at X. The rate is preserved under the second loop √ at a step size smaller by a factor of r in the layer rank, a penalty the analysis cannot avoid because the scaled sign contracts in the Euclidean norm and not in the layer norm the spectral geometry requires (Remark 5, Appendix A.10); Section 5.3 measures what it costs in practice. Both methods descend where the placements they repair ascend: Figure 1 (centre) has them on the 5 × 5 instance of Theorems 2–3. Appendix A.10 shows them to be exact instances of the EF21-Muon framework, the one substantive check being that the scaled sign is a contractive compressor (Lemma 5), so they inherit its guarantees (Theorem 5). Under Assumptions 1–2 both reach mint≤T E∥∇f (Xt )∥2∗ = O(T −1/2 ), the standard smooth nonconvex rate, which uncompressed Muon attains as well: one bit changes the con0 1 stant and not the rate. Under P (L , L )-smoothness EF21MuonUSign reaches mint i E∥∇i f (Xt )∥∗ = O(T −1/4 ) at a constant step size (Corollaries 1–2). Memory is the other cost, one model-sized buffer per compressed channel: EF21MuonUSign holds the gradient estimator on each client, and EF21-MuonSign holds that estimator and, on the server, the broadcast model W. Of these, only the client-side buffer is a
practical constraint, since the server is the better-provisioned side.
4.5
Federated Learning
In the federated setting (2) the placement decides where the oracle runs. With the sign after it, each client must orthogonalize its own momentum: it computes a stochastic gradient at the broadcast model, maintains a momentum buffer, applies the Muon LMO (Algorithm 1), then uploads the elementwise sign of the result. The server takes a majority vote, P (j) sagg = sign , and steps Xt = Xt−1 − ηt sagg t t , as j st SignSGD does (Bernstein et al. 2019). With the sign before, (j) the client uploads sign(M̃t ); the server votes, then applies a single LMO to the outcome. The vote rather than the average is what keeps the oracle’s argument a sign matrix, so that the server-side method is exactly the MuonUSign of (6); the error-feedback methods below instead average, as their framework prescribes. The direction that returns is dense, so MuonUSign broadcasts the model at full precision, whereas MuonSign signs that direction once more and broadcasts sign(Dt ). SignMuon and MuonSign therefore send a ±1valued object down as well as up, the vote itself in the first case, free of ties at an odd client count, so both directions cost one bit; and since every client applies the same update, copies started from a common X0 never drift. Error feedback changes the uplink message, not where the oracle runs: each client sign-compresses the residual between its estimator and the quantity it would otherwise have sent, the polar factor for EF21-SignMuon and the momentum for (j) (j) the other two, and sends (st , αt ); the server averages these into a global estimator. The extra per-layer scalar leaves the uplink at ≈1 bit per parameter, but that estimator is a scaled average of signs and so is dense, and the vote argument lapses: the full model must be broadcast unless a second error-feedback loop compresses it, as EF21-MuonSign does. Error feedback meets the same obstruction for SignSGD, where it is analysed for a single worker only (Karimireddy et al. 2019) and its distributed forms compress the return path with a second loop of their own (Tang et al. 2019). The complete procedures are Algorithms 8–9.
5
Experiments
Descent in practice. On a deterministic convex quadratic (Appendix A.12) the first-order term of the descent lemma can be measured directly, through the alignment ρt = ⟨∇f, Dt ⟩/(∥∇f ∥F ∥Dt ∥F ) between the gradient and the direction actually taken. The direction descends when ρt > 0, and Theorems 1–3 provide instances on which ρt < 0; on random instances this does not occur, all three placements keeping ρt bounded away from zero at every step. The counterexamples describe a worst case rather than a typical one, which is what permits the network results below to run contrary to them.
5.1
Centralized Learning
We compare all six sign-based methods against Muon, SignSGD, SGD and Adam on CIFAR-10 (Krizhevsky 2009)
test accuracy (%)
95
95
95
94
94
94
93
93
93
92
92
92
Muon SignMuon MuonUSign MuonSign
91 90 30
40
50
60
70
Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign
91 90 30
40
epoch
50
60
Muon SGD SignSGD Adam
91 90
70
30
40
epoch
50
60
70
epoch
Figure 2: Centralized ResNet-18 on CIFAR-10: test accuracy from epoch 25 at each method’s selected η0 (Table 1). Panels group the sign placements, the EF21 variants and the baselines; Muon is the gray dashed reference, bands ±1 s.d. over three seeds.
Method SignMuon Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign MuonUSign Adam SignSGD MuonSign SGD
η0 0.02 0.1 0.02 0.05 0.005 0.02 0.001 0.002 0.1 0.02
Test acc (%) 94.60 ± 0.15 94.35 ± 0.27 94.31 ± 0.11 94.14 ± 0.07 94.04 ± 0.10 93.98 ± 0.12 93.37 ± 0.27 93.37 ± 0.26 93.31 ± 0.21 93.04 ± 0.14
Ep. to 90% 7.7 7.7 9.0 10.3 11.0 10.3 20.0 19.0 17.7 21.3
Table 1: Centralized ResNet-18 / CIFAR-10, 75 epochs. Test accuracy is the mean ± s.d. over three seeds of the last five epochs; “Ep. to 90%” is the mean epoch at which it first reaches 90%.
with a ResNet-18 adapted to low-resolution images, over 75 epochs with η0 cosine-annealed to zero. The only tuned hyperparameter is η0 , selected per method on a held-out split and read identically across methods through the unit-gain rule (7). Numbers average three seeds; differences below the seed spread are not claimed (Appendix A.11). SignMuon ranks first, but by less than one seed spread over Muon: what Table 1 supports is that it matches Muon at one bit per parameter, not that it exceeds it. The separation that does resolve is the 1.2 points over SignSGD, which spends the same budget without the lmo; the geometry accounts for it, not the compressor. Error feedback is not free here, EF21-SignMuon lying 0.29 points below SignMuon against standard deviations of 0.11 and 0.15. Both families order the placements after, before, both sides, the last no better than SignSGD. The threshold column separates the methods more
Up
Down
Rds. to 80%
Test acc (%)
Muon 0.1 32 SignMuon 0.1 1.09 EF21-SignMuon 0.02 1.09 MuonUSign 0.05 1.09 EF21-MuonSign 0.05 1.09 EF21-MuonUSign 0.01 1.09 MuonSign 0.02 1.09 SGD 0.05 32 SignSGD 0.01 1.09 Adam 0.001 32
32 1.09 32 32 1.09 32 1.09 32 1.09 32
260 540 640 500 980 900 860 1240 1140 —
85.98 ± 0.26 85.72 ± 0.24 84.71 ± 0.15 84.56 ± 0.35 83.99 ± 0.28 83.56 ± 0.41 82.94 ± 0.19 81.69 ± 0.37 81.44 ± 0.15 77.12 ± 1.04
Optimizer
η0
Table 2: CIFAR-10 federated learning on CNN2, ordered by accuracy: N = 11 clients, homogeneous split, 2000 rounds at batch 192, momentum 0.9. Test accuracy is the mean of the final five evaluations over five seeds, ± one s.d. across seeds; Up and Down are bits per parameter per round each way (Appendix A.14). Every method but Adam reached 80% on all five seeds, Adam on none. sharply than accuracy does: 7.7 epochs to 90% for SignMuon against 19.0–21.3 for SGD, SignSGD and Adam.
5.2
Federated Learning
We compare the same ten methods on CNN2 (two convolutional blocks with BatchNorm and an MLP classifier), with CIFAR-10 split homogeneously across N = 11 clients and no local steps; N is odd, so the majority vote cannot tie. Rates are tuned per method at the reporting horizon on a split held out before the client partition; two schemes cover all six, worker- and server-side LMO (Algorithms 8–9, Table 13). Federation separates the methods far more. At one bit per parameter in both directions SignMuon reaches 85.72%
4.6
Validation loss
4.4
3.35
4.2 3.30
4.0 3.8
1950
2100
2250
3.6 3.4 500 Muon SignSGD SignMuon
1000
1500
Optimizer step
MuonUSign MuonSign EF21-SignMuon
2000 EF21-MuonUSign EF21-MuonSign (W)
Figure 3: NanoGPT speedrun, 8×H100: validation loss against optimizer step, one run per method; dotted is the target 3.28, and EF21-MuonSign is drawn at its broadcast model W. The inset magnifies the boxed tail, where SignSGD lies above the range shown. against Muon’s 85.98%, about one seed standard deviation apart, and exceeds SignSGD by 4.3 points, far more than centrally. Five seeds resolve the three placements: they span 2.8 points in the order after, before, both sides, all three clearing SignSGD, the last by 1.5 points where centrally it was level. The second error-feedback loop is not the source of the cost: EF21-MuonSign, compressed in both directions, stands marginally ahead of the uplink-only EF21-MuonUSign. Less favourably for the theory, the two methods carrying an unconditional guarantee trail SignMuon by several seed spreads, as they do centrally, so what the guarantee costs here is charged to the placement. EF21-MuonSign is scored at its server model Xt , not the model its clients hold (13); the two track each other here, and Section 5.3 shows that they need not (Remark 4, Appendix A.10).
5.3
Method
Step
η0
Val. loss Steps to 3.35
Muon (record #40) EF21-SignMuon SignMuon MuonUSign EF21-MuonUSign EF21-MuonSign (W) MuonSign SignSGD
lmo lmo sign lmo lmo lmo sign sign
0.06 0.06 0.03 0.06 0.06 0.06 0.03 0.03
3.2785 3.2860 3.2881 3.2959 3.3203 3.3213 3.3249 3.4049
1.00× 1.02× 1.02× 1.05× 1.13× 1.14× 1.14× –
EF21-MuonSign (X)
lmo
0.06
5.5198
–
Table 3: NanoGPT after 2330 steps (611M tokens), one run per method. Record #40 reports 3.2780 ± 0.0009 over five seeds, so differences below ∼0.003 are noise; “Steps to 3.35” is relative to Muon. The last row is the server model X of the same run as the W row.
wall-clock. Second, on the sign-after placement error feedback is free: EF21-SignMuon and SignMuon differ by 0.002, below the ∼0.003 noise level, so the two are indistinguishable and jointly the strongest compressed methods here. The target both compress, polar(M̃t ), is an orthogonal factor whose entries stay evenly spread in these runs, the regime in which the scaled sign loses least (Appendix A.16). Third, EF21-MuonSign’s two models (13) separate at this width. The run has a single client, so its broadcast model W is the only point at which a gradient is ever evaluated, and W is indistinguishable from EF21-MuonUSign: the compressed downlink costs nothing where training occurs. The server model X, the iterate the guarantee bounds, settles 2.2 nats above it, a persistent offset that Appendix A.16 localizes to one layer type, the zero-initialized output projection of each MLP block (c_proj). This is the mechanism of Remark 4 (Appendix A.10), not a tuning failure: only a spectrally contractive downlink compressor removes it. The three settings therefore agree on the placement, and the placement they select is the one the theory excludes. Signafter is what Theorem 1 makes diverge and error feedback repairs for no (L, η, µ) (Theorem 4), yet in all three the strongest compressed method is a sign-after one, ahead of every variant carrying an unconditional guarantee.
Language Modelling
We test where the matrices are large enough for the layerrank dependence of Corollary 1 to take effect: the moddednanoGPT speedrun (record #40), a 12-layer transformer with 768 × 3072 hidden matrices, trained on 611M FineWeb tokens on 8×H100 (Jordan et al. 2024a). Each method replaces the record’s Muon on the hidden matrices and gates, leaving all else untouched; our Muon run is record #40’s own update rule, re-implemented without its Triton kernels. Rates are fixed a priori by the unit-gain rule at one η0 per family, so every contrast is matched-hyperparameter (Appendix A.16). Three conclusions follow (Table 3, Figure 3). First, composing the sign with the lmo transfers to language modelling: all six such methods improve on SignSGD by at least 0.08 in validation loss, and the best two, EF21-SignMuon and SignMuon, lie within 0.01 of full-precision Muon at equal
6
Conclusion
A sign step and a spectral step are each an LMO, sound alone; composed, they are an LMO for no norm, and the descent property each factor guarantees is lost in the composition. On small explicit instances, at every step size and momentum, every placement of the sign around the oracle can turn the update into an ascent direction on a linear objective: SignMuon after the LMO, MuonUSign before it, and MuonSign on both sides. Where error feedback is applied then decides whether it repairs this. On the oracle’s output it does not: the polar factor can move by a constant however small the step size, so one shared magnitude cannot track it, and for every (L, η, µ) some L-smooth objective makes EF21-SignMuon diverge. On the gradient it does: EF21-MuonUSign attains the standard nonconvex rate at a one-bit uplink and EF21-MuonSign
at one bit in each direction. Experiment ranks the methods in the opposite order, the strongest compressed method on all three architectures being a sign-after one, which carries no theoretical guarantee. We document that tension rather than resolve it: what the counterexamples preclude is a guarantee covering every problem in the class, not one holding under further conditions that ordinary problems satisfy. Identifying such conditions is the main open question, together with the convergence rate for the (L0 , L1 ) setting under a compressed downlink and whether any one-bit compressor contracts in a layer norm.
Acknowledgments We thank Alexander Tyurin for drawing our attention in June 2026 to the concurrent SignMuon work of Mishra, Trivedi, and Kumar (2026).
Author Contributions A. Kravatskiy proposed compressing Muon with a sign compressor in February 2026 and led the project. M. Smirnova ran the preliminary experiments and wrote the first draft of the paper. The divergence counterexamples are due to A. Kravatskiy; the reduction of EF21-MuonUSign and EF21MuonSign to the EF21-Muon framework of Gruntkowska et al. (2025) was carried out jointly. Both authors ran the experiments reported here and expanded and edited the manuscript into its present form.
Code Availability Code for this paper is available at https://github.com/ intsystems/signmuon. The repository records the exact command and the hyperparameters behind each reported number.
References Ahn, K.; Xu, B.; Abreu, N.; Fan, Y.; Magakyan, G.; Sharma, P.; Zhan, Z.; and Langford, J. 2025. Dion: Distributed Orthonormalized Updates. arXiv:2504.05295. Alistarh, D.; Grubic, D.; Li, J.; Tomioka, R.; and Vojnovic, M. 2017. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. In Advances in Neural Information Processing Systems (NeurIPS), 1709–1720. Amsel, N.; Persson, D.; Musco, C.; and Gower, R. M. 2025. The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm. arXiv:2505.16932. Bernstein, J. 2025. Deriving Muon. https://jeremybernste. in/writing/deriving-muon. Blog post. Bernstein, J.; and Newhouse, L. 2024. Old Optimizer, New Norm: An Anthology. arXiv:2409.20325. Bernstein, J.; Wang, Y.-X.; Azizzadenesheli, K.; and Anandkumar, A. 2018. signSGD: Compressed Optimisation for Non-Convex Problems. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, 560–569. PMLR. Bernstein, J.; Zhao, J.; Azizzadenesheli, K.; and Anandkumar, A. 2019. signSGD with Majority Vote is Communication Efficient and Fault Tolerant. In International Conference on Learning Representations (ICLR). arXiv:1810.05291.
Beznosikov, A.; Horváth, S.; Richtárik, P.; and Safaryan, M. 2023. On Biased Compression for Distributed Learning. Journal of Machine Learning Research, 24(276): 1–50. Bolatov, A.; Riabinin, A.; Kornilov, N.; Veprikov, A.; Horváth, S.; Takáč, M.; and Beznosikov, A. 2026. LionMuon: Alternating Spectral and Sign Descent for Efficient Training. arXiv:2605.19811. Cesista, F. L. 2025. Steepest Descent Under Schatten-p Norms. https://leloykun.github.io/ponder/steepest-descentschatten-p/. Blog post. Chen, X.; Chen, T.; Sun, H.; Wu, Z. S.; and Hong, M. 2020. Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:1906.01736. Cutkosky, A.; and Mehta, H. 2020. Momentum Improves Normalized SGD. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, 2260–2268. PMLR. Douillard, A.; Feng, Q.; Rusu, A. A.; Chhaparia, R.; Donchev, Y.; Kuncoro, A.; Ranzato, M.; Szlam, A.; and Shen, J. 2023. DiLoCo: Distributed Low-Communication Training of Language Models. arXiv:2311.08105. Grishina, E.; Smirnov, M.; and Rakhuba, M. 2025. Accelerating Newton–Schulz Iteration for Orthogonalization via Chebyshev-type Polynomials. arXiv:2506.10935. Gruntkowska, K.; Gaponov, A.; Tovmasyan, Z.; and Richtárik, P. 2025. Error Feedback for Muon and Friends. arXiv:2510.00643. Gupta, A.; Celente, R.; Shivanna, A.; Braithwaite, D. T.; Dexter, G.; Tang, S.; Udagawa, H.; Silva, D.; Ramanath, R.; and Keerthi, S. S. 2025. Effective Quantization of Muon Optimizer States. arXiv:2509.23106. Horváth, S.; Kovalev, D.; Mishchenko, K.; Richtárik, P.; and Stich, S. 2023. Stochastic distributed learning with gradient quantization and double-variance reduction. Optimization Methods and Software, 38(1): 91–106. Jin, R.; Liu, Y.; Huang, Y.; He, X.; Wu, T.; and Dai, H. 2025. Sign-Based Gradient Descent With Heterogeneous Data: Convergence and Byzantine Resilience. IEEE Transactions on Neural Networks and Learning Systems, 36(2): 3834–3846. Jordan, K.; Bernstein, J.; Rappazzo, B.; @fernbear.bsky.social; Boza, V.; You, J.; Cesista, F.; Koszarsky, B.; and @Grad62304977. 2024a. modded-nanogpt: Speedrunning the NanoGPT baseline. https://github.com/ KellerJordan/modded-nanogpt. Jordan, K.; Jin, Y.; Boza, V.; You, J.; Cesista, F.; Newhouse, L.; and Bernstein, J. 2024b. Muon: An optimizer for hidden layers in neural networks. https://kellerjordan.github.io/ posts/muon/. Karimireddy, S. P.; Rebjock, Q.; Stich, S.; and Jaggi, M. 2019. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, 3252–3261. PMLR.
Kovalev, D. 2025. Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization. arXiv:2503.12645. Kravatskiy, A.; Kozyrev, I.; Kozlov, N.; Vinogradov, A.; Merkulov, D.; and Oseledets, I. 2025. Ky Fan Norms and Beyond: Dual Norms and Combinations for Matrix Optimization. arXiv:2512.09678. Krizhevsky, A. 2009. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto. https://www.cs.toronto.edu/~kriz/learningfeatures-2009-TR.pdf. Large, T.; Liu, Y.; Huh, M.; Bahng, H.; Isola, P.; and Bernstein, J. 2024. Scalable Optimization in the Modular Norm. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2405.14813. Li, J.; and Hong, M. 2025. A Note on the Convergence of Muon. arXiv:2502.02900. Liu, J.; Su, J.; Yao, X.; Jiang, Z.; Lai, G.; Du, Y.; Qin, Y.; Xu, W.; Lu, E.; Yan, J.; Chen, Y.; Zheng, H.; Liu, Y.; Liu, S.; Yin, B.; He, W.; Zhu, H.; Wang, Y.; Wang, J.; Dong, M.; Zhang, Z.; Kang, Y.; Zhang, H.; Xu, X.; Zhang, Y.; Wu, Y.; Zhou, X.; and Yang, Z. 2025. Muon is Scalable for LLM Training. arXiv:2502.16982. Mishra, N.; Trivedi, K.; and Kumar, P. 2026. SignMuon: Communication-Efficient Distributed Muon Optimization. arXiv:2605.16311. Parshakova, T.; Khaled, A.; Crawshaw, M.; Garrigos, G.; and Gower, R. M. 2026. Muon Does Not Converge on Convex Lipschitz Functions. arXiv:2605.08980. Penedo, G.; Kydlíček, H.; Ben Allal, L.; Lozhkov, A.; Mitchell, M.; Raffel, C.; Von Werra, L.; and Wolf, T. 2024. The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale. In Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track. arXiv:2406.17557. Pethick, T.; Xie, W.; Antonakopoulos, K.; Zhu, Z.; SilvetiFalls, A.; and Cevher, V. 2025a. Training Deep Learning Models with Norm-Constrained LMOs. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, 49069–49104. PMLR. Pethick, T.; Xie, W.; Erdogan, M.; Antonakopoulos, K.; Silveti-Falls, A.; and Cevher, V. 2025b. Generalized Gradient Norm Clipping & Non-Euclidean (L0 , L1 )-Smoothness. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2506.01913. Qian, X.; Gaponov, A.; Malinovsky, G.; and Richtárik, P. 2026. Communication-Efficient Gluon in Federated Learning. arXiv:2604.10689. Riabinin, A.; Shulgin, E.; Gruntkowska, K.; and Richtárik, P. 2025. Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs). arXiv:2505.13416. Richtárik, P.; Sokolov, I.; and Fatkhullin, I. 2021. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 4384–4396.
Safaryan, M.; and Richtárik, P. 2021. Stochastic Sign Descent Methods: New Algorithms and Better Theory. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, 9224–9234. PMLR. Seide, F.; Fu, H.; Droppo, J.; Li, G.; and Yu, D. 2014. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Interspeech 2014, 1058–1062. Shah, I.; Polloreno, A. M.; Stratos, K.; Monk, P.; Chaluvaraju, A.; Hojel, A.; Ma, A.; Thomas, A.; Tanwer, A.; Shah, D. J.; Nguyen, K.; Smith, K.; Callahan, M.; Pust, M.; Parmar, M.; Rushton, P.; Mazarakis, P.; Kapila, R.; Srivastava, S.; Singla, S.; Romanski, T.; Vanjani, Y.; and Vaswani, A. 2025. Practical Efficiency of Muon for Pretraining. arXiv:2505.02222. Shulgin, E.; AlRashed, S.; Orabona, F.; and Richtárik, P. 2026. Beyond the Ideal: Analyzing the Inexact Muon Update. In Proceedings of the 29th International Conference on Artificial Intelligence and Statistics (AISTATS). arXiv:2510.19933. Sun, T.; Wang, Q.; Li, D.; and Wang, B. 2023. Momentum Ensures Convergence of SIGNSGD under Weaker Assumptions. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, 33077–33099. PMLR. Takezawa, Y.; Koloskova, A.; Jiang, X.; and Stich, S. U. 2026. FedMuon: Federated Learning with Bias-corrected LMO-based Optimization. In International Conference on Learning Representations (ICLR). arXiv:2509.26337. Tang, H.; Yu, C.; Lian, X.; Zhang, T.; and Liu, J. 2019. DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, 6155–6165. PMLR. Thérien, B.; Huang, X.; Defazio, A.; Rish, I.; and Belilovsky, E. 2025. MuLoCo: Muon is a practical inner optimizer for DiLoCo. arXiv:2505.23725. Yang, G.; Hu, E. J.; Babuschkin, I.; Sidor, S.; Liu, X.; Farhi, D.; Ryder, N.; Pachocki, J.; Chen, W.; and Gao, J. 2021. Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 17084–17097. arXiv:2203.03466. Yang, G.; Simon, J. B.; and Bernstein, J. 2023. A Spectral Condition for Feature Learning. arXiv:2310.17813. Zhang, X.; and Gao, H. 2025. On Provable Benefits of Muon in Federated Learning. arXiv:2510.03866.
A A.1
Appendix
Preliminaries: LMO, Muon, and generalized smoothness
This subsection states in full the definitions that Section P 3 uses in abbreviated form. Equip Rm×n with the inner product ⟨M, D⟩ = i,j Mij Dij , let ∥ · ∥ be a norm on it, let B = {D ∈ Rm×n : ∥D∥ ≤ 1} be its unit ball, and let ∥M∥dual = maxD∈B ⟨M, D⟩ be the dual norm. The Linear Minimization Oracle (LMO) of ∥ · ∥ minimizes a linear form over the unit ball: it outputs A(M) ∈ arg min ⟨M, D⟩ = − D ∈ B : ⟨M, D⟩ = ∥M∥dual , (14) D∈B
Hence ⟨M, A(M)⟩ = −∥M∥dual ≤ 0: the oracle returns a steepest-descent direction with respect to ∥ · ∥, normalized to the unit ball. The minimizer need not be unique, whence the inclusion; at rank-deficient M we use the rank-r selection fixed in the next paragraph. An LMO method minimizes a differentiable objective F by stepping along this direction: at the iterate X it forms an effective update direction M, a stochastic gradient or a momentum estimate in every method below, and moves along A(M), the minimizer over B of the first-order model D 7→ F (X) + ⟨M, D⟩. Each layer of Section 3 carries its own norm and so its own oracle (Riabinin et al. 2025); for the role of the construction in optimizer design see (Bernstein and Newhouse 2024; Bernstein 2025; Pethick et al. 2025a; Kovalev 2025; Riabinin et al. 2025; Cesista 2025; Kravatskiy et al. 2025). Muon is the instance in which each matrix layer carries the spectral norm ∥ · ∥2→2 , so that the oracle uses the matrix structure of the gradient and the update direction is obtained by orthogonalizing the gradient matrix (Bernstein and Newhouse 2024). Let M = UΣV⊤ be the singular value decomposition (SVD) of the matrix M ∈ Rm×n , where U ∈ Rm×r and V ∈ Rn×r are the orthonormal matrices of singular vectors, Σ ∈ Rr×r is the diagonal matrix of singular values, and r = rank(M). Then the LMO direction is A(M) = −UV⊤ : Muon selects an orthonormal update direction corresponding to the solution of the linear minimization problem induced by the spectral norm geometry. Orthogonalization equalizes the singular values of the update, so that the directions in which the gradient is weak are not crowded out by the dominant ones (Jordan et al. 2024b); large-scale pretraining studies report a corresponding efficiency gain over AdamW (Liu et al. 2025; Shah et al. 2025). The reference implementation obtains Ut Vt⊤ from a fixed number of Newton–Schulz iterations rather than from an SVD (Jordan et al. 2024b); Algorithm 1 gives the procedure and the coefficients we use. p Choice of layer norm and the shape factor. Muon is also presented in the RMS→RMS operator norm, n/m ∥ · ∥2→2 on Rm×n (Bernstein and Newhouse 2024; Pethick et al. 2025a). Theptwo readings give different oracles: the unit ball of p p n/m ∥ · ∥2→2 is the spectral ball scaled by m/n, so its LMO is − m/n UV⊤ . The unscaled −UV⊤ therefore belongs to the spectral norm and to no other, since a norm whose oracle it is has ∥M∥dual = ⟨M, UV⊤ ⟩ = ∥M∥∗ for every M and hence equals ∥ · ∥2→2 by biduality. We take the spectral norm, in which Assumption 2 and every statement below are stated, and treat the shape factor as a step-size question, for three reasons. It is a positive per-layer constant, so it changes neither sign(·) p m/n is not nor the sign of any descent inner product, and no result of this paper is sensitive to it. The RMS→RMS value p in fact the factor Muon uses: the reference implementation applies max(1, m/n) (Jordan et al. 2024b), which agrees with it only for m ≥ n and is what our unit-gain rule returns (Appendix A.17). And that rule must also scale the two sign-terminated placements, for which no norm supplies a scale at all: by Theorems 1 and 3 they are oracles for none. Finally, Corollary 2 requires Assumption 2 only in its weaker layer-wise (L0 , L1 ) form, which replaces the constant Lgi by 0,g Li + L1,g i ∥∇i g(X)∥∗ (Riabinin et al. 2025; Pethick et al. 2025b): for every layer i and all parameter tuples X, Y, 1,g ∥∇i g(X) − ∇i g(Y)∥∗ ≤ L0,g (15) i + Li ∥∇i g(X)∥∗ ∥Xi − Yi ∥2→2 , again with one pair of constants per layer for g = f and per layer and client for g = fj ; at L1,g = 0 the display is Assumption 2. i It is Assumptions 8–9 of Gruntkowska et al. (2025), the hypotheses of the theorem Corollary 2 quotes, stated there as here for arbitrary pairs: the tuples may differ in every block although only block i enters the bound. That quantifier is strong. Fixing Xi = Yi while varying the remaining blocks forces ∇i g(X) = ∇i g(Y), so each ∇i g depends on its own block alone, and a function satisfying the bound with finite constants is additively separable across layers. At p = 1, the setting of every counterexample and synthetic measurement in this paper, the restriction is empty and the display is ordinary (L0 , L1 )smoothness. For a multilayer network it is the framework’s idealization, and we inherit it unweakened: the descent lemma behind Theorem 5 applies the bound along a step in which every layer moves, which the restriction to pairs differing in one block would not license.
A.2
Width-one blocks: vector parameters
The setup of Section 3 asks each block to be a matrix, and min(mi , ni ) = 1 is permitted: a bias, a normalization gain, or any other one-dimensional parameter is the block R1×ni or Rmi ×1 . Gluon states the same product space and leaves the norm on each block arbitrary, so it too admits them without comment (Riabinin et al. 2025); Scion is explicit, giving biases the RMS norm with oracle b/∥b∥RMS (Pethick et al. 2025a). Fixing the spectral norm on every block recovers nearly that: on a width-one block the rank is one, the spectral, nuclear and Euclidean norms coincide, and polar(g) = g/∥g∥ √ 2 for g ̸= 0. Assumptions 1 and 2 then read unchanged, and the norm-equivalence constant of Corollary 1 improves to ρ̄i = ri = 1.
Substituting polar(g) = g/∥g∥2 into (6) gives, on R1×n , sign(polar(g)) = sign(g),
polar(sign(g)) = √1n sign(g),
and the two-sided placement returns sign(g) as well: all three are SignSGD up to a positive constant the step size absorbs. The ascent instances of Theorems 1–3 accordingly have min(m, n) ≥ 2. √ √ The unit-gain multipliers of√Appendix A.17 need no special case either: λ = m/∥P∥F returns (1, 1/ n) for the lmo and sign families on R1×n , and ( m, 1) on Rm×1 . Which parameters reach the methods. Little of this affects our experiments, since the sign methods are applied where Muon is. Centralized and federated runs give the rule to parameters of two or more dimensions other than the classifier head, and route biases, BatchNorm scales and that head to AdamW as the auxiliary group, whose bandwidth cost Appendix A.14 counts. On nanoGPT we keep record #40’s grouping unchanged: one-dimensional scalars, the embeddings and the head go to its distributed Adam, the hidden matrices and the two kinds of gate weight to the method under test. One gate is width-one, the 1 × 12 smear_gate, and there polar is ℓ2 normalization, so the three sign-terminated methods reduce exactly to SignSGD on it and the lmo five to normalized momentum. In the CIFAR runs the corresponding parameters are one-dimensional, and our implementation returns those from the oracle unchanged rather than ℓ2 -normalized, which differs from polar by a positive scale and so alters neither the sign nor the descent inner product.
A.3
Divergence on linear objectives: the ascent criterion and momentum
The criterion quoted in Section 4 collapses each of the three methods to a single scalar inequality and removes momentum from the discussion entirely. Proposition 1 (Ascent criterion on linear objectives) Run any of the three methods (6) on the linear objective (8) with G ̸= 0, from an arbitrary X0 , with any momentum coefficient µ ∈ [0, 1) under either the Standard or the Nesterov rule. Then M̃t = γt G with γt > 0, the update direction is the constant matrix s(G) obtained by substituting G for M̃t in (6), and f (Xt ) − f (Xt−1 ) = −ηt G, s(G) . In P particular, if ⟨G, s(G)⟩ < 0 then f strictly increases at every iteration for any ηt > 0, and f (Xt ) → +∞ whenever t ηt = ∞ (for instance, for any constant step size). Proof of Proposition 1. On the linear objective (8) the gradient is globally constant, Gt = G, so the momentum buffer of (5) Pt−1 is Mt = (1 − µ) i=0 µi G = (1 − µt ) G. Both momentum rules then return a positive multiple of G, ( 1 − µt , (Standard), (16) M̃t = γt G, γt = t+1 1 − µ , (Nesterov), both positive for t ≥ 1 because µ ∈ [0, 1); the Nesterov case is (1 − µ)G + µ(1 − µt )G. (Under the heavy-ball convention every γt is multiplied by 1/(1 − µ), which changes nothing below.) The elementwise sign(·) and the Muon LMO polar(·) are each invariant under multiplication by a positive scalar, so evaluating (6) at M̃t = γt G returns the same matrix as evaluating it at G; that is, st = s(G) for every t, independently of µ and of the momentum variant. Hence f (Xt ) − f (Xt−1 ) = ⟨G, Xt − Xt−1 ⟩ = Pt −ηt ⟨G, s(G)⟩, which is (9). PIf ⟨G, s(G)⟩ < 0, then f (Xt ) = f (X0 ) − ⟨G, s(G)⟩ i=1 ηi increases strictly at every step and diverges to +∞ whenever t ηt = ∞. ■ By Proposition 1, each divergence theorem reduces to exhibiting a single gradient G with ⟨G, s(G)⟩ < 0; the three proofs below accomplish exactly this, and momentum requires no further comment.
A.4
Proof of Theorem 1 (Divergence of SignMuon)
Theorem 1 (Divergence of SignMuon) There is a matrix G ∈ R4×4 with G, sign(polar(G)) = − 42468 103 < 0. Hence SignMuon ascends on (8): f strictly increases at every iteration for all ηt > 0, all µ ∈ [0, 1), and both momentum variants. For SignMuon s(G) = sign(polar(G)), so by (9) it suffices to construct G ∈ R4×4 with ⟨G, sign(polar(G))⟩ < 0. Group the SVD G = UΣV⊤ of an invertible G as the polar decomposition G = QH, with Q = UV⊤ = polar(G) orthogonal and H = VΣV⊤ ≻ 0 symmetric. Only the symmetric part of Q⊤ sign(Q) then contributes to the trace against H: ⟨G, sign(polar(G))⟩ = tr HQ⊤ sign(Q) = H, sym(Q⊤ sign(Q)) , (17) so a counterexample with polar factor Q exists precisely when λmin sym(Q⊤ sign(Q)) < 0: necessity because H ≻ 0, sufficiency by taking H = ww⊤ + δI at a minimizing eigenvector w and δ > 0 small, which keeps G invertible and its polar factor unique. The question thus concerns orthogonal matrices alone.
We construct G ∈ R4×4 by defining a specific orthogonal matrix O and a specific rank-1 principal component u1 v1⊤ . Let the orthogonal matrix O be given by the following exact rational numbers: 101 20 2 −2 1 −20 97 20 −20 . (18) O= 2 101 103 −2 20 −2 20 −101 −2 Because no entry is zero, its element-wise sign matrix S = sign(O) is uniquely defined. Now, let u1 and v1 be the following exact unit vectors: 10 10 1 −3 1 3 u1 = √ (19) . 10 , v1 = √ 309 309 −10 10 10 One can easily verify that Ov1 = u1 , meaning u1 and v1 act perfectly as left and right singular vectors for this orthogonal space. The crucial feature of this geometry is that the Frobenius inner product between this rank-1 component and the sign matrix S yields an exact, strictly negative fraction: ⟨u1 v1⊤ , S⟩ = u⊤ 1 Sv1 = −
43 . 103
(20)
We construct the gradient matrix G by assigning a large singular value (σ1 = 1001) to this pathological component and a singular value of 1 to the rest of the orthogonal space. Exactly, 100303 30060 −99994 99994 1 −30060 −8709 30060 −30060 G := 1000 u1 v1⊤ + O = , (21) 99994 30060 −99994 100303 309 99994 30060 −100303 99994 or, to one decimal, 324.6 −97.3 G≈ 323.6 323.6
97.3 −28.2 97.3 97.3
−323.6 323.6 97.3 −97.3 . −323.6 324.6 −324.6 323.6
(22)
Since Ov1 = u1 and v1⊤ v1 = 1, Gv1 = 1000 u1 (v1⊤ v1 ) + Ov1 = 1001 u1 , so (u1 , v1 ) is a singular pair of G with σ1 = 1001. For any w ⊥ v1 we have Gw = Ow; as O is orthogonal and Ov1 = u1 , the restriction O|v1⊥ is an isometry onto u⊥ 1 , hence σ2 = σ3 = σ4 = 1. Moreover, with uk = Ovk for k ≥ 2, P
⊤ ⊤ k≥2 uk vk = O I − v1 v1
= O − u1 v1⊤ ,
⊤ so UG VG = u1 v1⊤ + (O − u1 v1⊤ ) = O. All four singular values are positive, so G is invertible and polar(G) = O is its unique polar factor. The sign matrix (26) of Theorems 2–3 is full rank as well, so in all three proofs the argument of polar is invertible and its polar factor is unique: no statement depends on the selection rule fixed above for rank-deficient arguments. Substituting the resulting matrix G into the descent condition yields:
⟨G, S⟩ = ⟨1000 u1 v1⊤ + O, S⟩ = 1000⟨u1 v1⊤ , S⟩ + ⟨O, S⟩.
(23)
532 . Therefore: The inner product ⟨O, S⟩ is equivalent to the L1 norm (sum of absolute values) of O, which equals exactly 103 43 532 42468 ⟨G, S⟩ = 1000 − + =− ≈ −412.31. (24) 103 103 103
Here S = sign(O) = sign(polar(G)) = s(G), so ⟨G, s(G)⟩ = − 42468 103 < 0. By Proposition 1, SignMuon strictly ascends, f (Xt ) − f (Xt−1 ) = 42468 η > 0 at every iteration, for every η t t > 0, every µ ∈ [0, 1), and both momentum variants; 103 f (Xt ) → +∞ under any non-summable step size. ■
A.5
Proof of Theorem 2 (Divergence of MuonUSign)
Theorem 2 (Divergence of MuonUSign) There is a matrix G ∈ R5×5 with G, polar(sign(G)) ≈ −13.89 < 0. Hence MuonUSign ascends on (8) for all ηt > 0, all µ ∈ [0, 1), and both momentum variants. MuonUSign (Algorithm 4) applies the sign before the LMO, so s(G) = polar(sign(G)). By (9) it suffices to construct G ∈ R5×5 with ⟨G, polar(sign(G))⟩ < 0. Here the step depends on G only through the magnitudes |Gij | and the sign pattern S = sign(G); write D = polar(S) for the direction it produces. Under the randomized convention S ∈ {±1}m×n throughout, and the entrywise identity Gij = |Gij | Sij holds without exception, both sides vanishing wherever Gij = 0. Consequently P G, polar(sign(G)) = i,j |Gij | Sij Dij , (25) P and likewise ⟨G, sign(D)⟩ = i,j |Gij | Sij sign(Dij ) for the MuonSign step of Theorem 3. Every summand in (25) is nonnegative unless some entry is mismatched, Sij Dij < 0. It therefore suffices to exhibit one sign matrix carrying a mismatched entry: inflating |Gij | there, with the other magnitudes held fixed, drives the sum below zero. Fix the full-rank sign matrix S ∈ {−1, 1}5×5 , −1 −1 1 1 1 −1 −1 1 −1 −1 1 −1 , (26) S = 1 −1 1 1 1 −1 −1 1 1 1 1 −1 1 √ and let D = polar(S) be its (unique, since S is full rank) polar factor. A direct computation gives D4,2 = −1/ 17 ≈ −0.2425 < 0 while sign(Di,j ) = Si,j at all 24 other entries; equivalently, sign(D) and S disagree at exactly the single entry (4, 2), where S4,2 = +1. We exploit this lone mismatch. Define G = ϵ S + (M − ϵ) e4 e⊤ 2,
ϵ > 0, M > ϵ,
(27)
so that G4,2 = M > 0 and Gi,j = ϵSi,j otherwise; hence sign(G) = S and polar(sign(G)) = D for every M > 0. The descent inner product splits as X ⟨G, D⟩ = ϵ Si,j Di,j + M D4,2 = ϵ C + M D4,2 , (28) (i,j)̸=(4,2)
√ P where C := (i,j)̸=(4,2) |Di,j | = 10.366 > 0 is fixed (every such entry agrees in sign with S), while M D4,2 = −M/ 17 → √ −∞. Thus ⟨G, D⟩ < 0 for any M > 17 Cϵ ≈ 42.7 ϵ; with ϵ = 1, M = 100 one obtains ⟨G, D⟩ = −13.89, for the exact polar factor that the theorem is stated over. By Proposition 1, MuonUSign strictly ascends on f (X) = ⟨G, X⟩ for every ηt > 0, every µ ∈ [0, 1), and both momentum variants; f (Xt ) → +∞ under any non-summable step size. ■
A.6
Proof of Theorem 3 (Divergence of MuonSign)
Theorem 3 (Divergence of MuonSign) For the same matrix G ∈ R5×5 as in Theorem 2, G, sign(polar(sign(G))) = −76 < 0. Hence MuonSign ascends on (8) for all ηt > 0, all µ ∈ [0, 1), and both momentum variants. MuonSign (Algorithm 5) signs the polar factor as well, so s(G) = sign(polar(sign(G))) = sign(D). We reuse the same S and G of (26)–(27): since sign(G) = S, the bidirectional step is the constant matrix sign(D), which agrees with S at all 24 2 entries except (4, 2), where sign(D4,2 ) = −1 = −S4,2 . Using Si,j = 1 everywhere, ⟨G, sign(D)⟩ = ϵ
X
Si,j sign(Di,j ) + M sign(D4,2 )
(i,j)̸=(4,2)
(29)
= 24 ϵ − M. This is negative for every M > 24ϵ; with ϵ = 1, M = 100 it equals exactly −76. By Proposition 1, MuonSign strictly ascends on f (X) = ⟨G, X⟩ for every ηt > 0, every µ ∈ [0, 1), and both momentum variants; f (Xt ) → +∞ under any non-summable step size. In particular, the same 5 × 5 linear instance is an ascent instance for the uplink-only placement (MuonUSign) and for the bidirectional one (MuonSign) alike. ■
A.7
Comparison with the convergence claim for SignMuon
Concurrently, Mishra, Trivedi, and Kumar (2026) introduced the sign-after-LMO method under the same name SignMuon: their algorithm √ forms the momentum√Mt , computes its polar factor, and steps along St = sign(polar(Mt )), normalized to Dt = St / mn; after absorbing√1/ mn into η this is the SignMuon step of Section 4. Their abstract and contributions attribute to this method an O(1/ T ) stationarity guarantee; the theorem that establishes the rate is stated, accurately, for a gradient-sign instantiation. The distance between the two statements is the subject of this subsection. Two facts resolve it, and neither contradicts Theorem 1: the finalized rate is proved for an update that computes no polar factor and carries no momentum, and the one bound of theirs that does apply to the SignMuon update is an inequality whose right-hand side exceeds its left-hand side on the instance of Theorem 1, at every iteration and for every step size, so that it is satisfied there while the method ascends. PT −1 √ The two components of their analysis. Their stationarity measure is GT = T1 t=0 E ∥∇f (Xt )∥1 / mn , controlled through the per-entry sign-error probabilities qij,t = Pr St,ij ̸= sign([∇f (Xt )]ij ) | Xt of the transmitted sign matrix St . The first component is generic. For an arbitrary sign oracle, the conditional identity 1 X E ⟨∇f (Xt ), Dt ⟩ Xt = √ [∇f (Xt )]ij 1 − 2qij,t (30) mn i,j and the descent lemma of spectral smoothness telescope into ∗
GT ≤
T −1 X
L∗ 2 1 f (X0 ) − f + η+ [∇f (Xt )]ij qij,t . E √ ηT 2 T t=0 mn i,j {z } | X
(31)
=: RT
e t ), where G e t is an The second component estimates the residual RT , and it is here that the oracle is fixed: for St = sign(G 2 unbiased stochastic gradient with coordinatewise variance at most σij /nb at mini-batch size nb , a Markov–Jensen argument P √ √ yields [∇f (Xt )]ij qij,t ≤ σij / nb , hence RT ≤ 2∥σ∥1 / mn nb with ∥σ∥1 = i,j σij . The residual vanishes as nb → ∞, √ and the choice nb = T produces the O(1/ T ) rate. The finalized rate is not a result about SignMuon. The oracle of the second component transmits the sign of the stochastic gradient itself. That update invokes neither the momentum buffer nor√the polar factor; as an algorithm it is SignSGD at batch size nb , in single-worker and majority-vote form, normalized by 1/ mn and analysed under spectral rather than coordinatewise smoothness, which their own comparison identifies as the sole improvement over Bernstein et al. (2018). Nor is the restriction incidental. The Markov–Jensen estimate bounds the probability of a sign error by the ratio of noise to signal, √ σij /( nb |[∇f (Xt )]ij |), and is therefore available exactly when sampling noise is the only mechanism by which a transmitted sign can disagree with the gradient’s. For the SignMuon oracle the disagreement is structural rather than stochastic: even with exact gradients (σ ≡ 0),√qij,t is the indicator that sign(polar(Mt )) and sign(∇f (Xt )) differ at (i, j), a quantity that no batch size reduces. The O(1/ T ) rate accordingly attaches to the gradient-sign update, and to SignMuon their analysis offers only (31) with RT unestimated. Scope of the generic bound. Inequality (31) is valid for every sign oracle, and for that reason asserts nothing until RT is estimated. By (30), the summand of RT at time t exceeds the corresponding summand of GT precisely when E[⟨∇f (Xt ), Dt ⟩ | Xt ] ≤ 0, that is, precisely when the expected step fails to be a descent direction. Whenever this occurs at every t, the right-hand side of (31) exceeds the left-hand side termwise and the inequality holds irrespective of how the iterates behave. The bound therefore has content only where the transmitted sign is already positively aligned with the gradient in expectation; that alignment is the property a convergence proof for SignMuon would have to establish, and it is the property Theorem 1 refutes. On the instance of Theorem 1. Consider the linear objective (8) with the 4 × 4 gradient G of Theorem 1. By Proposition 1 the gradient equals G and the update direction equals the constant matrix sign(polar(G)) at every iteration, whatever the momentum, so the oracle is deterministic and qij is the indicator that sign(polar(G))ij ̸= sign(Gij ). Identity (30) then evaluates exactly: X < 0. (32) |Gij | (1 − 2qij ) = G, sign(polar(G)) = − 42468 103 √ Dividing by
i,j
mn = 4, every term of RT exceeds the corresponding term of GT by the same amount, so that RT = GT + 10617 103
for every T.
(33)
The right-hand side of (31) therefore exceeds the left-hand side by at least 10617/103 for every η > 0, every L∗ and every T : the inequality is satisfied and constrains nothing. What the trajectory actually does is read off the same identity,
f (Xt ) − f (Xt−1 ) = −η⟨G, Dt ⟩ = η · 10617 103 > 0, the divergence of Theorem 1: the excess RT − GT of (33) and the per−1 iteration ascent rate η f (Xt ) − f (Xt−1 ) are the same number. The one assumption of theirs the linear instance lacks is lower boundedness, and the modification of Remark 1 applies unchanged: f is unbounded below only on a half-space the iterates never enter, where a smooth bounded replacement restores the assumption without moving the trajectory or any quantity above. In their terms, Theorem 1 exhibits a smooth instance on which the sign-error probabilities qij,t of the SignMuon oracle, averaged over the entries with weights [∇f (Xt )]ij , exceed 21 at every iteration. Any rate extracted from (31) requires that weighted average to stay below 12 by a uniform margin, and no assumption of theirs implies such a bound for sign(polar(Mt )). Their theorems stand as guarantees for majority-vote SignSGD under spectral smoothness. A convergence guarantee for SignMuon they are not, and Theorem 1 shows that none is available at this level of generality.
A.8
Extended comparison with S-Muon
P Taking the norms dual to the Ky Fan k-norms, Kravatskiy et al. (2025) obtain the Fanion family, whose updates i≤k ui vi⊤ interpolate between the rank-one step of the nuclear norm and Muon’s full-rank UV⊤ at k = min(m, n); a conic combination of LMO algorithms is again an LMO algorithm, for the norm dual to the corresponding combination of dual norms. Their S-Muon is one such combination, τ UV⊤ + (1 − τ ) c sign(Mt ) with fixed τ ∈ [0, 1], c > 0 (their notation differs; we reserve α for compressor contraction and η for the learning rate). There the sign enters inside the oracle, so the step is still an LMO for an explicit norm and inherits the convergence theory of one; our three placements act around the oracle. A caution from the same work applies to us directly: they exhibit an LMO method (rank-one Neon) markedly worse than Muon in practice despite sharing its convergence asymptotics in the bounds of Kovalev (2025) and Riabinin et al. (2025), from which our own guarantee descends. A rate of the form O(T −1/2 ) is not a prediction of the performance a method will attain.
A.9
Proof of Theorem 4 (Divergence of EF21-SignMuon)
Theorem 4 (Divergence of EF21-SignMuon) For every L > 0, step size η > 0, momentum coefficient µ ∈ [0, 1), and either momentum variant, there is an L-smooth (Assumption 2), bounded-below (Assumption 1) function f : R2×2 → R on which EF21-SignMuon started at X0 = 0 diverges: for an explicit constant c = c(f ) > 0, f (Xt+2 ) − f (Xt ) = c Lη 2 > 0
(t ≥ 3),
(34)
so f (Xt ) → +∞. In particular, no step-size rule η = η(L, µ) using only the smoothness and momentum constants can make the method convergent. Recall from the main text that EF21-SignMuon (Algorithm 3) does not step along the polar factor Dt = polar(M̃t ) itself, est but along the error-feedback estimate dest t of (10), followed by Xt = Xt−1 − η dt . A single magnitude αt rescales the signs of all entries at once, and it is this coupling that the counterexample exploits. We now prove Theorem 4. Proof idea The mechanism. The error-feedback update (10) moves every entry of dest t by the same magnitude αt ; only the signs are individual. Suppose then that one entry must track a target alternating between +1 and −1 while another must track a small constant −ε. The alternating entry keeps its residual, and with it αt , at Θ(1); the constant entry is therefore displaced by ±Θ(1) at every step and can only oscillate about its target, never settle on it. Which side of the target the oscillation favours is decided by its phase, and a one-bit sign carries no information by which a phase could be corrected. In the unfavourable phase the estimate of the constant entry has a time average of the sign opposite to −ε, and the iterate driven by that estimate moves the wrong way forever. From the sketch to an instance. The sketch is not yet a counterexample: in EF21-SignMuon the quantity tracked is the polar factor Dt = polar(M̃t ), of unit spectral norm, and the gradients behind it must all come from one smooth function. Both a ±b 2 2 constraints are met at size 2 × 2 by the reflections D̄± = ±b −a with a + b = 1: one matrix the oracle can emit carries 24 both roles of the sketch at once, the large alternating entries on the off-diagonal (b = 25 ) and the small constant ones on the 7 diagonal (a = 25 ), coupled by the shared αt . On these targets the estimate enters a period-two cycle in which the time average 7 of the (2, 2)-entry is positive although every target value is − 25 , so (Xt )22 travels to −∞, the direction in which the objective increases (Figure 1, right). Nor does the mechanism rest on degeneracy: the momentum matrices of the divergent tail have condition number 16 9 throughout. The role of the preamble. The unfavourable phase must be arranged. From dest 0 = 0, the alternating targets alone lock the estimate into a period-two cycle whose diagonal average has the correct sign. The recursion (10) is piecewise affine, the pieces indexed by the sign pattern of the residual, and the harmless cycle and the wrong-sign one lie in different pieces, which the dynamics cannot join. The target sequence of Part 2 therefore opens with two preamble steps, whose sole purpose is to place the estimate in the piece containing the wrong-sign cycle. Eliminating the parameters. The step size and the smoothness constant only rescale the trajectory, so η = 1 and one value of L suffice (Part 1). Momentum determines only which gradients produce a given target sequence, not how the recursion (10) responds to it; solving the momentum recursion for the gradients therefore settles every (µ, variant) at once (Part 3).
Accordingly the proof has three parts, and they are independent. Part 1 removes L and η by rescaling. Part 2 carries the dynamics, and is a finite computation in exact rational arithmetic: on one fixed sequence of LMO targets, the estimate enters a limit cycle whose diagonal has the wrong sign. Part 3 is an existence argument only: it exhibits a smooth function whose gradients generate that target sequence for every µ and either momentum variant. A reader willing to grant that some smooth objective produces the targets can stop after Part 2. Proof Part 1: rescaling. 2 Lemma 1 (Scale reduction) If f˜ is L̃-smooth with EF21-SignMuon iterates X̃t at step size 1, then f (X) := Lη f˜(X/η) is L̃ Lη 2 ˜ L-smooth and its run at step size η (same µ, same variant, from 0) satisfies Xt = η X̃t and f (Xt ) = f (X̃t ).
L̃
Proof. ∇f (X) = Lη ∇f˜(X/η), so f is L-smooth. Suppose Xs = η X̃s for s < t: the two gradients then differ by the positive L̃ Lη factor L̃ , which Mt and M̃t (positive combinations of past gradients) inherit and polar discards. Hence Dt and dest t match the normalized run, and Xt = η X̃t . ■ It therefore suffices to exhibit, for each (µ, variant), a C ∞ L̃-smooth f˜ on which the normalized run (η = 1) obeys (34); that f˜ may be taken bounded below (Assumption 1) is shown afterwards (Remark 1). We fix η = 1 from now on. Part 2: the limit cycle of the estimate. The dynamical core of the proof is the behavior of the recursion (10) on the fixed target sequence t D1 = S1 , D2 = S2 , Dt = D̄(−1) (t ≥ 3), (35) 7/25 ±24/25 D̄± = ±24/25 −7/25 , (36) −4/5 3/5 −4/5 S1 = −3/5 −4/5 , S2 = 3/5 . 0 0 7 24 7 , − 25 ), while their off-diagonal ± 25 The divergence originates in the tail (t ≥ 3): the reflections D̄± share the diagonal ( 25 reverses sign at every step. The rotation S1 and the rank-one S2 form a two-step preamble. Only S2 requires comment: at a rank-deficient argument the spectral-ball LMO is not unique, and Section 3 resolves it through the thin SVD that retains only the nonzero singular directions, polar(M) = UV⊤ with one column of U, V per nonzero singular value of M; under that convention a rank-one matrix of unit spectral norm, such as S2 , is its own polar factor, and this is also what the implementation computes. The next lemma says what the preamble is for, and that something like it is unavoidable. a ±b 2 2 Lemma 2 (The cycle reached without the preamble) Write D̄± = ±b −a with a + b = 1 and 0 < a < b. On the purely t (−1) alternating targets Dt = D̄ (t ≥ 1), the recursion (10) started from dest 0 = 0 enters a period-two cycle immediately, 1 −1 b−a −1 1 a a+b est namely dt = 2 −1 −1 for odd t and 2 1 1 for even t. Over a period its (2, 2)-entry averages − 2 : the same sign as every target value −a, at half the magnitude. + − 1 −1 est + est Proof. Put m = a+b D̄− − 0 has signs − − and mean modulus m, so d1 = m −1 −1 . Next, D̄ − d1 = 2 . The residual a−m b+m −+ b−a −1 1 est est modulus b, giving d2 = 2 b+m m−a has signs + + (as a < m) and mean 1 1 . Repeating once returns d1 . The 1 b−a a average of the two (2, 2)-entries is 2 −m + 2 = − 2 . ■ That cycle is harmless: the alternation by itself does not diverge, and no choice of (a, b) makes it do so. The divergence comes + −− from a second period-two cycle of the same recursion, whose residuals carry a uniform sign pattern ( + + + and − − ) where those of the harmless cycle are mixed. Since (10) is affine on each sign-pattern cell, the dynamics cannot pass from one cycle to the other; the preamble exists solely to place dest 2 in the cell of the wrong-sign cycle, which is what Lemma 3 verifies.
Lemma 3 (Wrong-sign limit cycle) On the targets (35), the recursion (10) from dest 0 = 0 enters at t = 3 the exact period-two cycle dest t = dB (odd t), dA (even t), where −61 −201 1 1 131 −9 dB = 200 dA = 200 (37) −61 −61 , 131 131 . 7 7 Over a period its (2, 2)-entry averages 12 (dA )22 + (dB )22 = + 40 , opposite in sign to every target value (Dt )22 = − 25 . Proof.
Substituting (35) into (10) gives the values t αt dest t
1 1 10
7 10 −7 7 −7 −7
2
3
4 (then 2-periodic)
21 20 1 7 −7 20 7 7
131 200
24 25
dB
dA
(38)
Φ1
ψ1
1
Φ2
ψ2
ρ1+
1
−γW22 γ h(W22 )
0.5
ρ2+
0.0
0.75
ϕ(|s|/r) bk /(‖Ck ‖F r)
0.50
−0.5 0
1.00
0
0.25
−1.0
0.00 −1
−1
ρ1−
0
1
2
−1.5
ρ2−
0.00
W12
0.25
0.50
visited region
−0.25
0
W21
2
−1
W22
0
s/r
1
P Figure 4: The components of the objective f˜ = g + k bk of Part 3, as implemented. First two panels: the periodic ramps − ψ1 , ψ2 and their bounded antiderivatives Φ1 , Φ2 over two periods; the marked residues ρ+ i (kept at odd iterates) and ρi (even iterates) lie on the plateaus where ψi = ±1 exactly, so from t ≥ 4 the off-diagonal gradient entries alternate between +A and −A. The drawn ψi is the implementation’s ramp; the trajectory samples only the plateaus, on which any C ∞ choice agrees with it. Third panel: the divergence term −γW22 and its bounded replacement γ h(W22 ) of Remark 1; the two agree on the visited 7 region {W22 ≤ 10 } (shaded), so the floor changes no iterate while restoring Assumption 1. Fourth panel: the correction bk of (41) along the ray Zk + s Ck /∥Ck ∥F , normalized by ∥Ck ∥F r, with the cutoff ϕ: bk vanishes at Zk while ∇bk (Zk ) = Ck , and its support, the ball {∥W − Zk ∥F ≤ r}, contains no iterate other than its own center. −7 −61 1 Each residual Dt − dest t−1 has strictly nonzero entries, so the signs are unambiguous; e.g. at t = 3 it is 100 −131 −63 , all negative. From t = 3 the targets are 2-periodic and the pair (dB , dA ) reproduces itself: D̄+ − dB and −(D̄− − dA ) are both 24 24 entrywise positive with mean 24 25 , so dB + 25 J = dA and dA − 25 J = dB (J all-ones). ■ 7 Since Xt = Xt−1 − dest t (recall η = 1), over one period the (2, 2)-coordinate changes by −(dA + dB )22 = − 20 . Consequently 7 7 49 ˜ a term −γW22 in f , with γ := 12 , increases by γ · 20 = 240 per period. This is the divergence, provided a genuine smooth function produces the targets (35); Part 3 constructs one.
Part 3: realization by a smooth function.
7 1 Fix (µ, variant) and set γ = 12 , ν = 1+2µ , and
1+µ (standard), 1−µ 1+µ A= (Nesterov). (1 − µ)(1 + 2µ) A=
We build f˜ = g + The field is where Φi (w) =
(39)
P3
Rw
k=1 bk from a periodic-plus-linear field g and three localized corrections bk , all explicit.
g(W) = −γ W22 + A Φ1 (W12 ) + A Φ2 (W21 ), R pi
ψi and ψi : R → [−1, 1] is a fixed C ∞ , pi -periodic function with 0 21 , p1 = 20
7 p2 = 20 ,
0
(40) ψi = 0,
1 δ = 100 ,
+ − − equal to +1 on [ρ+ i − δ, ρi + δ] and −1 on [ρi − δ, ρi + δ] (mod pi ), where − 131 140 ρ+ 1 = 200 , ρ1 = 200 ;
− 61 ρ+ 2 = 200 , ρ2 = 0.
9 The two intervals are disjoint mod pi (their centers are 200 > 2δ apart), so such a ψi exists; the zero-mean condition, met by balancing the rest of the period, makes Φi periodic (hence bounded). On each of the two intervals Φ′i = ψi = ±1 exactly. Figure 4 draws both ramps, together with the remaining components of f˜. The corrections pin the first three gradients. Fix once a C ∞ cutoff ϕ : R → [0, 1] with ϕ ≡ 1 on [0, 12 ] and ϕ ≡ 0 on [1, ∞), 1 put r = 50 , and set bk (W) = Ck , W − Zk ϕ ∥W − Zk ∥F /r , (41) centered at the first three iterates (from Lemma 3) 1 7 −7 1 7 −7 Z1 = 0, Z2 = 10 Z3 = 20 7 7 , 7 7 .
Each bk is C ∞ , supported in {∥W − Zk ∥F ≤ r}; since its linear factor vanishes at Zk while ϕ(0) = 1, ∇bk (Zk ) = Ck . We choose Ck := Ĝk − ∇g(Zk ) with the explicit Ĝk of (42) below, so that ∇f˜(Zk ) = Ĝk . Every term of f˜ has a bounded Hessian, so f˜ is C ∞ and L̃-smooth for a finite L̃(µ, variant). Lemma 4 (Realization) For every µ ∈ [0, 1) and either variant, EF21-SignMuon on this f˜ (η = 1, from 0) generates exactly the targets (35). Proof. The required gradients. The buffer recursion Mt = µMt−1 + (1 − µ)Gt of (5) can be solved for the gradients: prescribing the buffers (Mt )t≥1 forces Gt = (Mt − µMt−1 )/(1 − µ), and these are the gradients the function must deliver. Define accordingly the transient gradients Mt − µMt−1 Ĝt = (t = 1, 2, 3; M0 = 0) (42) 1−µ 0 ±A 0 ±1 ± and the field gradient G± = ±A −γ , where the prescribed buffer values M1,2,3 are given below. With M̄ = ±1 −γ , the factorization 24/25 ∓7/25 M̄± = D̄± ∓7/25 337/300 (43) (second factor ≻ 0, det = 1) shows polar(M̄± ) = D̄± , with singular values 34 and 43 ; this is the condition number 16 9 cited in the proof idea. Standard momentum (M̃t = Mt ). Take M1 = S1 , M2 = S2 , M3 = M̄− ; then Ĝ1,2,3 are the explicit matrices (42). Feeding t t G(−1) for t ≥ 4 keeps Mt = M̄(−1) , because (1 − µ)G± = M̄± − µM̄∓ with A as in (39). As polar(S1 ) = S1 (orthogonal) and polar(S2 ) = S2 (rank one), (43) yields the targets (35). Nesterov momentum (M̃t = (1 + µ)Mt − µMt−1 ). It is here that the orthogonality of S1 is needed. The Nesterov direction involves two consecutive buffers, so prescribing the tail t ≥ 4 already fixes M3 , and only the preamble remains to absorb the mismatch at t = 3; and the set of matrices with a given polar factor D is {DH : H ≻ 0}, which is three-dimensional when D is orthogonal but only one-dimensional (a positive scalar) when D has rank one. A preamble of two rank-one targets leaves too little freedom: a symbolic check shows that it admits no realization once µ ≳ 0.3. One orthogonal target supplies 1 1 S1 H1 , M2 = 1+µ (S2 + µM1 ), enough freedom, of which the construction uses a single scalar, the τ below. Take M1 = 1+µ t 0 ±ν ′− ′(−1) ′± M3 = M̄ and Mt = M̄ (t ≥ 4), where M̄ = ±ν −γ , H1 = diag(1, 1 + τ ), and, for µ > 0, 2 1+µ − 44 τ = 140(1+µ) 1+2µ 117µ > 0. (At µ = 0 the Nesterov rule reads M̃t = Mt and is the standard case already treated, so nothing is left to prove there.) Then t M̃1 = S1 H1 and M̃2 = S2 have polar factors S1 , S2 , and M̃t = M̄(−1) for t ≥ 4 (since ν(1 + 2µ) = 1). The one nontrivial step is t = 3. Set H3 := D̄− M̃3 ; since (D̄− )2 = I, this is the same as M̃3 = D̄− H3 . The stated τ is exactly the value making s (s > 0) the numerators of its two leading minors are polynomials H3 symmetric, and H3 ≻ 0 for all µ ∈ (0, 1): under µ = 1+s − in s with nonnegative coefficients. Hence polar(M̃3 ) = D̄ , completing (35). t The function delivers these gradients. It remains to verify ∇f˜(X̃t−1 ) = Ĝt for t ≤ 3 and = G(−1) for t ≥ 4, by induction along the run: as long as the gradients match this prescription, the iterates are those computed in Part 2, and the prescription need only be checked at those points. By Lemma 3 the iterates X̃0 , X̃1 , X̃2 are exactly the centers Z1 , Z2 , Z3 , where ∇f˜ = Ĝ1,2,3 131 7 > 2r), and every later iterate has (1, 2)-entry ≥ 200 while the by construction. The three balls are disjoint (∥Zj − Zk ∥F ≥ 10 centers have it ≤ 0, so no ball is re-entered. For t ≥ 4 the query lies in the field, where 0 Aψ1 (W12 ) . ∇g(W) = Aψ2 (W21 ) −γ The period shift X̃t+2 − X̃t = −(dA + dB ) advances W12 by exactly +p1 and W21 by exactly −p2 per period, so the two − coordinates travel to +∞ and −∞ respectively while, mod pi , they hold the residues ρ+ i at odd indices and ρi at even ones; (−1)t there ψi = ±1, giving ∇g = G .■ Proof of Theorem 4. By Lemma 4 the normalized run produces the targets (35), so by Lemma 3 its estimate locks onto the wrong-sign cycle and X̃t+2 − X̃t is a constant shift. Along it Φ1 , Φ2 return to their values and the corrections bk vanish, so 7 49 49 only the linear term acts: f˜(X̃t+2 ) − f˜(X̃t ) = −γ(− 20 ) = 240 > 0. By Lemma 1, f then obeys (34) with c = 240 . As L̃ (L, η, µ, variant) were arbitrary, no rule η = η(L, µ) can prevent divergence. ■ Remark 1 (Boundedness below) Only the linear term −γW22 makes f˜ unbounded below, and only as W22 → +∞, a region 7 the iterates never enter, since (X̃t )22 ≤ 10 throughout (it decreases after the transient). Replacing −γW22 by any C ∞ function that agrees with it on {W22 ≤ 1} and is constant on {W22 ≥ 2} therefore leaves the whole trajectory, and (34) with it, unchanged while rendering f˜ bounded below (Assumption 1); the theorem is stated with this modification in force.
f(Xt ) − f(X0 )
150
100
50
0 0
200
400
600
800
1000 0
200
iteration μ=0
400
600
800
1000
iteration μ = 0.5
μ = 0.9
μ = 0.95
μ = 0.99
49 slope 480
Figure 5: Momentum does not prevent the divergence of EF21-SignMuon. For each momentum coefficient µ and variant, EF21SignMuon is run on the corresponding instance of Theorem 4 and f (Xt ) − f (X0 ) is plotted; left: standard momentum, right: 49 Nesterov. Every setting diverges at the common rate 480 (dotted). Subtracting f (X0 ) removes the only genuinely µ-dependent offset (the field constant A(µ) scales a bounded periodic term); what remains is a bounded transient, largest as µ → 1, on top of the shared linear divergence. Remark 2 (The construction is not convex) Theorems 1–3 run on a linear, hence convex, objective; f˜ is nonconvex, through the periodic terms AΦi and the corrections bk . The nonconvexity is forced by the run rather than chosen by the realization: along the divergent trajectory, ∇f˜(X̃6 ) − ∇f˜(X̃3 ), X̃6 − X̃3 = − 9A 50 < 0, violating the gradient monotonicity that every convex function obeys, so no convex function generates these iterates and gradients. The theorem is stated under Assumptions 1–2 because that is where it is needed: EF21-MuonUSign and EF21MuonSign converge under exactly these hypotheses (Theorem 5), so the divergence and the guarantees concern one problem class. Whether some convex instance, necessarily through a different trajectory, also defeats EF21-SignMuon we leave open. Remark 3 (Verification) The construction is checked in two independent ways: symbolically, in exact rational arithmetic, and numerically, by running the float64 reference implementation of Algorithm 3 on the assembled f˜. The right panel of Figure 1 confirms that at µ = 0 EF21-SignMuon is the only one of the eight methods that diverges, the others (SignMuon, MuonUSign, MuonSign, EF21-MuonUSign, EF21-MuonSign, SignSGD, Muon) staying bounded; Figure 5 confirms that EF21-SignMuon 49 diverges at the exact rate 480 for every µ ∈ {0, 12 , 0.9, 0.95, 0.99} under both standard and Nesterov momentum, as the reduction predicts.
A.10
Convergence of EF21-MuonUSign and EF21-MuonSign
We do not analyse the two error-feedback methods from scratch. EF21-MuonUSign and EF21-MuonSign are exact instances of EF21-Muon (Gruntkowska et al. 2025, Algorithm 3), already analysed in the layer-wise, stochastic, federated setting. Three conditions must be verified before its guarantees transfer: our step is their LMO step, our loop is their loop (Proposition 2), and our messages come from contractive compressors (Lemma 5). Only the last is non-trivial. Table 4 is the change of variables. Notation and constants. For the layer tuple X = [X1 , . . . , Xp ], Xi ∈ Rmi ×ni , of the Problem Statement write di := mi ni , r√i := min(mi , ni ), dmax := maxi di ; a second subscript selects a layer (Xt,i , gt,i ). We use ∥Y∥2→2 ≤ ∥Y∥F ≤ ∥Y∥∗ ≤ P rank Y ∥Y∥F . Smoothness constants: Li for f and Li,j for fj in Assumption 2, with L̃2i := N1 j L2i,j and L := maxi Li ; in the (L0 , L1 ) form the pairs are again per layer for f and per layer and client for fj , with L1i,max := maxj L1i,j . Assumption 3 (Stochastic gradient) Each client’s stochastic gradient is unbiased, Eξ [∇fj (X; ξ)] = ∇fj (X), with bounded variance Eξ ∥∇fj (X; ξ) − ∇fj (X)∥2∗ ≤ σ 2 . Assumptions 1–3 are Assumptions 1–2 and 6–10 of Gruntkowska et al. (2025) with the layer norms taken spectral; our variance bound is stated in the nuclear norm and implies theirs via ∥ · ∥F ≤ ∥ · ∥∗ . The clause fj ≥ fj∗ of Assumption 1 is needed only for Corollary 2.
Main result Theorem 5 (Convergence of the EF21 methods) Run the federated Algorithm 9 with the EF21 uplink and EMA momentum µ ∈ [0, 1). Then: (i) (smooth; EF21-MuonUSign and EF21-MuonSign) under Assumptions 1–3, with the “sharp” learning rate ηt,i = γi ∥gt,i ∥∗ P and tuned (γi , µ), both methods reach T1 t<T E∥∇f (Xt )∥2∗ = O(T −1/2 ) (Corollary 1); (ii) (generalized smooth; P EF21-MuonUSign only) under (L0 , L1 )-smoothness, EF21-MuonUSign with a plain constant learning rate reaches mint≤T i E∥∇i f (Xt )∥∗ = O(T −1/4 ) (Corollary 2). Both statements are written for a per-layer constant common to all layers (γi ≡ γ, ηi ≡ η); for unequal constants the left-hand sides carry the step-size weights of Corollaries 1–2. Part (i) implies the rate announced in the main text, since the minimum over t ≤ T is at most the average. The centralized Algorithms 6–7 are the federated method at N = 1, so both parts cover the centralized runs as well. The reduction The step is their LMO step. For G = UΣV⊤ the framework’s oracle over the spectral ball of radius τ is lmo(G) = ⊤ X − τ UV⊤ , which is our server step with τ = ηt,i , since Dt,i = −A(gt,i ) = Ut,i Vt,i : Xt,i = Xt−1,i − ηt,i Dt,i = lmoB(Xt−1,i ,ηt,i ) (gt,i ).
(44)
Their “sharp” step X−γ G♯ uses G♯ = ∥G∥∗ UV⊤ , so a constant γi amounts to the schedule ηt,i = γi ∥gt,i ∥∗ and a constant ηt,i to the plain Muon rate: the two differ as learning-rate choices, not as algorithms, and either run is an instance of the framework. The guarantees, however, are attached to specific choices. Part (i) of Theorem 5 assumes the nuclear-norm schedule, which our implementation does not use; what the corollaries then cover of the constant-rate √ runs we actually perform is recorded in the Scope paragraph below. The spectral norm-equivalence constants are ρi = 1, ρ̄i = ri , defined by ρi ∥Y∥2→2 ≤ ∥Y∥F ≤ ρ̄i ∥Y∥2→2 . At rank-deficient G the LMO is non-unique, but any selection serves: writing ∆ := lmoB(X,τ ) (G) − X for the displacement it produces, the analysis uses only ⟨G, ∆⟩ = −τ ∥G∥∗ and ∥∆∥2→2 ≤ τ , with G = 0 read as the zero step (0♯ = 0). The momentum is their momentum. Algorithm 9 uses Mt = µMt−1 + (1 − µ)Gt , which is (5) and is the framework’s momentum with β = 1 − µ. Rescaling the momentum stream by a constant, as the heavy-ball convention does by the factor 1/(1 − µ), alters nothing: the EF21 recursion is positively homogeneous and the Muon LMO scale-invariant, so the factor leaves the iterates unchanged under a constant ηt,i and is absorbed into γi under the “sharp” schedule. (The Nesterov branch is a different filter; see the end of this appendix.) (j)
(j)
Proposition 2 (Exact instance) Fix µ, a learning-rate schedule, and the LMO selection above. Started from M0 = g0 = g0 = 0, W0 = X0 , Algorithm 9 with the EF21 uplink and either downlink mode (C ↓ ∈ {exact, EF21-P}) produces the same trajectory as Algorithm 3 of Gruntkowska et al. (2025) with spectral norms, scaled-sign worker compressors, identity/scaled-sign server compressor, β = 1 − µ, and radii tki = ηk,i , up to a one-step index shift X t+1 = Xt . Proof The loops differ only in where the round is cut: they order it step → downlink → gradient → uplink, we order it downlink → gradient → uplink → step. Their iteration k = 0 is vacuous under our initialization: g0 = 0 gives X 1 = X 0 = X0 and a zero downlink residual, so W 1 = X0 . Thereafter their iteration k = t performs our round t verbatim, with the same momentum, the same compressed residual and the same LMO step (44), giving X t+1 = Xt , W t+1 = Wt by induction. Running their method for K = T + 1 iterations therefore yields {X0 , X0 , X1 , . . . , XT −1 }, and any average or minimum over these equals ours up to one duplicated nonnegative term. ■ Zero initialization also makes their initial-error constant Ψ0 explicit: the ∥M0 − g0 ∥ term vanishes and the gradient-deviation terms become ∥∇i f (X0 )∥. The β −1 surviving in Ψ0 enters only through the Ψ0 /T term, which T −1/2 dominates. The scaled sign is a contractive compressor The framework requires every transmitted message to originate in a contractive compressor: a map with E∥C(Y) − Y∥2 ≤ (1 − α)∥Y∥2 for some α ∈ (0, 1] (Gruntkowska et al. 2025, Def. 1). This is precisely the property that fails for a bare sign and holds once it is scaled. Lemma 5 (Contractivity of the scaled sign) For every Y ∈ Rm×n (d = mn), the scaled sign C(Y) = mean(|Y|) sign(Y), with exact zeros resolved to ±1 as in Section 4, satisfies (45) ∥C(Y) − Y∥2F = ∥Y∥2F − d1 ∥Y∥21 ≤ 1 − d1 ∥Y∥2F , so C is Euclidean-contractive with α = 1/d. The identity holds for every draw of the random signs, not merely in expectation, and gives the exact contraction α(Y) = ∥Y∥21 /(d∥Y∥2F ), which is Θ(1) for dense Y (e.g. → 2/π for i.i.d. Gaussian entries) and equals 1/d exactly at any 1-sparse Y.
This paper EF21-Muon clients / rounds iterate momentum learning rate norm equivalence uplink compr. downlink compr. compression α
N, T Xt µ ηt,i√ 1, ri scaled sign exact / sign 1/dmax
n, K = T + 1 X t+1 1−β radius tti ρi , ρ̄i B2 (αD ) I / B2 (αP )† αD
Table 4: Change of variables from our notation to that of Gruntkowska et al. (2025). Layer norms ∥ · ∥(i) , ∥ · ∥(i)⋆ are read as ∥ · ∥2→2 , ∥ · ∥∗ and smoothness constants L0i , L̃0i as Li , L̃i ; the index shift is Proposition 2. † Their Theorem 19 as printed asks for a server compressor in B(αP ), contractive in the layer norm; the Euclidean class B2 (αP ), to which the scaled sign does belong, is admitted by their Remark 23, which introduces the factor ρ̄2i appearing in Corollary 1 and Remark 5. Proof Write c := ∥Y∥1 /d and skl = ±1 for the transmitted signs. A nonzero entry contributes (|Ykl | − c)2 and a zero entry contributes (c skl )2 = c2 whichever sign was drawn, so ∥C(Y) − Y∥2F = ∥Y∥2F − 2c∥Y∥1 + c2 ∥Y∥0 + c2 (d − ∥Y∥0 ) = ∥Y∥2F − 2c∥Y∥1 + dc2 , which is (45) on substituting p c. The bound then follows from ∥Y∥1 ≥ ∥Y∥F , with equality exactly at the 1-sparse Y; the Gaussian limit uses E|Ykl | = 2/π σ. ■ The randomized sign(0) is what makes (45) hold with equality for every Y: under the ternary convention the ∥Y∥0 -terms in the proof do not cancel, the error depends on the sparsity of Y, and α = 1/d becomes an infimum rather than an attained value. The scaling is essential p to Lemma 5: a bare sign contracts for no α at all, since as ∥Y∥F → 0 on a fixed support, ∥ sign(Y) − Y∥F → ∥Y∥0 . That is the dividing line between our divergent and convergent methods: the majority-vote methods transmit unscaled signs of full quantities, the EF21 variants the scaled sign of a residual, at the cost of one extra scalar per layer per round. Per layer the uplink scaled sign lies in B2 (1/di ) ⊆ B2 (α) with α := 1/dmax ; the downlink is exact for EF21-MuonUSign (αP = 1) and the same scaled sign for EF21-MuonSign. Transferred guarantees All requirements hold, so the framework’s theorems apply through Table 4. We state the rates and stepsize rules; the explicit non-asymptotic bounds are those of Theorems 19 (smooth) and 24 ((L0 , L1 )-smooth) of Gruntkowska et al. (2025), evaluated at the constants of Table 4. Corollary 1 (Smooth case; EF21-MuonUSign and EF21-MuonSign) Let Assumptions 1–3 hold. Run EF21-MuonUSign or EF21-MuonSign (Algorithm 9 with the EF21 uplink and the exact or the scaled-sign downlink, respectively) with EMA momentum and ηt,i = γi ∥gt,i ∥∗ , for any γi below the per-layer threshold of Gruntkowska et al. (2025, Thm. 19) under Table 4. Then, applying the momentum tuning of Gruntkowska et al. (2025, Cor. 2) per layer (their Corollary 1 supplies the layer-wise initialization, their Corollary 2 the tuning at p = 1), P Pp 1 −1/2 2 ), t<T i=1 wi E∥∇i f (Xt )∥∗ = O(T T P P with wi := γi /( p1 l γl ); for a common γi all wi = 1 and the left side is T1 t<T E∥∇f (Xt )∥2∗ . Proof By Proposition 2 the run is an instance of Algorithm 3 with K = T + 1, and by Lemma 5 its compressors satisfy αD = α and αP ∈ {1, α} (EF21-MuonSign’s Euclidean downlink is admissible by their Remark 23, which multiplies the √ αP -terms of the threshold constant ζi by ρ̄2i = ri ). Substituting ρi = 1, ρ̄i = ri into Gruntkowska et al. (2025, Thm. 19) gives the threshold and the rate; the duplicated X0 -term changes the constant by at most the factor T T+1 . ■ √ The threshold in question is γi ≤ (2Li + 2 ζi )−1 , with ζi the constant of Gruntkowska et al. (2025, Thm. 19). Under Table 4, ζi grows polynomially in the layer dimension, through ρ̄2i = ri and the uplink α = 1/d √max ; for EF21-MuonSign its αP -terms carry the additional factor ri of Remark 23, shrinking the admissible γi by a further ri . That additional factor is structural: the scaled sign is spectrally contractive for no parameter at all (Remark 5). Corollary 2 ((L0 , L1 ) case; EF21-MuonUSign) Let Assumption 2 hold in its (L0 , L1 ) form. Run EF21-MuonUSign (exact downlink) with S := T + 2, momentum µ = 1 − S −1/2 , and the constant per-layer rate ηt,i ≡ ηi /S 3/4 for any ηi ≤ 1 with √ ηi2 ri (L1i,max )2 = O(1).1 Then Pp ηi −1/4 min ), vi := 1 P . i=1 vi E∥∇i f (Xt )∥∗ = O(T η 0≤t≤T
1
p
l
l
Gruntkowska et al. (2025, Thm. 24) imposes four upper bounds on ηi2 ; at β = (K + 1)−1/2 the two quoted here are the binding ones,
the first bound relaxing as T grows. Their second bound, √ as printed, carries a factor K√+ 1 in the denominator that the proof does not use: the display it is chosen to ensure requires only ηi2 ≤ (1 − 1 − αD ) ρi (K + 1)1/2 /(24 1 − αD ρ̄i (L1i,max )2 ), which also relaxes as T grows, and this is the requirement we work from.
Proof Their Theorem 24 requires the identity server compressor, i.e. the exact downlink of EF21-MuonUSign (so EF21MuonSign is excluded). Applying it with K = T + 1, β = S −1/2 and Table 4 gives the schedule and the rate. ■ Under plain smoothness (L1 = 0) every constraint above collapses to ηi ≤ 1. The constant-learning-rate EF21-MuonUSign we actually run is therefore covered as it stands, and at no loss of order: O(T −1/4 ) for the norm corresponds to O(T −1/2 ) for its square, the quantity of part (i). What the “sharp” schedule changes is the bounded quantity, an average of the squared norm in place of a minimum of the norm, not the effective speed. Scope The reduction covers the two error-feedback methods and no others, which matches our negative results. The majorityP (j) vote methods send unscaled signs and fall outside the framework: their server aggregates by a vote, sign( j st ), where Algorithm 3 averages, and it is the average that Proposition 2 matches. EF21-SignMuon compresses the LMO output rather than the gradient, so it tracks the non-Lipschitz polar factor and the momentum-tracking step breaks (Theorem 4). EF21-MuonSign gets the smooth guarantee but not the (L0 , L1 ) one, whose theory assumes an uncompressed downlink. One further gap is ours and not the framework’s. Corollary 1 reaches EF21-MuonSign only under the “sharp” schedule ηt,i = γi ∥gt,i ∥∗ , while Corollary 2, the constant-rate statement, excludes it for want of an identity server compressor. Our experiments run a cosine-annealed constant η0 , so the EF21-MuonSign runs are covered by neither, whereas constant-rate EF21-MuonUSign is covered by Corollary 2 at L1 = 0. The trajectories remain exact instances of Algorithm 3 either way; what the constant rate costs is the step-size hypothesis of the rate, not the reduction. The remaining gap is the Nesterov branch, which our language-model runs use (Appendix A.16): with β := 1 − µ it steers by M̃t = (1 − β)Mt + βGt rather than by the buffer Mt , and the framework’s analysis is written for a direction that itself satisfies the recursion Mt = (1 − β)Mt−1 + βGt , which M̃t does not. The discrepancy is small and explicit: writing nt := Gt,i − ∇i f (Xt ), we have ∇i f − M̃t = (1 − β)(∇i f − Mt ) − β nt , and since E⟨∇i f − Mt , nt ⟩ = −β E∥nt ∥22 , E∥∇i f − M̃t ∥22 ≤ (1 − β)2 E∥∇i f − Mt ∥22 + 3β 2 σi2 . The first term is exactly the deviation Gruntkowska et al. (2025, Thm. 19) already tracks, contracted rather than enlarged; the second is dominated by the βσi2 term already in its bound. Nesterov should therefore degrade the constants rather than the rate. We state this as an expectation, not as a corollary, since the tracking recursion for ∥M̃t+1 − M̃t ∥ would have to be redone as well. Remark 4 (Worst-case and realized contraction) The uplink parameter α = 1/dmax enters the threshold of Corollary 1 through the 1/α2 -terms of ζi , so the admissible γi shrinks linearly in dmax , the dimension of the largest layer; the same dimension factor arises for Top-1 compressors in Euclidean EF21 (Richtárik, Sokolov, and Fatkhullin 2021). On the uplink this is a worst case only: by Lemma 5, α = 1/d requires a residual concentrated on a single coordinate, whereas the momentum residual is dense, with α(∆) = Θ(1), and the framework is stated to extend to iteration-dependent α (Gruntkowska et al. 2025, Rem. 12), under which the dense value would enter in place of the worst case. The downlink residual of EF21-MuonSign does not stay dense. Unlike the uplink residual, which every round’s gradient refreshes, it is produced by the compressor’s own recursion ∆↓t+1 = ∆↓t − ηt+1 Dt+1 − mean |∆↓t | sign(∆↓t ), which corrects every coordinate by the same scalar mean |∆↓t |. A coordinate whose per-step drive ηt+1 (Dt+1 )kl exceeds that scalar receives a correction smaller than its drive at every step, while the remaining coordinates keep the scalar small, so the residual concentrates on few coordinates; by the exact expression α(Y) = ∥Y∥21 /(d∥Y∥2F ) of Lemma 5, concentration is precisely what lowers α. Section 5.3 measures the effect: on the layers built from a zero initialization, α(∆↓ ) falls to 1.2 × 10−4 , about four orders of magnitude below the uplink value on the same layers, yet still far above the floor 1/d = 4.2 × 10−7 . The dimension dependence of Corollary 1 is therefore not attained on the downlink either, but the downlink lacks the Θ(1) contraction that suppresses it on the uplink. Remark 5 (The scaled sign is not layer-norm contractive) Corollary 1 reaches EF21-MuonSign only through Gruntkowska et al. (2025, Rem. 23) and its factor ρ̄2i , for two reasons. First, the alternative, a server compressor contractive in the layer norm, is unavailable: the scaled sign is contractive there for no αP > 0; for Yδ = (1 − δ)In + δJn (Jn all ones, 0 < δ < 1, n ≥ 2), every entry is positive, so sign(Yδ ) = Jn , mean |Yδ | = (1 + (n − 1)δ)/n, and C(Yδ ) − Yδ = (1 − δ) n1 Jn − In , a matrix with eigenvalues 0 and −(1 − δ); hence ∥C(Yδ ) − Yδ ∥2→2 = 1 − δ while ∥Yδ ∥2→2 = 1 + (n − 1)δ, and the ratio tends to 1 as δ ↓ 0. Second, the sufficient condition of Gruntkowska et al. (2025, App. D), which certifies a compressor in B2 (α) as layer-norm contractive when α > 1 − 1/ri , is out of reach: for a 768 × 3072 layer it demands α > 0.9987, where the scaled sign attains 2/π on dense inputs (Lemma 5). The factor ρ̄2i = ri in ζi can therefore be removed only by replacing the 2 compressor, for instance by random dropout (αP = p) or a Top-K SVD compressor (αP = 1 − σK+1 /σ12 ), both layer-norm contractive (Gruntkowska et al. 2025, App. D) and neither one-bit.
√ Remark 6 (From Muon to Gluon) Only (ρi , ρ̄i ) = (1, ri ) is spectral-norm-specific: Lemma 5 is Euclidean and the framework’s theorems hold for arbitrary layer norms. A new geometry has to supply only its LMO and its norm-equivalence pair; both √ corollaries then hold with those constants in place of (1, ri ), giving EF21-GluonUSign and EF21-GluonSign for the Gluon setting (Riabinin et al. 2025). Admissible geometries abound: ℓ1 → ℓ∞ for embeddings (Pethick et al. 2025a), the Schatten-p norms (Cesista 2025), the Ky Fan duals of the Fanion family (Kravatskiy et al. 2025), and, by the closure property of the last work, the norms whose LMO is a conic combination of these LMOs; their unit ball is the corresponding Minkowski sum, whence P (j) ρ̄i ≤ j αj ρ̄i . Convergence is thus a property of error feedback together with scaled-sign compression, not of the spectral geometry. We assume the exact spectral LMO, as do all analyses of Muon-type methods (Li and Hong 2025; Kovalev 2025; Riabinin et al. 2025; Gruntkowska et al. 2025); in practice the polar factor is approximated by polynomial iterations (Amsel et al. 2025; Grishina, Smirnov, and Rakhuba 2025), in our case the five Newton–Schulz steps of Algorithm 1, with vector parameters and the last layer trained by AdamW as usual (Jordan et al. 2024b). That substitution is not covered by Theorem 5 either; Shulgin et al. (2026) analyse the inexact Muon update directly and find the method tolerant of oracle error.
A.11
Reproducibility Details
Choice of benchmarks. Each benchmark answers a question the others cannot. On the convex quadratic of Appendix A.12 the smoothness constant and the minimizer are known in closed form, so the alignment the counterexamples attack can be measured there rather than inferred. CIFAR-10 with a ResNet-18 (Krizhevsky 2009) carries no such special property: we use it because it is the benchmark on which the sign-compression line of work is quoted (Bernstein et al. 2018, 2019; Karimireddy et al. 2019) and on which SignMuon’s own concurrent proposal is evaluated (Mishra, Trivedi, and Kumar 2026); it is small enough to run every method at several step sizes and several seeds, which is what the claims about seed spread require. The federated split of the same data at N = 11 tests the methods in the setting they are designed for, a bandwidth-limited link between clients and a server. NanoGPT supplies what CIFAR cannot: a transformer language model at practical scale, with matrices wide enough for the layer-rank term of Corollary 1 to be visible, which is where the two models of EF21-MuonSign separate. Computing infrastructure. The experiments were not all run on the same machine. The synthetic study ran on one NVIDIA RTX A4000 (128-core AMD EPYC 7543 host, 472 GB RAM; Linux 6.12, Python 3.12, PyTorch 2.7.0, CUDA 12.8, driver 575.51.03); the language-modelling runs used a rented 8×H100 SXM node, specified in full in Appendix A.16. The centralized and federated CIFAR-10 runs were executed on single-GPU workstations; each run records its machine, commit and wall time in its metrics.json. All 126 centralized runs and all 175 federated runs behind the tables and figures below were executed on the same machine and at one commit: an NVIDIA RTX A4500 (19.6 GB) in a 32-core AMD Ryzen 9 5950X host with 62.7 GB of memory, under Linux 5.15, Python 3.12.11, PyTorch 2.5.1+cu124, CUDA 12.4, driver 560.35.05. Randomness and seeds. The network experiments are seeded through a single routine that seeds Python’s random module, NumPy and PyTorch on all CUDA devices; the federated runs additionally pin cuDNN to deterministic kernels, while the centralized sweep leaves cuDNN autotuning enabled, since it reports the spread across seeds rather than a bitwise-reproducible trajectory. The synthetic study forks and re-seeds its own generator per configuration. The federated experiment of Table 2 uses five seeds (0–4) per method and the centralized experiment of Table 1 three (0–2), each reported as mean ± one sample standard deviation across seeds; the weight-decay ablations use seed 0. The nanoGPT runs of Table 3 are single runs at the speedrun’s own unpinned initialization, and the table quotes the five-seed spread published upstream; our released script accepts an explicit seed but pins the generator only, since deterministic kernels would forfeit the wall-clock time the same table reports. The synthetic study of Appendix A.12 averages over three draws of the problem (seeds 1337–1339) at a fixed X0 (seed 42), its claims concerning random instances. Differences smaller than the seed spread are not claimed as results, and we report spreads rather than significance tests because at these seed counts no test could reject: a paired Wilcoxon signed-rank test over n seeds has smallest attainable two-sided exact p-value 21−n , which is 0.0625 at five seeds and 0.25 at three, above the 5% level in both cases. The comparisons we claim are separated by several standard deviations. Learning-rate selection is performed once, at seed 0, on a validation split disjoint from the test set, and the selected rate is reused unchanged for every seed. Step-size schedules. Each experiment inherits the schedule conventional to its domain, and none of them is the constant rate our rates are proved for. The ResNet runs anneal cosinally to zero, the standard for this architecture and the premise of every accuracy we can be compared against; the nanoGPT runs keep record #40’s stable-then-decay schedule, flat for the first 55% of steps and decaying linearly to a tenth of the base rate η0 of (7) thereafter (Appendix A.16), because altering it would forfeit the reproduction that validates our port. The discrepancy is deliberate: matching the analysed step size would sacrifice comparability on both benchmarks and close only one of several gaps between the theory and the runs, the others being Newton–Schulz in place of an exact oracle, momentum, and normalization layers. One measurement is exempt: the growth-exponent diagnostic of Appendix A.17, which is run at a constant rate because under a decaying one the accumulated update saturates and the fit reports the schedule instead of the alignment. Learning-rate selection. The only tuned hyperparameter is η0 . Every method with a norm-fixed step is tuned and reported under the unit-gain rule (7), so that η0 is the per-step RMS gain for each of them; SGD and Adam have no norm-fixed step and run
at one global rate. The rule is a heuristic, and Appendix A.17 bounds and measures what depends on it: the three sign methods keep their order when re-tuned from scratch under one global rate and under µP (Table 11). Momentum is fixed at 0.9 and weight decay at 0 in the primary tables, the setting the sweep of Mishra, Trivedi, and Kumar (2026) itself selects; the regularized case is an ablation (Appendix A.13 centralized, and below for the federated study). The auxiliary group, biases, normalization parameters and the classifier head, is trained by AdamW at 10−3 for every method, a convention rather than a verified common optimum: a sweep at matched budget places SignMuon’s optimum at 10−3 and Muon’s at 2 × 10−3 , a difference of 0.16 points that lies within the seed spread, so the auxiliary rate is method-dependent, to a degree the sweep does not quantify. In the centralized study, selection uses a fixed 45k/5k train/validation partition and validation accuracy averaged over the last five epochs; the test set is never consulted during tuning. Each method starts from the same five-point 1–2–5 lattice (three points per order of magnitude); an optimum at a grid endpoint triggers a widening and a re-run, up to four times, extending Muon and EF21-MuonUSign to seven points and SignSGD to nine. Selection runs use the same 75-epoch cosine schedule as the reported ones, so the tuning and reporting horizons coincide. The selected η0 is then retrained on the full 50k training set at three seeds, and we report the mean and standard deviation of the test accuracy over the last five epochs. Tuning the federated study. So that no placement is handicapped by its step size, every method receives the same tuning budget: a five-point 1–2–5 lattice in η0 , ranked on a 5k validation split held out of the 50k before the client partition, at the full 2000-round horizon Table 2 reports, with the grid widened and the method re-tuned whenever an optimum occurred at an endpoint. SignMuon is the one method that required the widening, settling at η0 = 0.1 on seven points; every selected rate is interior to its own grid. The reported runs then use the full 50k at the selected rate, so no test image is ever scored during selection. One selection margin requires comment. Eight of the nine methods carrying a per-layer multiplier (the eight of Appendix A.17 and the server-side-LMO control) separate their selected rate from the runner-up by 0.15 to 1.07 validation points; SignMuon separates 0.1 from 0.05 by 0.02 at the single tuning seed, which is no separation at all, so its row in Table 2 is to be read as either of two adjacent lattice points. The ambiguity does not extend further, the next points out lying 0.5 and 1.3 points behind. The selected rates span a factor of ten, from η0 = 0.01 for SignSGD and EF21-MuonUSign to 0.1 for Muon and SignMuon, with both families covering that range. This spread is between methods and carries no verdict on the per-layer rule, whose claim concerns layer shape; the measurement that does bear on the rule, re-tuning under competing conventions, is Table 11. Weight decay is 0 in the reported table. Switching on a decoupled 5 × 10−4 at seed 0 moves Muon by −0.32 points, SignMuon by +0.27 and the server-side-LMO control by +0.05: Muon leads in either setting, and the other two exchange places by margins below the 0.24 standard deviation SignMuon carries over five seeds, so the ablation separates nothing that the primary table does not. Accuracy and the threshold column. Alongside final accuracy we report the number of epochs (rounds, in the federated tables) to reach a fixed test accuracy. The two measure distinct quantities: with the methods spanning about a point and a half at 75 epochs (Table 8), final accuracy is close to the noise floor, whereas a threshold crossing on a monotonically rising curve separates the methods by factors rather than by tenths of a point, and is the analogue of the “steps to 3.35” column of Table 3. Conventions with numerical consequences. Three implementation conventions can displace reported numbers and are recorded here. (i) The Muon LMO is computed in bfloat16 (five Newton–Schulz steps) unless stated otherwise; for the methods that sign the LMO output, entries of polar(·) near zero may flip at this precision, so that their trajectories carry a precision-dependent component (-lmo-dtype float32 is available). (ii) In the federated runs, BatchNorm running statistics are never updated: local models are discarded each round and BN runs in inference mode during gradient accumulation, so the statistics stay at their initialization for the entire run, in training and evaluation alike. The result is a fixed normalization with learnable affine parameters, self-consistent between train and test, applied identically to every method. It is also one reason a channel may remain inactive across an entire local batch and so contribute an exactly zero row to the momentum. (iii) For EF21-MuonSign, training metrics are logged at the broadcast model W (where gradients must be evaluated) while validation and test metrics are evaluated at the server model X of (13), the iterate the guarantee bounds, except where a table states otherwise.
A.12
The smooth convex problem
On a deterministic L-smooth convex quadratic we measure the scalar the guarantees rest on: the alignment ρt = ⟨∇F (Xt ), Dt ⟩/(∥∇F (Xt )∥F ∥Dt ∥F ) between the gradient and the step. Theorems 1–3 construct instances driving it negative; on random instances the three methods they cover keep ρt ≥ 0.142 throughout a tuned trajectory, so the construction is not one that random data reproduces. Only EF21-MuonSign becomes negative, on 0.95% of steps and to −0.026; it is also the one method here possessing a convergence guarantee (Appendix A.10), obtained without per-step descent. The same experiment separates the two effects that a fixed-target iteration count confounds. Sign compression of an lmo step secures a lower accuracy floor, not a faster rate: SignMuon’s floor lies a factor 1.74–1.80 below SignSGD’s at every step size, and the two share ∥S∥F exactly, so the separation resides in the floor rather than in the step length.
Algorithm SignMuon MuonUSign MuonSign EF21-SignMuon EF21-MuonUSign EF21-MuonSign Muon SignSGD SGD Adam
iters
best F
min ∥∇F ∥F
364 556 595 401 521 695 267 486 66 85
−4
−2
6.9 · 10 7.1 · 10−4 4.8 · 10−4 5.4 · 10−4 5.3 · 10−4 3.8 · 10−4 4.7 · 10−4 4.3 · 10−4 1.9 · 10−8 9.2 · 10−6
2.4 · 10 2.3 · 10−2 1.9 · 10−2 2.1 · 10−2 1.8 · 10−2 1.7 · 10−2 2.0 · 10−2 2.2 · 10−2 1.6 · 10−6 6.5 · 10−4
tuned (η, µ) (1.0 · 10−3 , 0) (1.0 · 10−2 , 0.5) (6.8 · 10−4 , 0.5) (6.8 · 10−3 , 0) (6.8 · 10−3 , 0) (4.6 · 10−3 , 0) (1.0 · 10−2 , 0.5) (6.8 · 10−4 , 0.5) (2.15, 0.5) (6.8 · 10−2 , —)
Table 5: Fixed-target criterion under the current protocol: fewest iterations to F ≤ 10−3 within Tmax = 5000 at m = n = 100, over three problem draws, (η, µ, schedule) tuned on logarithmic grids spanning five orders of magnitude. A constant schedule is selected for every method. Best F and min ∥∇F ∥F are minima over all 5000 iterations rather than values at the crossing, so they report the floor the method settles into.
Construction. To isolate the effect of matrix structure from stochastic noise and from the complexity of DNN architectures, we use a deterministic L-smooth convex quadratic: F (X) =
1 1/2 1 ∥A XB1/2 ∥2F = ⟨X, AXB⟩ → min , 2 2 X∈Rm×n
(46)
n with A ∈ Sm ++ , B ∈ S++ symmetric and X0 drawn entrywise from N (0, 0.01). Eigenvalues are sampled uniformly from (0, 1) in a Haar-random eigenbasis, so the matrices are almost surely positive definite and the minimizer is X⋆ = 0 with F ⋆ = 0. Two facts about this instance are exact rather than estimated, and both are used below. The Hessian of F is the Kronecker product B ⊗ A, so its eigenvalues are the products λi (A)λj (B): the Frobenius smoothness constant is L = maxij λi (A)λj (B) ≤ 1 and the strong-convexity constant is σ = minij λi (A)λj (B) > 0. The uniform draw leaves the resulting condition number L/σ uncontrolled (it is near 3.7 × 104 at the m = n = 100 every measurement in this subsection uses), so where conditioning is the variable we instead use log-spaced spectra with L = 1 and L/σ set exactly. And since ∇F (X) = AXB in closed form, the gradient can be evaluated at any point without an autograd graph, which permits the bidirectional method to be scored on its exact model X while its gradient is taken at the broadcast model W, as its algorithm requires.
The fixed-target criterion. The natural criterion, fewest iterations to F (X) ≤ 10−3 within Tmax = 5000 with learning rate and momentum √ tuned per method, does √ not measure a convergence rate. Eight of the ten methods take a norm-fixed step, ∥ sign(·)∥F = mn and ∥polar(·)∥F = r, so at a constant η the iterate settles into a ball of radius η∥S∥F and F plateaus; Adam, bounded entrywise by ≈η, plateaus as well, and SGD, whose step vanishes with the gradient, is the only method that does not. Write F∞ and g∞ for the settled values of F (Xt ) and ∥∇F (Xt )∥F . Measured directly, g∞ ∝ η for every method possessing a floor, F∞ ∝ η 2 for every such method but SignSGD, whose exponent is 1.33, and the iteration count is const/η. The tuner accordingly returns the largest η whose plateau falls under the target, and the resulting ranking is one of accuracy floors. Over the seven step sizes at which both methods were run, SignMuon’s g∞ lies a factor 1.74 to 1.80 below SignSGD’s, flat in η as two floors of equal exponent must be, while its F∞ lies 6.7 to 71 times below, the two F -exponents differing. Tuned per budget, SignMuon holds the smaller mint ∥∇F ∥F at every horizon but T = 250, where SignSGD prevails by 2%, a margin below what three draws resolve. We therefore report floor and rate separately, reading the descent lemma 2
F (Xt+1 ) ≤ F (Xt ) − η⟨∇F (Xt ), Dt ⟩ + η 2L ∥Dt ∥2F
(47)
as the statement that separates them: the second term is the floor, the first is the rate. Table 5 nonetheless reports the criterion. Read as a ranking of floors, it orders the six placements identically within both families: sign after the lmo is the least expensive, sign on both channels the most. Error feedback adds 10% on SignMuon and 17% on MuonSign, and removes 6% on MuonUSign, the one placement whose lmo already receives a compressed argument. Muon surpasses all six placements, and SGD (66) and Adam (85) surpass every normalized step by factors of three to ten, a quadratic with an exactly known Hessian being precisely the case for which a scaled gradient step is designed. Figure 6 plots the trajectories behind those counts, and shows the plateau that makes the criterion a ranking of floors. Alignment. Equation (47) makes progress contingent on a single scalar, the normalized alignment between the gradient and the step actually taken, ⟨∇F (Xt ), Dt ⟩ ρt := ∈ [−1, 1]. (48) ∥∇F (Xt )∥F ∥Dt ∥F
10
2 × 10
1
−3
10
−1
F(Xt )
3 × 10
10
300
−3
10
−5
10
−7
0
1000
0
10
−1
10
−2
10
−3
10
−4
10
−5
10
−6
3 × 10
−2
2 × 10
−2
−4
2000
450
600
3000
750
4000
5000
‖∇F(Xt )‖F
10
10
−3
0
1000
iteration SignMuon EF21-SignMuon
200
400
600
800
2000
3000
4000
5000
iteration MuonUSign MuonSign
EF21-MuonUSign EF21-MuonSign
Muon SignSGD
SGD Adam
Figure 6: Trajectories at the optima of Table 5, geometric mean over three problem draws. Every normalized method plateaus within a few hundred iterations and stays there, which renders the crossing time a ranking of floors; SGD, whose step vanishes with the gradient, is the only curve still descending at Tmax , and Adam oscillates about its floor rather than settling onto it. The insets magnify the arrival window, over the full axis a fold of curves in the first sixth of the range, and are scaled to the eight norm-fixed methods: the dashed line is the target F ≤ 10−3 , and the order in which the curves cut it is the iteration count of Table 5, Muon first and EF21-MuonSign last. Those counts are means of the per-draw crossing times rather than crossings of the plotted mean, and for the slowest method the two differ by enough to see. Algorithm
mint ρt
median ρt
mean ρt
% of steps with ρt < 0
closed form
SignMuon MuonUSign MuonSign EF21-SignMuon EF21-MuonUSign EF21-MuonSign Muon SignSGD SGD
0.208 0.161 0.142 0.333 0.346 −0.026 0.454 0.174 —
0.381 0.357 0.360 0.659 0.558 0.489 0.666 0.503 —
0.399 0.378 0.364 0.573 0.553 0.419 0.633 0.499 —
0.00% 0.00% 0.00% 0.00% 0.00% 0.95% 0.00% 0.00% —
— — — — — — 0.695 0.794 1
tuned (η, µ) (2.2 · 10−4 , 0) (3.2 · 10−3 , 0) (2.2 · 10−4 , 0) (1.5 · 10−3 , 0) (1.5 · 10−3 , 0) (1.5 · 10−3 , 0) (1.5 · 10−3 , 0) (2.2 · 10−4 , 0.5) (3.2, 0.95)
Table 6: Alignment ρt of Equation (48) along the tuned trajectory, over three problem draws at m = n = 100. The closed form is evaluated at X0 without momentum and is comparable only to rows whose tuned µ is 0; the six sign-around-the-lmo methods admit none. SGD’s closed form is 1 but its step is not instrumented, so its distribution column is empty; Adam is omitted, its step lying outside the descent lemma. Every method of Theorems 1–3 stays bounded away from zero; the single negative excursion is EF21-MuonSign’s, which Appendix A.10 proves convergent through the EF21 estimator rather than per-step descent. Theorems 1–3 are constructions that drive ρt negative. Table 6 reports its distribution along the tuned trajectory on random instances, which is the empirical counterpart of those theorems and the one measurement here that is√about the methods rather than about the tuning √ protocol. Three closed forms anchor it: ρ = 1 for SGD, ρ = ∥G∥1 /(∥G∥F mn) for SignSGD, and ρ = ∥G∥∗ /(∥G∥F r) for Muon. The six sign-around-the-lmo methods admit none, which is the subject of this paper. Closed-form checks. Three measurements test quantities the theory predicts in closed form. (i) The floor: balancing the two terms of (47) at ⟨∇F, D⟩ √ = ρ∥∇F ∥F ∥D∥F gives g∞ = η L∥S∥F /(2ρ), a slope of 1 in log η with that coefficient. SignMuon and SignSGD share ∥S∥F = mn exactly, so any separation between their floors is attributable to ρ alone. (ii) The budget exponent: tuning (η, µ, schedule) separately at each horizon T and fitting err ∝ T −p , η ⋆ ∝ T −q , with err := mint≤T ∥∇F (Xt )∥2∗ the squared dual norm our theorems bound. The nonconvex bound gives p = q = 21 ; a strongly convex problem gives p = q = 1,
floor Algorithm SignMuon MuonUSign MuonSign EF21-SignMuon EF21-MuonUSign EF21-MuonSign Muon SignSGD SGD Adam predicted
budget
d log g∞ /d log η
R
2
1.000 1.000 1.000 1.000 1.000 1.000 1.000 0.989 no floor 1.000
1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
1
1.000
p
R
2
1.88 1.86 1.93 2.07 2.04 2.14 2.03 1.76 8.97 2.65
0.996 0.995 0.993 1.000 1.000 1.000 0.999 0.990 0.985 0.915
1/2 or 1
stability q
R
2
ηmax ∥S∥F
0.39 0.39 0.44 0.55 0.55 0.55 0.55 0.39 −0.11 −0.66
0.94 0.94 0.94 1.00 1.00 1.00 1.00 0.94 0.50 0.62
13.4 14.9 11.8 18.9 14.9 14.9 17.6 11.1 2.06† > 100‡
1/2 or 1
2/L
Table 7: Floor exponent, budget exponents and stability edge against the predicted values, at m = n = 100 over three problem draws. The floor exponent attains its prediction exactly for eight of the nine methods possessing a floor and to within 1.1% for SignSGD, fitted on the seven step sizes at which the plateau is reached (four for Adam). SGD possesses no floor, its step vanishing with the gradient, so its floor columns are empty and its ηmax is the control reproducing 2/L; neither baseline admits a power law in η ⋆ . † SGD has no ∥S∥F ; the entry is ηmax , 1.02 times 2/L. ‡ The search reached its ceiling without encountering an edge: Adam’s step is bounded by ≈η irrespective of the gradient, so it oscillates rather than diverges.
and this instance, having σ > 0, need not occupy the nonconvex regime. The fit reports both at once: the eight norm-fixed methods tune η ⋆ as the nonconvex bound prescribes, q scattering about 21 , while the attained error falls at p between 1.76 and 2.14, a step size chosen for the worst case of the smoothness class applied to an instance far easier than that worst case. (iii) The stability edge: the largest stable η, with SGD as a control required to reproduce the textbook 2/L. Reported as the step length ηmax ∥S∥F , this would be family-independent were the operative bound the Frobenius ball; the spread measures how far that bound stands from the geometry in which each step actually resides. Conditioning. Conditioning governs the dynamics of a quadratic, and the construction above leaves it to chance, so the right panel of Figure 7 sweeps κ over five orders of magnitude, from 10 to 106 , at fixed L = 1. The eight norm-fixed methods are insensitive to it: over the entire sweep the attained ∥∇F ∥ moves by a factor of 3.2 (Muon) to 8.3 (EF21-MuonSign), and the fitted d log ∥∇F ∥/d log κ lies between −0.096 (Muon) and −0.17 (EF21-SignMuon). The factor is the measurement and the slope a summary of it, which is the order to read them in: six of the eight fits have R2 ≥ 0.90, but EF21-MuonUSign’s is 0.83 and EF21-MuonSign’s 0.67, so for those two rows the slope is not itself a quantity we would quote. The sign is mildly negative because at fixed L a larger κ entails a smaller σ, hence a flatter landscape to occupy rather than a harder one to descend; their floors are fixed by η∥S∥F , which is independent of the spectrum. SGD and Adam are sensitive to it, jointly spanning sixteen orders of magnitude across the sweep, which is why the panel is scaled to the eight and leaves those two below it. SGD’s fitted slope of 3.6 is not an exponent: its first three points lie at or below 10−20 , which on this problem constitutes exact convergence rather than a measurement. Protocol and reproduction. Every measurement above is at m = n = 100 over three problem draws (seeds 1337–1339, X0 from seed 42), with the lmo taken in bfloat16 as in the network experiments, and is reported as the geometric mean over the draws for the error metrics and the arithmetic mean for iteration counts. Learning rates are searched on logarithmic grids spanning five orders of magnitude, one per step-norm family, each ending past the largest stability edge measured for that family so that no stable step size falls outside the search. A linear grid spanning a single order of magnitude, which an earlier version of this experiment used, is narrow enough to censor an optimum at a grid boundary, giving an upper bound rather than a tuned value; the search flags any optimum at an edge. No learning rate reported above is flagged. The windows are derived from √ ∥S∥F rather than from the method name, which matters for MuonUSign and EF21-SignMuon: both take a step of length r despite the sign in their names, and under a window assigned by name both were searched an order of magnitude below the range their step length calls for. The remaining flags are on momentum, at the top of its grid (0.99), and belong to SGD and SignSGD at the largest condition numbers: an ill-conditioned quadratic asks for heavy momentum, so those two rows of the κ sweep bound the dependence from one side rather than measuring it. The other eight methods select 0.5 or less at every κ, and the three carrying an error-feedback estimator select 0 throughout. Every number in this subsection comes from a single scripted run of the released benchmark, which records each stage together with the commit, GPU and wall time it ran under.
10
−4
10
−3
10
10
1
10
0
−1
10
−2
10
−3
10
−4
t≤T
10
min‖∇F(Xt )‖F
−2
t≤T
10
−1
min‖∇F(Xt )‖2*
g∞
10
−2
10
−3
SGD, Adam below
−2
10
SGD, Adam below 3
10
horizon T
step size η SignMuon EF21-SignMuon
10
MuonUSign MuonSign
2
10
4
10
6
condition number κ = L/σ
EF21-MuonUSign EF21-MuonSign
Muon SignSGD
Adam SGD
Figure 7: Log–log fits behind Table 7, at m = n = 100 over three problem draws. Left, the accuracy floor g∞ of a constant step, the settled ∥∇F ∥F : the √ lines are parallel because every exponent is 1, and the two clusters are the two step lengths, the √ three methods with ∥S∥F = mn on the left and the five with r on the right, each swept over the window its length calls for. Centre, error at each retuned horizon, in the norm dual to each method’s own lmo ball, whence the two bands: ℓ1 above and nuclear below, comparable within a family but not across families. Right, tuned at each κ; over the five orders of magnitude swept, the eight norm-fixed methods vary by a factor of 3.2 to 8.3, against the sixteen orders of magnitude spanned by SGD and Adam. Both of the last two panels are scaled to those eight, leaving SGD and Adam below the frame: on a quadratic with an exactly known Hessian a scaled gradient step converges to machine precision. The gap reaches nineteen orders of magnitude at κ = 10, where SGD attains 2 · 10−22 against the 2 · 10−3 of the closest norm-fixed method. Dataset
CIFAR-10
Optimizer SignMuon Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign MuonUSign Adam SignSGD MuonSign SGD
Epochs
75
η0 0.02 0.1 0.02 0.05 0.005 0.02 0.001 0.002 0.1 0.02
Train Acc 99.99 99.99 100.00 99.99 99.99 99.99 99.97 99.97 99.98 99.96
Test Acc 94.60 ± 0.15 94.35 ± 0.27 94.31 ± 0.11 94.14 ± 0.07 94.04 ± 0.10 93.98 ± 0.12 93.37 ± 0.27 93.37 ± 0.26 93.31 ± 0.21 93.04 ± 0.14
Ep. to 90% 7.7 7.7 9.0 10.3 11.0 10.3 20.0 19.0 17.7 21.3
s/epoch 16.6 14.4 16.6 16.7 18.1 16.2 12.7 12.5 17.2 12.2
Table 8: CIFAR-10: centralized learning on ResNet-18, three seeds. Test accuracy is the mean ± standard deviation of the last five epochs; train accuracy, “Ep. to 90%” and “s/epoch” are means over the same three seeds. η0 was selected on a held-out 5k validation split at the same 75-epoch horizon the table reports, and the selected rate then retrained on the full 50k set, as described in Appendix A.11. Every method fits the training set to within 0.05 points of the others, so the column separates nothing on its own; the differences in the test column are not differences in how far training got.
A.13
Centralized training results
Table 8 reports the centralized CIFAR-10 results on ResNet-18 in full: the selected η0 , the final train and test accuracies, the epoch count to the 90% threshold, and the per-epoch cost. Figure 2 starts at epoch 25, where the methods are a few points apart rather than twenty. Every run uses batch 128, momentum 0.9, auxiliary rate 10−3 , and zero weight decay, so that the matrix rule and η0 are the only quantities that vary. Figure 8 gives the accuracy curves from epoch 3, Figure 9 the training loss, and Figure 10 the learning-rate sweep behind the selection.
test accuracy (%) (full run)
95.0
95.0
95.0
92.5
92.5
92.5
90.0
90.0
90.0
87.5
87.5
87.5
85.0
85.0
85.0
Muon SignMuon MuonUSign MuonSign
82.5 80.0
test accuracy (%) (final 50 epochs)
20
40
Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign
82.5 80.0
60
20
40
80.0
60
20
95
95
95
94
94
94
93
93
93
92
92
92
91
91
91
90
90 40
60
epoch
Muon SGD SignSGD Adam
82.5
40
60
90 40
60
epoch
40
60
epoch
Figure 8: Test accuracy over the whole run (top row) and from epoch 25 (bottom row), the same data at two scales, grouped as in Figure 2. Bands are ±1 standard deviation over three seeds; Muon is the gray dashed reference in every panel. Series are named in each panel’s legend. Selection horizon. Selection and reporting share the 75-epoch horizon, so each η0 above is the argmax of a validation sweep conducted at the length the table reports. An earlier protocol that selected at 15 epochs and reported at 75 was abandoned because the two horizons selected different rates for two of the methods. The selection is not sharply peaked for the sign-after methods: over the rates within a factor of five of its own optimum, SignMuon’s validation accuracy varies by 0.13 points, against 0.65 for Muon and 3.00 for SignSGD (Figure 10). Weight decay. The primary table is unregularized, the setting the theorems analyse and the one Mishra, Trivedi, and Kumar (2026)’s sweep selects. Repeating the top three at the same η0 with decoupled decay 5 × 10−4 (seed 0, decay not re-tuned) displaces each by at most 0.34 points, of the order of the three-seed standard deviation of the undecayed runs, and leaves the three within 0.23 of one another: Muon 94.46% against 94.12% undecayed at that seed, EF21-SignMuon 94.45% against 94.42%, SignMuon 94.23% against 94.43%. The ordering within that interval does change, but at a single seed and over so narrow a range it is not a measured effect; what the ablation establishes is that decay introduces no separation where the primary table shows none. Decay is applied decoupled, X ∗= 1 − ηλ, so the lmo sees the true gradient; the coupled convention would only rotate the direction, since every step here is scale-invariant.
A.14
Communication accounting
Table 2 quotes mean bits per parameter per round. This section states precisely what is counted, since the headline “32×” of the sign-compression literature is an idealization eroded by three separate effects, only one of which is customarily acknowledged. Write Pmat for the number of matrix parameters, Paux for the auxiliary group (biases, BatchNorm affine parameters, the classifier head), L for the number of matrix layers, and P = Pmat + Paux . On CNN2, Pmat = 762,560, Paux = 2,146 and L = 3. All figures below are per client per round: the uplink is what one client sends, the downlink what the server sends to one client.
training loss (log scale)
10
Muon SignMuon MuonUSign MuonSign
0
10
Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign
0
10
10
−1
10
−1
10
−1
10
−2
10
−2
10
−2
10
−3
10
−3
10
−3
10
−4
10
−4
10
−4
0
20
40
60
0
20
epoch
40
60
Muon SGD SignSGD Adam
0
0
20
epoch
40
60
epoch
validation accuracy (%) at 75 epochs
Figure 9: Training loss (log scale), grouped as in Figure 2 and over the same runs. Within a panel the methods are hard to separate (eight of the ten fall below 10−3 , differing mainly in how early), which is why the body figure carries the accuracy alone. What the loss does show is the separation between families: in the right panel Muon reaches 10−2 six to eleven epochs before SGD, SignSGD and Adam and terminates four to six times lower, while in the left panel SignMuon tracks Muon and the sign-before and both-sides orderings lie above it, in the same order as their accuracies. The three EF21 variants (centre) are indistinguishable in loss, whereas their accuracies span 0.27 points.
94
93
92 Muon SignMuon MuonUSign MuonSign
91
10
−3
10
−2
10
−1
learning rate (log scale)
10
0
Muon EF21-SignMuon EF21-MuonUSign EF21-MuonSign
10
−3
10
−2
10
−1
learning rate (log scale)
10
0
Muon SGD SignSGD Adam
10
−3
10
−2
10
−1
10
0
learning rate (log scale)
Figure 10: Learning-rate sweep at the 75-epoch selection horizon, on the tuning split and on the validation accuracy that selection ranked, grouped as in Figure 2, with Muon repeated as the gray dashed reference. The shaded band marks η0 ∈ [0.01, 0.05], the only interval every method but Adam was swept over; the nine vary by 0.10 to 0.93 points within it, SGD (0.44) among them, so an absolute window no longer discriminates between the families, their optima lying two orders of magnitude apart. The matched comparison is the relative one. Within a factor of five of its own optimum SignMuon varies by 0.13 points and SignSGD by 3.00; the two emit steps of identical Frobenius length, so the difference is attributable to the lmo. The remaining eight lie between these, from 0.46 (MuonSign) to 2.00 (EF21-MuonSign). Taking the sign of the oracle’s output does not reduce this insensitivity: SignMuon’s sweep is the flattest of the ten.
(i) The uplink alphabet. The randomized sign of Section 4 renders every transmitted symbol a genuine bit, so the uplink costs one bit per parameter with no entropy coding required to realize it.
Method
Up
Down
Muon, MuonServer SGD, Adam
Up (bits) Down (bits) 32 32
32 32
1.0× 1.0×
1.0× 1.0×
SignMuon SignSGD MuonSign EF21-MuonSign
1.0870 1.0870 1.0870 1.0871
1.0870 1.0870 1.0870 1.0871
29.4× 29.4× 29.4× 29.4×
29.4× 29.4× 29.4× 29.4×
MuonUSign EF21-SignMuon EF21-MuonUSign
1.0870 1.0871 1.0871
32 32 32
29.4× 29.4× 29.4×
1.0× 1.0× 1.0×
Table 9: Communication per client per round on CNN2, under the randomized-zero convention. Bits are per model parameter; reductions are against a 32-bit baseline. The fourth decimal separates the error-feedback methods from the rest: it is the per-layer scale of point (iii). Groups: uncompressed references, one bit in both directions, one bit on the uplink only.
(ii) The auxiliary group is never compressed. It travels at full precision in both directions for every method, so a “one-bit” channel actually costs 1 · Pmat + 32 Paux = 1.087 bits, P a 29.4× reduction rather than 32×. On CNN2 the group is 0.28% of the parameters; on an architecture with a large embedding or head it would dominate this table, which is why the quantity is computed per model rather than quoted. (iii) Error feedback carries one scale per layer. Both EF21 channels transmit the pair (st , αt ) with one full-precision αt per matrix layer: on the uplink for every EF21 method, and again on the downlink for EF21-MuonSign. That is 32L bits, adding 32L/P ≈ 1.3 × 10−4 bits per parameter here. That lies four decimal places in, and it is reported for completeness rather than because it alters a conclusion: it is the difference between “one bit per parameter” and “one bit per parameter, plus a constant”. (iv) Which methods compress the downlink. The criterion is not whether the method applies a compressor but whether the object the server must distribute is already ±1-valued. Three cases qualify: the majority vote sagg itself (SignMuon, SignSGD), t a signed lmo output (MuonSign), and a primal error-feedback residual (EF21-MuonSign). In the first of these the server broadcasts the vote rather than the model and each client applies the step to its local copy; the copies start from a common X0 and receive identical updates, so they never drift. The remaining three methods must distribute a dense server-side quantity, namely polar(·) of the aggregate for MuonUSign and EF21-MuonUSign and a scaled average of signs for EF21-SignMuon, and therefore transmit it at full precision. Table 9 collects the four effects into the per-round cost of each method, and is the source of the Up and Down columns of Table 2. It is computed by federated.algorithms.communication_bits from the alphabet and the measured zero rate of the run it describes, so a run made under the legacy ternary convention reports its own higher figure rather than the idealized one. Every run behind Table 2 was made under the randomized convention, which makes these figures realized rather than idealized. Two diagnostics record what the convention had to absorb, both counted before the randomized mapping and therefore feeding no accounting. Exact zeros do occur on the uplink, at up to 3.7% of coordinates for MuonSign and 0.5% for SignMuon, and at none at all for the three error-feedback methods, whose compressed quantity is a residual rather than a direction. And the majority vote tied in no coordinate of any evaluated round of any reported run, as at N = 11 and ±1 client messages it cannot.
A.15
Federated training results
Figure 11 (together with Table 2 in the main text) reports the comparison of optimizers at N = 11 clients. The figure additionally shows Muon with a server-side LMO, which is not a communication-efficient method but isolates whether moving the oracle off the clients carries a penalty on its own; it does not (85.74 ± 0.11% against Muon’s 85.98 ± 0.26%), so the gaps in Table 2 are attributable to compression and sign placement rather than to where the oracle runs. On the sign-after placement the cost of error feedback depends on the setting, and federation is where it is largest: EF21SignMuon lies 1.00 points below SignMuon here, against 0.29 points centrally (Table 1), while on nanoGPT the two are indistinguishable (Table 3). Two features of the figure do not appear in the table. The threshold column does not order the methods as final accuracy does: MuonUSign crosses 80% in 500 rounds, ahead of SignMuon’s 540 and EF21-SignMuon’s 640, and finishes below both, so which method leads depends on where the round budget is cut. And the left panel orders them differently again: the lowest test cross-entropy of the eleven is EF21-SignMuon’s, 0.482 ± 0.005, and the highest bar Adam’s is Muon’s, 0.586 ± 0.016, the reverse of how those two stand on accuracy. Cross-entropy and accuracy are not obliged to agree, and it is accuracy the
band is ±1 s.d. over 5 seeds Muon Muon (srv) SignMuon MuonUSign SignSGD SGD EF21-MuonSign MuonSign
0.60
test cross-entropy
1.4
0.56
1.2
0.52
85 80
EF21-MuonUSign
1.0
EF21-SignMuon
0.48 1200
1500
1800
0.8
test accuracy (%)
1.6
75 70
Muon SignMuon Muon (srv) EF21-SignMuon MuonUSign EF21-MuonSign EF21-MuonUSign MuonSign SGD SignSGD
86
65
84
60 82
55
0.6
80
50 0
500
1000
1500
2000
communication round
SignMuon EF21-SignMuon
MuonUSign MuonSign
1200
0
500
1500
1800
1000
1500
2000
communication round
EF21-MuonUSign EF21-MuonSign
Muon Muon (server LMO)
SignSGD SGD
Adam
Figure 11: CIFAR-10 federated learning on CNN2 at N = 11 clients and batch 192 per client, every method evaluated on the exact server model Xt . Both panels are clipped to exclude round 0, the untrained model, which is identical for every method. Solid lines are the one-bit methods, dashed the uncompressed references and dash-dot SignSGD, so that hue is not the only channel separating eleven curves. The insets magnify the final 45% of rounds, where every number in Table 2 is read, and name each curve at its own end; Adam finishes clear of the other ten and so falls outside the magnified window. Eleven methods are drawn, one more than Table 2, the extra being the server-side-LMO Muon control.
comparison is about; the loss panel is drawn so that the disagreement is on the record rather than suppressed by the choice of metric.
A.16
Language-modelling details
Setup. Upstream modded-nanoGPT record #40 (2025-10-04), the last record before NorMuon and hence the last whose hidden-matrix optimizer is a clean, separable momentum → LMO → step Muon, so our variants inject exactly at the LMO. Model: 12 layers, model dimension 768, 6 heads of dimension 128, vocabulary 50,257; hidden matrices are 768 × 3072 (the merged Q/K/V/O weight qkvo_w is used as four 768 × 768 blocks, and both the LMO and the compressor scale are applied per block; the two MLP matrices are the up-projection c_fc and the zero-initialized output projection c_proj, which maps the 3072-dimensional hidden activation back to the model dimension). Data: FineWeb10B, the 10B-token sample of FineWeb (Penedo et al. 2024) that the speedrun repository prepares and tokenizes; 262,144 tokens per step, 2330 steps (= 611M tokens), validation on the fixed 10,485,760-token split. Hardware: one rented 8×H100 SXM node (80 GB per GPU; dual Xeon Platinum host, 224 vCPU, 2 TB RAM, PCIe 5.0 ×16, NVMe scratch), driver 595.71.05, running PyTorch 2.10.0+cu128 under Python 3.12.3 in a virtual environment of its own rather than the container’s torch, since the prebuilt Flash-Attention-3 kernel the record fetches exists for no CUDA-13 build; one process per GPU. Gradients are averaged by reduce_scatter so the owning rank runs the centralized update and all_gather returns the parameter, i.e. the compression is a property of the update rule, as in the centralized algorithms we analyze. Hyperparameters. Matrix/gate optimizer: η0 = 0.06 (lmo family) or 0.03 (sign family), per-layer scaled by the unit-gain rule (Appendix A.17); Nesterov momentum µ = 0.95, warmed up linearly from 0.85 over the first 300 steps and cooled back to 0.85 over the last 50; weight decay 0 (the record’s own value); η constant then linearly cooled to 0.1η0 over the final 45% of the 2290 scheduled iterations, with the 40-step extension held at that floor; LMO by 5 Polar-Express iterations. Auxiliary parameters (embeddings, scalars, head) use the record’s distributed Adam unchanged: η = 0.008, β = (0.65, 0.95), ε = 10−8 , no weight decay, per-parameter multipliers 75 on embeddings and 5 on scalars, stepped every other iteration. Nothing above was tuned by us: the lmo family runs at the record’s own η0 , and every value outside the matrix optimizer is the record’s. Wall-clock varies by at most 1.1% across all eight methods (61.4–62.1 ms/step), all of them some 2% above the record’s own 60.4 ms/step, which
(a)
(b)
5.00
5.00
Training loss
4.75
MuonSign EF21-SignMuon EF21-MuonUSign EF21-MuonSign (W)
4.50 3.40
4.25 3.35
4.00 3.30
3.75
2100
2200
2300
4.50 4.25
MuonSign EF21-SignMuon EF21-MuonUSign EF21-MuonSign (W)
3.35
4.00
3.30
3.75
120
130
140
3.50
3.50 3.25
Muon SignSGD SignMuon MuonUSign
4.75
Validation loss
Muon SignSGD SignMuon MuonUSign
0
500
1000
1500
3.25
2000
20
40
Optimizer step
60
80
100
120
140
Training time (s, 8×H100)
Downlink contraction / gap
Figure 12: NanoGPT, supporting curves. (a) Training loss against optimizer step (EMA-smoothed; the logged quantity is a per-rank sum over 32,768 tokens, divided out here). (b) Validation loss against the speedrun clock, which excludes validation and compilation. Insets magnify the boxed tails, as in Figure 3. Marker positions are staggered in both figures so that curves lying within a line width of one another can still be followed individually. The ordering is the same on both axes: no method incurs a measurable wall-clock premium for its compressor or its error-feedback buffers. Note in (a) that EF21-MuonSign’s training loss, taken at W, exhibits no degradation throughout, which is what localizes its validation gap to the tracking of X rather than to training.
10
−1
10
−2
10
−3
10
−4
_ _
_ α(Δ ↓ ) ‖X − W‖F /‖W‖F
250
500
750
1000
1250
1500
1750
2000
2250
Optimizer step
Figure 13: The downlink measurement for EF21-MuonSign, per layer type: the contraction α(∆↓ ) the scaled sign actually achieves (solid) and the resulting server/broadcast gap ∥Xt − Wt ∥F /∥Wt ∥F (dashed). On the zero-initialized c_proj the contraction sits one to two orders of magnitude below the other two from step 250 on, then collapses over the last 500 steps to 1.2 × 10−4 , three orders below them, while the gap stops decreasing near 10−1 ; the other two contract at Θ(10−1 ) throughout and close their gaps by 42 and 64× over the run, ending near 10−3 . This is Remark 4 rendered as a measurement.
every method pays equally: our port replaces its Triton kernels and batched sharded transport with a pure-torch per-parameter equivalent. Supporting curves. Figure 12 gives the two views Figure 3 omits: training loss against optimizer step, and validation loss against the speedrun clock. The second is what supports the claim of equal wall-clock in Section 5.3; the first shows that EF21-MuonSign trains normally at W, which is what places its validation gap in the tracking of X rather than in training. Figure 13 then measures that tracking directly, per layer type.
uplink
downlink
α
lag
α
gap
EF21-SignMuon qkvo_w (×10) 0.640 0.66 c_fc (×11) 0.633 0.62 c_proj (×11) 0.634 0.62
– – –
– – –
EF21-MuonUSign qkvo_w 0.374 0.81 c_fc 0.323 0.82 c_proj 0.597 0.62
– – –
– – –
Layer type
EF21-MuonSign qkvo_w 0.406 0.79 0.380 0.0011 c_fc 0.355 0.78 0.253 0.0013 c_proj 0.596 0.61 1.2×10−4 0.083
Table 10: Compressor diagnostics at step 2330, medians over the identical layers of each type. α is the contraction the scaled sign achieves on that round’s residual (2/π for an isotropic residual, 1/d in the worst case); “lag” is ∥target − estimator∥F /∥target∥F ; “gap” is ∥Xt − Wt ∥F /∥Wt ∥F . Downlink columns are empty for the two methods that broadcast exactly. Gates are omitted (they are 6 × 12 and 1 × 12). Compressor diagnostics. Table 10 reports, per layer type at the final step, the contraction each scaled sign achieves, α(∆) = ∥∆∥21 /(d∥∆∥2F ), and the relative estimator lag. Three observations merit separate comment. (i) Every uplink is well-contractive, α ∈ [0.32, 0.64] against the isotropic 2/π = 0.637, and EF21-SignMuon’s is uniformly the best, the entries of its orthogonal target being the most evenly spread; yet the uplink lag is large (0.61–0.82), so that the estimator remains far from its target at every step and the methods nonetheless train well, the LMO being scale-invariant and requiring only the direction. (ii) The single anomaly in the table is the c_proj downlink, α = 1.2 × 10−4 , a factor 4.8 × 103 below its uplink on the very same layer. Since both compressors are the same operator, the difference is a property of the residual, not of the compressor: the uplink residual is refreshed by an exogenous stochastic gradient each round, the downlink residual is generated by the compressor’s own recursion (Remark 4). (iii) The resulting validation loss at the server model X falls to 4.20 by step 750, rises to 5.52 by step 1500, and then holds there (5.51–5.58 to the end of the run): a persistent offset above the broadcast model, not a divergence. Where the two models part. The c_proj anomaly of item (ii) is what separates EF21-MuonSign’s two models: on that layer the gap ∥Xt − Wt ∥F /∥Wt ∥F stops decreasing at 8% against <1% for every other layer and both gates, and it is the only layer whose gap fails to close, which is what localizes the ≈2.2-nat offset of item (iii) to it. The reason is the initialization. A layer built from zero receives maximally correlated updates, so its downlink residual concentrates, and a compressor that moves every coordinate by mean |∆↓ | cannot catch the coordinates driven hardest. This is the mechanism of Remark 4√ rather than a tuning failure. Lowering η0 does not repair it, because the admissible step size would have to shrink by a further r in the layer rank (Remark 5); only a downlink compressor contractive in the spectral norm would.
A.17
Per-Layer Step Sizes: the Unit-Gain Rule
This appendix derives the heuristic (7) stated in the main text, selects its one free exponent by measurement, and delimits its scope. SGD and Adam have no norm-fixed step, so the rule does not apply to them; both are run at one global rate throughout. Our counterexamples, like the analysis of Mishra, Trivedi, and Kumar (2026), concern a single matrix, where one scalar step size suffices. A network has layers of very different shapes, and the methods of this paper produce step matrices from two families whose norms scale differently with shape, so a single global η cannot be simultaneously correct for both families and across layers. This is not a lacuna we are obliged to tolerate: the layer-wise LMO framework to which our convergence result reduces (Riabinin et al. 2025; Gruntkowska et al. 2025) already carries per-layer norms ∥ · ∥(ℓ) , smoothness constants Lℓ and radii ηℓ ; it is only the experiments that have hitherto fixed that radius at a constant. What follows instantiates it. The specific rule is this paper’s own; the criterion behind it is borrowed (it is the average-case form of the spectral scaling condition of the maximal-update literature (Yang et al. 2021; Yang, Simon, and Bernstein 2023; Large et al. 2024)), and its lmo branch reproduces the aspect factor Muon already uses in practice (Jordan et al. 2024b), which is the external check we rely on. The two families. For a parameter reshaped to X ∈ Rm×n (m the output dimension, n the input dimension, r = rank = min(m, n) generically), the step matrix P that a method applies belongs to one of two families: P = UV⊤ (lmo),
P ∈ {±1}m×n (sign).
(49)
The lmo family comprises Muon, MuonUSign, EF21-MuonUSign, EF21-MuonSign and EF21-SignMuon; the sign family comprises SignMuon, MuonSign and SignSGD. Both have exactly known Frobenius norms: ∥UV⊤ ∥2F = tr(VU⊤ UV⊤ ) =
√ √ tr(V⊤ V) = r, so ∥P∥F = r; and a ±1 matrix has ∥P∥F = mn. (EF21-SignMuon steps along the error-feedback estimator √ dest r holds only in the limit; we assign it to the t of polar(M̃t ) rather than along the oracle output itself, so for it ∥P∥F = lmo family on that basis.) m×n The criterion. Define , i.e. how much it amplifies a generic input in root-mean-square terms, √ the RMS gain of A ∈ R with rms(v) := ∥v∥/ dim: Eu rms(Au)2 2 γ(A) := , u ∼ N (0, In ). (50) Eu [rms(u)2 ]
Since E∥Au∥2 = tr(A⊤ A) = ∥A∥2F and E∥u∥2 = n, (50) evaluates in closed form: ∥A∥F γ(A) = √ . m
(51)
The single modelling assumption is that u is isotropic and independent of A, to which we return below. Controlling a layer update’s RMS-to-RMS effect is precisely the desideratum of the spectral scaling condition (Yang, Simon, and Bernstein 2023) and of the modular norm (Large et al. 2024); (50) is its average-case (isotropic-input) version, and when the independence fails, that is, for aligned inputs, where the operator norm governs the gain instead, one recovers the µP value a = 1 discussed below. 2 Every standard initialization √ √ with variance ∝ 1/n has shape-independent gain. For 2He normal (σ = 2/n),√∥X∥F = √ σ mn = 2m, so γ(X) = 2; for PyTorch’s default Kaiming-uniform convolution (σ = 1/(3n)), γ(X) = 1/ 3. Either way a constant. Requiring the update’s gain to be a fixed fraction of the weight’s is therefore simply the requirement that the per-step gain be the same on every layer, and by (51) that is one formula: √ m ηℓ = η0 λℓ , λℓ = (52) ∥P∥F which gives γ(ηℓ P) = η0 exactly, √ for every shape and both families, so that η0 is the per-step RMS gain. One caveat: the rule is derived from ∥UV⊤ ∥F = r, which holds for the exact oracle. Five Newton–Schulz √ steps leave the singular values of the returned matrix in a band around 1 rather than at 1, so its Frobenius norm falls below r, by 5–22% on our layer shapes; for the lmo-terminated methods η0 is therefore the per-step RMS gain of the exact step, realized up to that shape-dependent factor. Substituting the two Frobenius norms of (49), q 1 (53) λlmo = max 1, m λsign =√ . ℓ ℓ n , n p Justification of (53). The first expression is exactly the aspect-ratio factor max(1, m/n) present in the reference Muon implementation (Jordan et al. 2024b), which was introduced as a practical heuristic. It is also the point at which the rule parts company with the geometric alternative: taking the layer norm to be RMS→RMS rather than spectral (Appendix A.1) prescribes p m/n, which coincides with unit gain for m ≥ n and falls below it for m < n, where the two disagree and the implemented factor is the unit-gain one. The disagreement is the informative case: p p on a wide layer the RMS→RMS ball shrinks the step in proportion to m/n, whereas the gain (51) of UV⊤ is already min(m, n)/m = 1 there and needs no correction. Nor does the geometric route reach the sign family at all: a ±1 matrix is the oracle output of no norm (Theorems 1–3), so there is no unit ball whose radius could set its scale, while (52) applies to it unchanged. The unit-gain criterion derives the aspect factor, and also explains why Muon’s step size is known to transfer across widths: its step has γ = η independently of n, so no correction in the input dimension is needed. The second expression is the counterpart the sign family has never been given. Only η0 is tuned, and it is now a shape-free quantity; the shape dependence is determined a priori. Two consequences follow. First, λℓ is a deterministic function of the layer shape, known to server and clients alike, so per-layer step sizes require no communication and leave the one-bit-per-parameter budget intact. Second, √ on the CIFAR ResNet-18 of √ 27 at the first convolution to 1/ 4608 in the last stage), so a our experiments λsign spans a factor of 13 across layers (from 1/ ℓ single global rate is necessarily a compromise: roughly correct for the middle of the network, several-fold too large at the first convolution and too small at the last stage. The lmo family is exempt from this, which is one reason full-precision Muon is easier to tune than its sign-compressed variants. Selecting the exponent. Writing λsign = n−a , the unit-gainP rule is a = 21 . Identity (51) assumes the input independent of A, ℓ the right model for a single step; if the accumulated update t ηPt aligns with the activations, its gain is Θ(ηn) rather than √ Θ(η n), giving a = 1, the µP rule η ∝ 1/n for sign-like updates (Yang et al. 2021). A direct measurement decides between √ the regimes: we track the realized gain ∥Xt − X0 ∥F / m at a constant step size (under a decaying schedule the accumulation saturates and the fit reports the schedule) and fit its growth exponent h in t, which is 12 for incoherent accumulation and 1 for aligned. Over 20 epochs the fit returns ĥ = 0.513 for Muon, 0.515 for SignMuon, 0.490 for SignSGD and 0.561 for MuonSign, each at R2 ≥ 0.999. Muon is the control: (53) and µP prescribe the lmo family the identical multiplier, so its exponent is the
diagnostic’s reading when the rule is not in question, and the sign methods match it. All four values lie near 12 and none near 1, so the accumulation is incoherent on this network and we adopt a = 12 for both families in every network experiment. The exponent fixes the shape dependence of λℓ and the transfer of η0 across widths; it makes no claim about which a maximizes accuracy at one fixed width, where the choice is largely absorbed into η0 . The placement of weight decay is not arbitrary. The same scale invariance that makes λℓ necessary also dictates where an ℓ2 penalty may be applied: sign(cM) = sign(M) and polar(cM) = polar(M) for all c > 0. Folding the decay into the e t = Gt + λwd Xt , the convention of Mishra, Trivedi, and Kumar (2026) and of most sign-method implementations, gradient, G therefore supplies no contraction: the step length ηt λℓ ∥P∥F is fixed by (49), and the decay term can only rotate the direction. That rotation is governed by ρt = λwd ∥Xt ∥F /∥Gt ∥F , which drifts from negligible to Θ(1) as ∥Gt ∥F falls over training and which depends on each method’s own momentum scale, so one nominal λwd is a different perturbation for each method. Decoupled decay, Xt+1 = (1 − ηt λwd )Xt − ηt λℓ Pt , is by contrast commensurate with the update under the unit-gain rule: its displacement has gain ηt λwd γ(Xt ) against the step’s ηt , a ratio free of ηt , of the layer shape and of the method. We therefore decouple, and use the coupled form only in an ablation. This explains an observation of Mishra, Trivedi, and Kumar (2026): sweeping λwd ∈ {0, 0.1, 0.2} coupled over 330 CIFAR-10 ResNet-50 configurations, every Muon and Sign-Muon entry in their top ten (the only entries with a decay sweep) selects λwd = 0; at the two nonzero values the decay term dominates the gradient e t for most of training, so the transmitted sign approaches sign(Xt ) and the sweep rejects this placement of the penalty, not in G regularization as such. Scope of the analysis. Our theorems are stated for unregularized f , so we report unregularized runs as the primary comparison and weight decay as an ablation; the reference nanoGPT configuration we build on also uses λwd = 0 for every parameter group. Two remarks delimit the gap. First, the coupled form is covered verbatim: it is nothing other than running the same method on 2 fλ = f + λwd 2 ∥X∥F , so every rate carries over with Li 7→ Li + λwd ri . The rank factor is not slack in the bound: our smoothness is measured in the nuclear norm against a spectral-norm displacement (Assumption 2), and ∥λwd Z∥∗ ≤ λwd ri ∥Z∥2→2 is tight at Z = Iri ; L 7→ L + λwd would be the Euclidean statement, and these rates are not Euclidean. The paradox is that this is precisely the variant which does not regularize. Second, the decoupled form is √ not covered by our rates, yet it furnishes something the analysis requires. Since ∥Pt ∥F is a known √ constant and λℓ ∥Pt ∥F = m identically under (52), the triangle inequality gives ∥Xt+1 ∥F ≤ (1 − ηt λwd )∥Xt ∥F + ηt m, and hence, for any ηt λwd ≤ 1, γ(Xt ) ≤ max γ(X0 ), λ−1 for all t, (54) wd a bound on the layer’s gain that is uniform in t and independent of the layer shape. Norm-constrained updates are what render this possible: for SGD the step length is data-dependent and no such a priori bound exists. Since layer-wise lmo analyses assume smoothness on a bounded region, (54) is the statement that decoupled decay supplies that region. We do not claim a convergence rate for the decoupled variant itself. Sensitivity to the rule. Equation (7) is a heuristic, so we state its scope precisely. Each candidate rule, one global rate (λℓ = 1), unit gain (λℓ = n−1/2 ) or µP (λℓ = n−1 ), shifts the selected η0 by roughly the multiplier it prescribes; what would matter is a change in the ordering of the methods. The exposure is bounded twice over: the lmo family cannot move, unit gain and µP prescribing it the identical multiplier, and the three sign methods are tuned and reported under one rule, so a wrong exponent rescales them alike. Neither consideration is a measurement, so Table 11 re-tunes the three sign methods from scratch under each rule on federated CNN2, whose three matrix parameters span a factor of 7.8 in λsign ℓ , and runs each selected rate at the reporting horizon. Two things follow. The selected η0 moves by roughly the multiplier the rule prescribes, which is the rule working and not a defect: measured against one global rate, unit gain raises SignMuon’s rate by a factor of 50 and µP by 103 , against the √ n ∈ [8.7, 67.9] and n ∈ [75, 4608] that the three layer shapes prescribe. The ordering, meanwhile, does not move: SignMuon, then MuonSign, then SignSGD under every rule, the first ahead of the last by 4.3 points under the global rate, 4.3 under unit gain and 4.0 under µP. Within a method the rules agree to within 0.2 points for SignMuon and 0.1 for SignSGD, at or below the seed spread; MuonSign is the one case where they separate at all, unit gain standing 0.57 above µP and 0.68 above the global rate, about two seed spreads, and in the direction that favours the rule we adopted. The sign-family ordering of Table 2 therefore does not rest on the exponent, which the exposure argument above could only bound rather than establish. √ Comparison with concurrent work. Mishra, Trivedi, and Kumar (2026) analyse the normalized update Dt = S̄t / mn, justified by ∥Dt ∥op ≤ ∥Dt ∥F√= 1 under their spectral-norm smoothness assumption, and remark that updating with S̄t directly is equivalent after absorbing mn into ηt . That equivalence holds for a single matrix but not across layers of differing shape, and their algorithm applies no shape factor, so their experiments use a single loose p global rate as well. The substitution is also √ in a shape-dependent way: S̄t has rank at most min(m, n), so ∥ S̄ ∥ ≤ min(m, n) ∥ S̄ ∥ and the substitution of mn for t F t op p √ the operator norm √ is loose by up to min(m, n). That bound itself grows with depth, from 27 ≈ 5.2 at the first convolution of a ResNet-18 to 512 ≈ 22.6 in the last stage, so the spectral radius the analysis assigns to the step varies across the network instead of remaining uniform. Table 12 sets the rules side by side.
η0
Test acc (%)
SignMuon global 1 SignMuon unit gain n−1/2 SignMuon µP n−1
0.002 0.1 2
85.68 ± 0.17 85.72 ± 0.24 85.52 ± 0.01
MuonSign global 1 MuonSign unit gain n−1/2 MuonSign µP n−1
0.001 0.02 0.5
82.26 ± 0.40 82.94 ± 0.19 82.37 ± 0.27
Method
SignSGD SignSGD SignSGD
Rule
λℓ
global 1 0.0005 81.37 ± 0.21 unit gain n−1/2 0.01 81.44 ± 0.15 µP n−1 0.5 81.47 ± 0.25
Table 11: The per-layer rule ablation, on the federated CNN2 of Table 2. Each (method, rule) pair is re-tuned from scratch on the five-point lattice of Appendix A.11 and then run at 2000 rounds: three seeds under the two alternatives, and under unit gain the five seeds Table 2 reports. Rule
lmo
sign
global (a = 0) 1 1 p — RMS→RMS ball p m n m Muon default ) 1 n pmax(1, m unit gain max(1, ) n−1/2 n p m µP (a = 1) max(1, n ) n−1 −1/2 Mishra et al. r (mn)−1/2
Equalizes nothing lmo trust region lmo gain per-step gain, both aligned accumulation ∥P∥F
Table 12: Per-layer step-size multipliers λℓ . Only η0 is tuned; λℓ is fixed a priori by the shape. The last four rules differ only in the sign family, and the lmo column of the unit-gain rule coincides with the factor already employed in practice (Jordan et al. 2024b), which is our principal evidence that (50) is the correct criterion. The second row is the multiplier implied by taking the layer geometry to be RMS→RMS rather than spectral: it departs from the other four for m < n and, being a property of a unit ball, is undefined for steps that are the oracle of no ball. The last row is the normalization of Mishra, Trivedi, and Kumar (2026), which equalizes ∥P∥F rather than the gain.
A.18
Algorithms
Federated protocol. At the start of round t each client j holds the global model Xt−1 and evaluates one stochastic gradient (j) (j) Gt = ∇fj (Xt−1 ; ξt ) at it; clients take no local parameter steps, so one round is one server step and no client-drift term arises. (The released runs accumulate three mini-batches of 64 at fixed weights to save activation memory; the BatchNorm statistics being frozen (Appendix A.11), the loss is separable across samples and the average is a gradient at batch 192, except where a client’s shard ends in a shorter mini-batch.) Each client updates its own momentum buffer, applies the LMO (Algorithm 1), and transmits the elementwise sign, (j) (j) (j) (j) (j) (j) (j) Mt = µMt−1 + (1 − µ) Gt , Dt = −A Mt , st = sign Dt , with the exponential-moving-average momentum of (5), matching Algorithms 8–9; the uplink is one bit per matrix parameter. PN (j) The server aggregates by majority vote, sagg = sign , which is ±1 in each component: client messages are ±1-valued t j=1 st by the convention of Section 4, so at an odd client count the vote cannot tie, and at an even count a tie is broken by a fair coin. Momentum having been applied at the clients, the server steps directly, Xt = Xt−1 − ηt sagg t , and the vote rather than the model travels back down the link: every client applies the same ±1-valued update to its local copy of the model, so client and server models remain identical and the downlink carries one bit per parameter as well (Appendix A.14). The final classification layer is exempt from the rule and trained with AdamW. Federated error feedback. The repair for the biased sign compressor is EF21 (Richtárik, Sokolov, and Fatkhullin 2021) in the LMO form of Gruntkowska et al. (2025): it changes the uplink message, and for EF21-MuonSign the downlink as well. (j) (j) Client j compresses the residual ∆t between its estimator and the quantity it would otherwise send, the polar factor Dt for (j) EF21-SignMuon, whose oracle runs on the client, and the momentum M̃t for EF21-MuonUSign and EF21-MuonSign, whose (j) (j) (j) (j) oracle runs on the server, and transmits the pair (sign(∆t ), αt ) with αt = mean |∆t |. The server accumulates these into a global estimator (dt in Algorithm 8, gt in Algorithm 9) and either steps along it or applies one LMO to it. The extra scalar is one full-precision number per matrix layer per round, so the uplink stays at ≈1 bit per parameter; the estimator itself is dense, so the downlink carries a full-precision model unless a second error-feedback loop compresses it, as EF21-MuonSign’s does.
Algorithm 1: MuonLMO Input: tensor Y; Newton-Schulz coefficients a = 3.4445, b = 4.7750, c = 2.0315; iteration count ns_steps Output: polar factor D ≈ UV⊤ of Y 1: Y ← ReshapeTo2D(Y) ▷ Flatten tensor to matrix m × n 2: Y ← Y/∥Y∥F ▷ Normalize (optional) 3: for k = 1 to ns_steps do ▷ 5th-order Newton-Schulz orthogonalization 4: A ← YY⊤ 5: Y ← a Y − b AY + c A2 Y 6: end for 7: D ← ReshapeToOriginal(Y) ▷ Reshape back to the original tensor shape 8: return D Algorithm 2: SignMuon Input: Initial model X0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0 2: for t = 1 to T do 3: Gt ← ∇f (Xt−1 ; ξt ) ▷ Stochastic gradient 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) 6: Dt ← MuonLMO(M̃t ) 7: s↑t ← sign(Dt ) ▷ Uplink sign compression 8: Xt ← Xt−1 − ηt s↑t ▷ Update parameters 9: end for Algorithm 3: EF21-SignMuon Input: Initial model X0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0, dest 0 ←0 2: for t = 1 to T do 3: Gt ← ∇f (Xt−1 ; ξt ) ▷ Stochastic gradient 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation (EMA) Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) 6: Dt ← MuonLMO(M̃t ) 7: ∆↑t ← Dt − dest ▷ Uplink residual (polar factor) t−1 ↑ ↑ 8: αt ← mean(|∆t |) ↑ ↑ est 9: dest ▷ Uplink EF21 t ← dt−1 + αt sign(∆t ) est 10: Xt ← Xt−1 − ηt dt ▷ Update parameters 11: end for All six federated methods are instances of just two templates, separated by where the Muon LMO is evaluated. When the sign acts after the LMO (the SignMuon family), each client must orthogonalize locally, so the LMO runs on the worker and the client transmits a compressed direction (Algorithm 8). When the sign acts before the LMO (the MuonUSign/MuonSign family), the client transmits a compressed gradient, and the server reconstructs it and applies a single LMO (Algorithm 9). Within each template, a method is fixed by its uplink compressor C ↑ ∈ {sign, EF21} and downlink compressor C ↓ ∈ {exact, sign, EF21-P}; Table 13 lists the six instantiations. The two uplinks aggregate differently, and each aggregation is forced. The EF21 uplink averages the decompressed messages, P (j) (j) gt = gt−1 + N1 j αt sign(∆t ), as Gruntkowska et al. (2025, Algorithm 3) prescribe and as the reduction of Appendix A.10 requires; replacing that average by a vote would leave the framework and forfeit Theorem 5. The plain sign uplink instead takes P (j) a majority vote, sign( j st ), before the server LMO. Voting is what keeps the oracle’s argument a ±1 matrix, so that the
Algorithm 4: MuonUSign Input: Initial model X0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0 2: for t = 1 to T do 3: Gt ← ∇f (Xt−1 ; ξt ) ▷ Stochastic gradient 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) 6: s↑t ← sign(M̃t ) ▷ Uplink sign compression 7: Dt ← MuonLMO(s↑t ) 8: Xt ← Xt−1 − ηt Dt ▷ Update parameters 9: end for Algorithm 5: MuonSign Input: Initial model X0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0 2: for t = 1 to T do 3: Gt ← ∇f (Xt−1 ; ξt ) ▷ Stochastic gradient 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) 6: s↑t ← sign(M̃t ) ▷ Uplink sign compression 7: Dt ← MuonLMO(s↑t ) 8: s↓t ← sign(Dt ) ▷ Downlink sign compression 9: Xt ← Xt−1 − ηt s↓t ▷ Update parameters 10: end for Algorithm 6: EF21-MuonUSign Input: Initial model X0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0, g0est ← 0 2: for t = 1 to T do 3: Gt ← ∇f (Xt−1 ; ξt ) ▷ Stochastic gradient 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) est 6: ∆↑t ← M̃t − gt−1 ▷ Uplink residual ↑ 7: αt ← mean(|∆↑t |) est + αt↑ sign(∆↑t ) ▷ Uplink EF21 8: gtest ← gt−1 9: Dt ← MuonLMO(gtest ) 10: Xt ← Xt−1 − ηt Dt ▷ Update parameters 11: end for server-side method is exactly the centralized MuonUSign, polar(sign(·)) of (6), evaluated at the aggregated sign; averaging would feed polar an argument valued in {−1, −1 + 2/N, . . . , 1} and define a different method, one that agrees with MuonUSign only at N = 1. The choice also matches the sign-compression literature it inherits from (Bernstein et al. 2019). It carries no consequence for the downlink of this family, the polar factor being dense either way. As in the centralized setting, both templates are applied per matrix parameter, while vector parameters and the final classification layer are optimized with AdamW.
Algorithm 7: EF21-MuonSign Input: Initial model X0 = W0 , momentum coefficient µ, learning rate ηt Output: Updated model X 1: M0 ← 0, g0est ← 0 2: for t = 1 to T do 3: Gt ← ∇f (Wt−1 ; ξt ) ▷ At the broadcast model 4: Mt ← µMt−1 + (1 − µ) Gt ▷ Momentum accumulation Mt , (default), 5: M̃t = (1 − µ) Gt + µMt , (Nesterov) est 6: ∆↑t ← M̃t − gt−1 ▷ Uplink residual ↑ 7: αt ← mean(|∆↑t |) est 8: gtest ← gt−1 + αt↑ sign(∆↑t ) ▷ Uplink EF21 9: Dt ← MuonLMO(gtest ) 10: Xt ← Xt−1 − ηt Dt ▷ Update parameters (server) ↓ ▷ Downlink residual 11: ∆t ← Xt − Wt−1 12: αt↓ ← mean(|∆↓t |) ▷ Downlink EF21-P 13: Wt ← Wt−1 + αt↓ sign(∆↓t ) 14: end for
Method
LMO
Uplink C ↑
Downlink C ↓
SignMuon EF21-SignMuon
worker worker
sign / MV EF21
exact exact
MuonUSign MuonSign EF21-MuonUSign EF21-MuonSign
server server server server
sign / MV sign / MV EF21 EF21
exact sign exact EF21-P
Table 13: The six federated methods as instantiations of the two templates: Algorithm 8 (worker-side LMO; rows 1–2) and Algorithm 9 (server-side LMO; rows 3–6). Each method is fixed by the LMO location and the uplink/downlink compressors. “MV”: majority vote; “EF21-P”: primal (model-side) error feedback; “exact”: the server applies no downlink compressor. That is not the same as a full-precision downlink: SignMuon’s server has nothing to compress because the object it distributes, the majority vote, is already ±1-valued, so its downlink is one bit per parameter all the same (Appendix A.14). The three methods that do broadcast a dense model are MuonUSign, EF21-SignMuon and EF21-MuonUSign.
Algorithm 8: Federated SignMuon / EF21-SignMuon (worker-side LMO) Input: initial model X0 ; clients N ; rounds T ; learning rate ηt ; momentum µ; uplink compressor C ↑ ∈ {sign, EF21} (Table 13) Output: global model XT (j)
(j)
1: M0 ← 0, d0 ← 0 for all j; d0 ← 0 2: broadcast X0 once; every client keeps a local copy, refreshed below from the downlink
message alone 3: for t = 1 to T do 4: for j = 1 to N in parallel do 5: 6:
(j) (j) Gt ← ∇fj (Xt−1 ; ξt ) (j) (j) (j) Mt ← µMt−1 + (1 − µ) Gt (j) (j) M̃t ← Mt (j) (j) Dt ← MuonLMO M̃t ↑
▷ client j, holding Xt−1
(j)
(j)
▷ or (1 − µ)Gt + µMt (Nesterov) 8: ▷ LMO on the client 9: if C = EF21 then ▷ EF21-SignMuon (j) (j) (j) (j) (j) 10: ∆t ← Dt − dt−1 ; αt ← mean(|∆t |) (j) (j) (j) (j) 11: dt ← dt−1 + αt sign(∆t ) (j) (j) 12: send sign(∆t ), αt 13: else ▷ SignMuon (j) (j) 14: send st ← sign(Dt ) 15: end if 16: end for on the server: 17: if C ↑ = EF21 then ▷ EF21-SignMuon: dt is dense, 32 bits down P (j) (j) 18: dt ← dt−1 + N1 j αt sign(∆t ) ▷ aggregate direction 19: Xt ← Xt−1 − ηt dt ; broadcast Xt 20: else ▷ SignMuon: the vote is ±1, 1 bit down P (j) 21: ŝt ← sign s ▷ majority vote j t 22: Xt ← Xt−1 − ηt ŝt ; broadcast ŝt ▷ clients apply the same step 23: end if 24: end for 7:
Algorithm 9: Federated MuonUSign / MuonSign / EF21-MuonUSign / EF21-MuonSign (server-side LMO) Input: initial model X0 ; clients N ; rounds T ; learning rate ηt ; momentum µ; compressors C ↑ ∈ {sign, EF21}, C ↓ ∈ {exact, sign, EF21-P} (Table 13) Output: global model XT (j)
(j)
1: M0 ← 0, g0 ← 0 for all j; g0 ← 0 2: broadcast X0 once; every client holds the broadcast model W0 ← X0 , refreshed below
from the downlink message alone (Wt = Xt unless C ↓ = EF21-P)
3: for t = 1 to T do 4: for j = 1 to N in parallel do
▷ client j, holding Wt−1 (j) (j) Gt ← ∇fj (Wt−1 ; ξt ) (j) (j) (j) 6: Mt ← µMt−1 + (1 − µ) Gt (j) (j) (j) (j) 7: M̃t ← Mt ▷ or (1 − µ)Gt + µMt (Nesterov) 8: if C ↑ = EF21 then ▷ EF21-MuonUSign / EF21-MuonSign (j) (j) (j) (j) (j) 9: ∆t ← M̃t − gt−1 ; αt ← mean(|∆t |) (j) (j) (j) (j) 10: gt ← gt−1 + αt sign(∆t ) (j) (j) 11: send sign(∆t ), αt 12: else ▷ MuonUSign / MuonSign (j) (j) 13: send st ← sign M̃t 14: end if 15: end for on the server: 16: if C ↑ = EF21 then P (j) (j) 17: gt ← gt−1 + N1 j αt sign(∆t ) ▷ reconstruct gradient 18: else P (j) ▷ majority vote 19: gt ← sign j st 20: end if 21: Dt ← MuonLMO(gt ) ▷ single LMO on the server 22: if C ↓ = sign then ▷ MuonSign: 1 bit/param down 23: Xt ← Xt−1 − ηt sign(Dt ); broadcast sign(Dt ) 24: Wt ← Wt−1 − ηt sign(Dt ) ▷ = Xt ; one model 25: else if C ↓ = EF21-P then ▷ EF21-MuonSign: 1 bit/param down 26: Xt ← Xt−1 − ηt Dt ▷ server model ↓ ↓ ↓ 27: ∆t ← Xt − Wt−1 ; αt ← mean(|∆t |) 28: Wt ← Wt−1 + αt↓ sign(∆↓t ); broadcast sign(∆↓t ), αt↓ ▷ clients apply the same refresh 29: else ▷ exact downlink: MuonUSign / EF21-MuonUSign 30: Xt ← Xt−1 − ηt Dt ; broadcast Xt ; Wt ← Xt 31: end if 32: end for 5: