SignMuon: Communication-Efficient Distributed Muon Optimization

# SignMuon: Communication-Efficient Distributed Muon Optimization
Source: [https://arxiv.org/html/2605.16311](https://arxiv.org/html/2605.16311)
theorem\]Lemma theorem\]Corollary theorem\]Proposition theorem\]Assumption theorem\]Definition theorem\]Example theorem\]Remark

Neel Mishra1,†Kushagara Trivedi2,†Pawan Kumar2 1Microsoft2IIIT Hyderabad †Equal contribution\.

###### Abstract

Distributed training of large neural networks is bottlenecked by full\-precision gradient communication and by coordinatewise optimizers that ignore the matrix structure of weight tensors\. We propose Sign\-Muon, a 1\-bit, matrix\-aware optimizer that combines majority\-vote sign aggregation from signSGD with the polar\-step framework of Muon\. Each worker forms a Muon\-style direction by taking the polar factor of its momentum via a Newton–Schulz iteration, transmits only the entrywise signs, and aggregates by majority vote; an optional local polar step further enforces orthogonality at no extra communication cost\.

Under spectral\-norm smoothness and bounded\-variance stochastic gradients, the spectral\-norm normalized sign step yields an𝒪​\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)nonconvex rate for anℓ1\\ell\_\{1\}\-based stationarity measure\. With unimodal symmetric noise, majority vote acrossMMworkers cuts the stochastic term by1/M1/\\sqrt\{M\}, matching signSGD\. In theα\\alpha\-β\\betamodel, distributed Sign\-Muon needs only one integer sum\-allreduce per iteration; all orthogonalization is local, giving a32×32\\timesbandwidth reduction over float32 \(4×4\\timesfor int8\)\.

Across 330 CIFAR\-10/ResNet\-50 configurations Sign\-Muon attains the best validation accuracy \(92\.15%\); its 4\-GPU majority\-vote variant reaches 92\.02% with 37% less training time at matched effective batch\. On nanoGPT, Sign\-Muon achieves lower perplexity and better anytime performance than other sign\-based baselines, with favorable weak\-scaling up to 16 GPUs\.

Keywords:distributed optimization; communication\-efficient training; sign methods; matrix\-structured updates; polar decomposition

## 1Introduction

The scale of the neural networks like large language models \(LLMs\) often runs into the limitations of distributed systems, when training large neural networks\. In synchronous data\-parallel training, numerous workers must constantly sync large amounts of data\. Gradients, updates, or the state of the optimiser, using collective communication, and this is expensive in terms of bandwidth and latency, eating away at the time available per iteration\. Two fairly recent approaches try to combat different aspects of this bottleneck\.

##### Why better optimizers matter across applications\.

Stochastic optimization sits at the heart of nearly every modern learning system: transformer\-based language and sequence models\[[35](https://arxiv.org/html/2605.16311#bib.bib35)\], structured tokenization and curriculum design for mathematics and science problem solving\[[20](https://arxiv.org/html/2605.16311#bib.bib31)\], dynamic learning\-rate schedules for plain gradient descent\[[25](https://arxiv.org/html/2605.16311#bib.bib29)\], second\-order updates for adversarial min–max problems in generative models\[[26](https://arxiv.org/html/2605.16311#bib.bib30),[5](https://arxiv.org/html/2605.16311#bib.bib34)\], light\-weight deep architectures for extreme multi\-label classification\[[24](https://arxiv.org/html/2605.16311#bib.bib33)\], and stable training in multi\-agent reinforcement learning via spectral normalization\[[22](https://arxiv.org/html/2605.16311#bib.bib32)\]\. In each of these settings the optimizer is invoked millions of times, so any improvement in its per\-step communication or its convergence behavior translates directly into shorter wall\-clock training and lower energy use\. This makes communication\-efficient, geometry\-aware optimizers like Sign\-Muon broadly relevant beyond a single benchmark\.

##### Sign\-based communication\.

Communication between workers is often a major bottleneck, and methods like signSGD can help, when training deep neural networks\. This is because signSGD replaces each gradient entry with its sign, and aggregates the signs of all workers, which basically boils down to 1\-bit communication per parameter\. As a result, we get convergence guarantees in nonconvex settings under very weak noise assumptions, thanks to\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\. The majority vote used in signSGD also makes it more robust to random noise and outliers, because it can effectively cancel out the outliers with the votes from the other workers\.

##### Matrix\-aware update geometry\.

Many parameters such as MLP weights and attention projections are in the form of matrices, but standard optimizers view them as one\-dimensional vectors, when training deep networks\. Muon fixes this discrepancy by orthogonalizing momentum matrices via the polar decomposition, which is then approximated using the Newton\-Schulz algorithm, and leads to update directions that are more favorable in the early stages of optimisation\. However, distributed variants of Muon carry over the communication cost associated with full\-precision synchronisation\.

##### Our goal and approach\.

We seek an optimizer that \(i\) retains Muon’s matrix\-aware geometry and its spectral\-norm analysis framework, while \(ii\) achievingsignSGD\-style extreme communication compression\. We proposeSign\-Muon: each worker computes a Muon\-style direction locally and transmits only its entrywise signs\. Workers obtain the aggregated direction by majority vote and apply a signed update whose spectral norm is explicitly controlled\. Orthogonalization \(via SVD or Newton\-Schulz\) can be applied either to the local momentum \(before sign transmission\) or to the aggregated sign matrix \(after majority vote\); in both cases, it is computed locally and does not increase communication\.

##### Theory of Sign\-Muon\.

Sign methods measure progress through anℓ1\\ell\_\{1\}\-aligned proxy that reflects coordinatewise sign reliability\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\], while Muon’s descent lemma is naturally expressed under spectral\-norm smoothness\[[11](https://arxiv.org/html/2605.16311#bib.bib20)\]\. By normalizing the signed direction to have spectral norm at most one, we obtain a spectral descent inequality whose leading term is anℓ1\\ell\_\{1\}quantity\. This yields us an𝒪​\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)nonconvex convergence rate for an averagedℓ1\\ell\_\{1\}stationarity measure\. Under unimodal symmetric noise, the majority vote approach improves the stochastic term by1/M1/\\sqrt\{M\}withMMworkers, matching the classicalsignSGDbenefit\. Detailed theory is presented in appendix\.

##### Empirical evaluation of Sign\-Muon\.

We evaluate Sign\-Muon on two workloads: CIFAR\-10\[[14](https://arxiv.org/html/2605.16311#bib.bib1)\]image classification and nanoGPT language modeling\. For CIFAR\-10/ResNet\-50\[[7](https://arxiv.org/html/2605.16311#bib.bib4)\], a sweep over 330 configurations shows that SignMuon achieves the best validation accuracy \(92\.15%\), and the 4\-GPU majority\-vote variant reaches 92\.02% while reducing training time by 37% in the matched\-batch setting\. For nanoGPT, Sign\-Muon achieves lower perplexity and better anytime performance than other sign\-based baselines, and we report weak\-scaling behavior up to 16 GPUs\.

##### Our Contributions\.

- •Algorithm\.We introduceSign\-Muon, a 1\-bit, matrix\-aware optimizer that embeds majority\-vote sign aggregation inside Muon’s polar\-step framework\.
- •Convergence and communication analysis\.Under spectral\-norm smoothness and bounded\-variance stochastic gradients, we prove𝒪​\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)convergence in anℓ1\\ell\_\{1\}\-based stationarity measure and show a1/M1/\\sqrt\{M\}improvement from majority vote under unimodal symmetric noise\. We also give anα\\alpha–β\\betacommunication model showing that distributed Sign\-Muon requires a single sign allreduce per iteration\.
- •Experiments\.We report results on vision and language workloads, including hyperparameter sweeps, time/memory measurements, and distributed scaling\.

## 2Related Work

Sign\-based optimization and robust aggregation\.Sign methods cut through the noise by sending just the sign of a stochastic gradient, when communicating and applying updates\. Well\-known signSGD algorithm from\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]provides non\-convex guarantees and proposed the idea of distributed majority voting which gives us a more reliable sign\. Building off that work, subsequent studies have looked at the robustness and ability of majority voting to withstand errors in collaborative and adversarial settings\. One major drawback of these methods is that they can be very “coordinate\-based”, and don’t take into account the matrix structure that exists in neural network parameters, but Sign\-Muon gets around this issue by using matrix\-aware directions that are generated from Muon\-style orthogonalization\.

Algorithm 1Sign\-Muon\(single worker\)1:Input:stepsizes

\{ηt\}\\\{\\eta\_\{t\}\\\}, momentum

β∈\[0,1\)\\beta\\in\[0,1\), weight decay

λ≥0\\lambda\\geq 0, NS iterations

KK, stability constant

ε\>0\\varepsilon\>0, scaling

scale∈\{spectral,fro\}\\textsc\{scale\}\\in\\\{\\textsc\{spectral\},\\textsc\{fro\}\\\}, power iters

PP\.

2:Initialize momentum

M0←0M\_\{0\}\\leftarrow 0\.

3:for

t=0,1,…,T−1t=0,1,\\ldots,T\-1do

4:Draw mini\-batch; compute stochastic gradient

GtG\_\{t\}at

WtW\_\{t\}\.

5:

G~t←Gt\+λ​Wt\\widetilde\{G\}\_\{t\}\\leftarrow G\_\{t\}\+\\lambda W\_\{t\}\.

6:

Mt\+1←β​Mt\+\(1−β\)​G~tM\_\{t\+1\}\\leftarrow\\beta M\_\{t\}\+\(1\-\\beta\)\\widetilde\{G\}\_\{t\}\.

7:

Ut←PolarNS​\(Mt\+1;K,ε,scale,P\)U\_\{t\}\\leftarrow\\mathrm\{PolarNS\}\(M\_\{t\+1\};K,\\varepsilon,\\textsc\{scale\},P\)
8:

Dt←sign⁡\(Ut\)D\_\{t\}\\leftarrow\\operatorname\{sign\}\(U\_\{t\}\)\(entrywise\)

9:

Wt\+1←Wt−ηt​DtW\_\{t\+1\}\\leftarrow W\_\{t\}\-\\eta\_\{t\}D\_\{t\}\.

10:endfor

Algorithm 2Sign\-Muon\(distributed with all\-reduce\)1:Input:Learning rates

\{ηt\}\\\{\\eta\_\{t\}\\\},

MMworkers, momentum

β∈\[0,1\)\\beta\\in\[0,1\), weight decay

λ≥0\\lambda\\geq 0, NS iterations

KK, tolerance

ε\>0\\varepsilon\>0, scale

∈\{spectral,fro\}\\in\\\{\\textsc\{spectral\},\\textsc\{fro\}\\\}, power iterations

PP
2:Initialize:

M0\(m\)←0M\_\{0\}^\{\(m\)\}\\leftarrow 0for all workers

m∈\{1,…,M\}m\\in\\\{1,\\ldots,M\\\}
3:for

t=0,1,…,T−1t=0,1,\\ldots,T\-1do

4:Each workermmindependently:

5:Compute local gradient

Gt\(m\)G\_\{t\}^\{\(m\)\}at current parameters

WtW\_\{t\}
6:Apply weight decay:

G~t\(m\)←Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\leftarrow G\_\{t\}^\{\(m\)\}\+\\lambda W\_\{t\}
7:Update local momentum:

Mt\+1\(m\)←β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\leftarrow\\beta M\_\{t\}^\{\(m\)\}\+\(1\-\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}
8:Compute polar decomposition:

Ut\(m\)←PolarNS​\(Mt\+1\(m\);K,ε,scale,P\)U\_\{t\}^\{\(m\)\}\\leftarrow\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\};K,\\varepsilon,\\textsc\{scale\},P\)
9:Extract local sign:

St\(m\)←sign⁡\(Ut\(m\)\)∈\{−1,\+1\}dS\_\{t\}^\{\(m\)\}\\leftarrow\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)\\in\\\{\-1,\+1\\\}^\{d\}
10:All\-reduce \(collective\):

11:All workers participate in sum\-reduce:

12:

sum​\_​signs←∑m=1MSt\(m\)\\mathrm\{sum\\\_signs\}\\leftarrow\\sum\_\{m=1\}^\{M\}S\_\{t\}^\{\(m\)\}\(all\-reduce with SUM, int8\)

13:All workers compute majority vote locally:

14:

S¯t←sign⁡\(sum​\_​signs\)∈\{−1,\+1\}d\\bar\{S\}\_\{t\}\\leftarrow\\operatorname\{sign\}\(\\mathrm\{sum\\\_signs\}\)\\in\\\{\-1,\+1\\\}^\{d\}\(ties default to \+1\)

15:Each workermmindependently:

16:Update parameters:

Wt\+1←Wt−ηt​S¯tW\_\{t\+1\}\\leftarrow W\_\{t\}\-\\eta\_\{t\}\\bar\{S\}\_\{t\}
17:endfor

18:Communication cost:

ddbytes per step \(int8 encoding,

dd= dimension\)

Worker11G~t\(m\)=Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\\!=\\\!G\_\{t\}^\{\(m\)\}\\\!\+\\\!\\lambda W\_\{t\}Mt\+1\(m\)=β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\\!=\\\!\\beta M\_\{t\}^\{\(m\)\}\\\!\+\\\!\(1\{\-\}\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}Ut\(m\)=PolarNS​\(Mt\+1\(m\)\)U\_\{t\}^\{\(m\)\}=\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\}\)St\(m\)=sign⁡\(Ut\(m\)\)∈\{±1\}dS\_\{t\}^\{\(m\)\}=\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)\\in\\\{\\pm 1\\\}^\{d\}WorkerMMG~t\(m\)=Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\\!=\\\!G\_\{t\}^\{\(m\)\}\\\!\+\\\!\\lambda W\_\{t\}Mt\+1\(m\)=β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\\!=\\\!\\beta M\_\{t\}^\{\(m\)\}\\\!\+\\\!\(1\{\-\}\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}Ut\(m\)=PolarNS​\(Mt\+1\(m\)\)U\_\{t\}^\{\(m\)\}=\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\}\)St\(m\)=sign⁡\(Ut\(m\)\)∈\{±1\}dS\_\{t\}^\{\(m\)\}=\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)\\in\\\{\\pm 1\\\}^\{d\}⋯\\cdots⋯\\cdots⋯\\cdots⋯\\cdots⋯\\cdotsAllReduce\(SUM,int8\):∑m=1MSt\(m\)\\displaystyle\\sum\_\{m=1\}^\{M\}S\_\{t\}^\{\(m\)\}S¯t=sign⁡\(∑m=1MSt\(m\)\)∈\{±1\}d\\bar\{S\}\_\{t\}=\\operatorname\{sign\}\\\!\\left\(\\sum\_\{m=1\}^\{M\}S\_\{t\}^\{\(m\)\}\\right\)\\in\\\{\\pm 1\\\}^\{d\}Each worker \(locally\):Wt\+1=Wt−ηt​S¯tW\_\{t\+1\}=W\_\{t\}\-\\eta\_\{t\}\\,\\bar\{S\}\_\{t\}■\\blacksquare1 collective / iter■\\blacksquarepayloads8=ds\_\{8\}=dBFigure 1:Schematic of distributedSign\-MuonwithSUMAllReduce\(Algorithm[2](https://arxiv.org/html/2605.16311#alg2)\)\. Each worker independently computes its momentumMt\+1\(m\)M\_\{t\+1\}^\{\(m\)\}, the Newton–Schulz polar directionUt\(m\)U\_\{t\}^\{\(m\)\}, and the entrywise signSt\(m\)∈\{−1,\+1\}dS\_\{t\}^\{\(m\)\}\\in\\\{\-1,\+1\\\}^\{d\}\. A single integerSUMAllReduceaggregates the sign buffers across workers; each worker then thresholds locally withsign⁡\(⋅\)\\operatorname\{sign\}\(\\cdot\)to recover the majority voteS¯t\\bar\{S\}\_\{t\}, and applies the parameter update with no further communication\. Spectral normalization and Newton–Schulz iterations are local; only oneint8collective per iteration crosses the network\.Communication\-efficient distributed training\.The usual techniques involve quantisation, sparsification and low\-dimensional representations, or sketches, when compressing communication in machine learning\. QSGD\[[1](https://arxiv.org/html/2605.16311#bib.bib9)\]and TernGrad\[[37](https://arxiv.org/html/2605.16311#bib.bib17)\]are two examples of methods that quantify gradients with a fine\-tuned balance between bias and variance\. Deep Gradient Compression\[[18](https://arxiv.org/html/2605.16311#bib.bib11)\]uses simple heuristics to cut down the size of the updates, and PowerSGD\[[36](https://arxiv.org/html/2605.16311#bib.bib13)\]zeroes in on the most important low\-rank features of the matrix, using its structure\. To combat the negative side effects of overly aggressive compression, error\-feedback mechanisms can be employed to restore the typical convergence rate of SGD, as demonstrated in Stich’s research\[[32](https://arxiv.org/html/2605.16311#bib.bib12)\]\. These methods commonly compress either the raw gradients or the low\-rank factorisation of them\. Sign\-Muon goes a step further, sending communications using extreme 1\-bit signals, and introduces a form of matrix normalisation, called polar normalisation, before sending the sign\.

![Refer to caption](https://arxiv.org/html/2605.16311v1/x1.png)\(a\)ResNet\-18 eval
![Refer to caption](https://arxiv.org/html/2605.16311v1/x2.png)\(b\)ResNet\-18 train
![Refer to caption](https://arxiv.org/html/2605.16311v1/x3.png)\(c\)ResNet\-34 eval
![Refer to caption](https://arxiv.org/html/2605.16311v1/x4.png)\(d\)ResNet\-34 train
![Refer to caption](https://arxiv.org/html/2605.16311v1/x5.png)\(e\)ResNet\-50 eval
![Refer to caption](https://arxiv.org/html/2605.16311v1/x6.png)\(f\)ResNet\-50 train
![Refer to caption](https://arxiv.org/html/2605.16311v1/x7.png)\(g\)ResNet\-101 eval
![Refer to caption](https://arxiv.org/html/2605.16311v1/x8.png)\(h\)ResNet\-101 train

Figure 2:Single\-worker CIFAR\-10 accuracy vs\. epochs\. Top: ResNet\-18/34; Bottom: ResNet\-50/101\. For each architecture, evaluation \(left\) and training \(right\)\.Matrix\-/geometry\-aware optimizers\.Concerning the way we update parameters in our neural networks, structure\-aware optimizers likeKK\-FAC\[[21](https://arxiv.org/html/2605.16311#bib.bib15)\]and Shampoo\[[6](https://arxiv.org/html/2605.16311#bib.bib14)\]leverages the shape of the parameters\. Moreover, they use curvature\-inspired preconditioners\. Meanwhile, Muon\[[11](https://arxiv.org/html/2605.16311#bib.bib20),[31](https://arxiv.org/html/2605.16311#bib.bib21)\]uses polar decomposition to orthogonalise momentum directions in a way that’s inspired by classical matrix\-iteration theory\[[8](https://arxiv.org/html/2605.16311#bib.bib5),[3](https://arxiv.org/html/2605.16311#bib.bib6)\]\. Coming from a different direction are the momentum/EMA methods\[[29](https://arxiv.org/html/2605.16311#bib.bib7),[33](https://arxiv.org/html/2605.16311#bib.bib8)\]and decoupled weight decay\[[19](https://arxiv.org/html/2605.16311#bib.bib16)\], still very much part of the mainstay of contemporary training\. Our proposed method, Sign\-Muon, which brings together the streamlined communication of sign aggregation with the matrix\-aware insights of Muon is another more recent addition\.

Recent sign\-based designs\.Sign updates also appear in non\-communication settings \(e\.g\., Lion\[[4](https://arxiv.org/html/2605.16311#bib.bib23)\]\), and recent work strengthens Byzantine\-robust sign aggregation\[[23](https://arxiv.org/html/2605.16311#bib.bib22)\]\. Overall, prior work tends to separate \(i\) sign\-based methods emphasizing extreme compression and robustness and \(ii\) matrix\-aware methods emphasizing structured directions under full precision\. Sign\-Muon bridges these lines by embedding majority\-vote sign aggregation within Muon’s polar\-step framework\.

## 3Proposed Method and Algorithms

We describeSign\-Muonand its distributed majority\-vote implementation \(Alg\.[1](https://arxiv.org/html/2605.16311#alg1),[2](https://arxiv.org/html/2605.16311#alg2),[3](https://arxiv.org/html/2605.16311#alg3)\)\. Throughout, a matrix\-shaped parameter block isW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}withd=m​nd=mnentries\. Stochastic gradients on a mini\-batch at iterationttare denotedGtG\_\{t\}\(orGt\(p\)G\_\{t\}^\{\(p\)\}on workerpp\)\. We usesign⁡\(⋅\)\\operatorname\{sign\}\(\\cdot\)entrywise, the spectral norm∥⋅∥op\\\|\\cdot\\\|\_\{\\mathrm\{op\}\}, and the Frobenius norm∥⋅∥F\\\|\\cdot\\\|\_\{\\mathrm\{F\}\}\. For matrixM=U​Σ​V⊤M=U\\Sigma V^\{\\top\}\(thin SVD\), we writepolar​\(M\)=U​V⊤\\mathrm\{polar\}\(M\)=UV^\{\\top\}for its polar factor\.

### 3\.1FromsignSGDand Muon toSign\-Muon

Sign\-Muon combines \(i\) majority\-vote sign aggregation fromsignSGD\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]with \(ii\) Muon’s matrix\-aware polar update directions\[[11](https://arxiv.org/html/2605.16311#bib.bib20),[31](https://arxiv.org/html/2605.16311#bib.bib21)\]\. We briefly recall both ingredients and then describe their integration\.

##### Sign aggregation \(majority vote\)\.

Given local sign matricesSt\(p\)∈\{−1,\+1\}m×nS\_\{t\}^\{\(p\)\}\\in\\\{\-1,\+1\\\}^\{m\\times n\}, the distributed aggregate is computed entrywise as follows

S¯t=sign⁡\(∑p=1MSt\(p\)\)\\bar\{S\}\_\{t\}\\;=\\;\\operatorname\{sign\}\\\!\\Big\(\\sum\_\{p=1\}^\{M\}S\_\{t\}^\{\(p\)\}\\Big\)which can be implemented by an integerSUMreduction followed by local thresholding\.

##### Polar directions\.

When muon updates its momentum matrix, it uses the polar factorUt=polar​\(Mt\+1\)U\_\{t\}=\\mathrm\{polar\}\(M\_\{t\+1\}\)which can be calculated either by Singular Value Decomposition \(SVD\) or a Newton\-Schulz \(NS\) iteration \(Alg\.[4](https://arxiv.org/html/2605.16311#alg4)\), and this process gives it a controlled spectrum of the update direction that is in sync with spectral\-norm regularisation\.

##### Sign\-Muon update\.

Each worker computes a local polar directionUt\(p\)U\_\{t\}^\{\(p\)\}from its momentum, transmitsSt\(p\)=sign⁡\(Ut\(p\)\)S\_\{t\}^\{\(p\)\}=\\operatorname\{sign\}\(U\_\{t\}^\{\(p\)\}\), aggregatesS¯t\\bar\{S\}\_\{t\}by majority vote, and updates withS¯t\\bar\{S\}\_\{t\}\(equivalentlyS¯t/m​n\\bar\{S\}\_\{t\}/\\sqrt\{mn\}after rescaling the stepsize\)\. Optionally, each worker applies a local polar steppolar​\(S¯t\)\\mathrm\{polar\}\(\\bar\{S\}\_\{t\}\)after aggregation; sinceS¯t\\bar\{S\}\_\{t\}is already shared, this does not change communication\.

![Refer to caption](https://arxiv.org/html/2605.16311v1/x9.png)Figure 3:Weak scaling comparison of All\-Gather and All\-Reduce for CIFAR\-10 with ResNet\-50\.

## 4Convergence and Communication Analysis

We summarize the main communication and convergence properties of Sign\-Muon; detailed derivations appear in Appendices[B](https://arxiv.org/html/2605.16311#A2)–[C](https://arxiv.org/html/2605.16311#A3)\.

##### Update and notation\.

For a matrix blockW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}withd=m​nd=mn, letgt=∇f​\(Wt\)g\_\{t\}=\\nabla f\(W\_\{t\}\)\. In the distributed memory setting withMMworkers, each worker forms a local sign matrixSt\(p\)∈\{−1,\+1\}m×nS\_\{t\}^\{\(p\)\}\\in\\\{\-1,\+1\\\}^\{m\\times n\}and workers compute the majority vote

S¯t,i​j=sign⁡\(∑p=1MSt,i​j\(p\)\),S¯t=\(S¯t,i​j\)i​j\.\\bar\{S\}\_\{t,ij\}\\;=\\;\\operatorname\{sign\}\\\!\\Big\(\\sum\_\{p=1\}^\{M\}S\_\{t,ij\}^\{\(p\)\}\\Big\),\\qquad\\bar\{S\}\_\{t\}=\(\\bar\{S\}\_\{t,ij\}\)\_\{ij\}\.\(1\)We analyze the normalized update

Dt=S¯tm​n,Wt\+1=Wt−ηt​Dt,D\_\{t\}\\;=\\;\\frac\{\\bar\{S\}\_\{t\}\}\{\\sqrt\{mn\}\},\\qquad W\_\{t\+1\}=W\_\{t\}\-\\eta\_\{t\}D\_\{t\},\(2\)noting that‖Dt‖op≤‖Dt‖F=1\\\|D\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq\\\|D\_\{t\}\\\|\_\{\\mathrm\{F\}\}=1\. Updating withS¯t\\bar\{S\}\_\{t\}directly is equivalent after absorbingm​n\\sqrt\{mn\}intoηt\\eta\_\{t\}\.

##### Assumptions\.

We need some basic assumptions \(i\)f​\(W\)≥f∗f\(W\)\\geq f^\{\\ast\}is lower bounded, \(ii\) spectral\-norm smoothness‖∇f​\(W\)−∇f​\(W′\)‖∗≤L∗​‖W−W′‖op\\\|\\nabla f\(W\)\-\\nabla f\(W^\{\\prime\}\)\\\|\_\{\\ast\}\\leq L\_\{\\ast\}\\\|W\-W^\{\\prime\}\\\|\_\{\\mathrm\{op\}\}, and \(iii\) unbiased stochastic gradients with coordinatewise varianceVar​\(G~t,i​j∣Wt\)≤σi​j2/nb\\mathrm\{Var\}\(\\widetilde\{G\}\_\{t,ij\}\\mid W\_\{t\}\)\\leq\\sigma\_\{ij\}^\{2\}/n\_\{b\}\. For the majority\-vote improvement we additionally assume unimodal symmetric per\-coordinate noise, following similar assumptions insignSGD\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\.

##### Stationarity metric\.

We measure stationarity via

𝒢T:=1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]\.\\mathcal\{G\}\_\{T\}\\;:=\\;\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\\|g\_\{t\}\\\|\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\.\(3\)
Theorem[4](https://arxiv.org/html/2605.16311#S4.SS0.SSS0.Px3)below states the cleanest specialization obtained for the*gradient\-sign*instantiation \(where the communicated sign comes directly from an unbiased stochastic gradient\)\. The generic bound for an arbitrary sign oracle \(including Muon\-direction\-sign\) is given in Theorem[C\.5\.1](https://arxiv.org/html/2605.16311#A3.SS5.SSS1)in Appendix[C](https://arxiv.org/html/2605.16311#A3)\.

\{theorem\}

\[Sign\-Muon convergence \(gradient\-sign instantiation; single worker and distributed\)\] Under the assumptions above and constant stepsizeηt≡η\\eta\_\{t\}\\equiv\\eta, we have the following

𝒢T\\displaystyle\\mathcal\{G\}\_\{T\}≤f​\(W0\)−f∗η​T\+L∗2​η\\displaystyle\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\\;\+\\;\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+2​‖σ‖1m​n×\{1nb,single worker,1M​nb,M\-worker majority vote,\\displaystyle\\quad\\;\+\\;\\frac\{2\\\|\\sigma\\\|\_\{1\}\}\{\\sqrt\{mn\}\}\\times\\begin\{cases\}\\frac\{1\}\{\\sqrt\{n\_\{b\}\}\},&\\text\{single worker\},\\\\\[3\.00003pt\] \\frac\{1\}\{\\sqrt\{Mn\_\{b\}\}\},&\\text\{$M$\-worker majority vote\},\\end\{cases\}\(4\)where‖σ‖1=∑i,jσi​j\\\|\\sigma\\\|\_\{1\}=\\sum\_\{i,j\}\\sigma\_\{ij\}\. Choosingη=2​\(f​\(W0\)−f∗\)L∗​T\\eta=\\sqrt\{\\tfrac\{2\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{L\_\{\\ast\}T\}\}yields an𝒪​\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)optimization term and a noise floor that improves as1/M​nb1/\\sqrt\{Mn\_\{b\}\}under majority vote\. For detailed proof for single worker, see Theorem[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2), and for multiple worker, see Theorem[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)\.

##### Distributed Communication Complexity\.

Withb∈\{1,8\}b\\in\\\{1,8\\\}bits per sign entry \(bit\-packed vs\. int8\), the sign payload size iss=\(b​d\)/8s=\(bd\)/8bytes\. Majority vote uses one integerSUMallreduce per iteration\. We adopt the same classicalα\\alpha\-β\\beta\(latency\-bandwidth\) model that has long been used to analyze communication of distributed numerical kernels in HPC, e\.g\., communication\-optimal least\-squares solvers\[[16](https://arxiv.org/html/2605.16311#bib.bib36),[17](https://arxiv.org/html/2605.16311#bib.bib37)\]and parallel implicit particle\-in\-cell solvers\[[15](https://arxiv.org/html/2605.16311#bib.bib38)\]\. Concretely,T​\(s\)≈α\+β​sT\(s\)\\approx\\alpha\+\\beta sforssbytes, whereα\\alphais latency andβ\\betais inverse bandwidth\. LetR​\(M\)R\(M\)be the number of allreduce rounds \(ring:2​\(M−1\)2\(M\-1\); tree:2​⌈log2⁡M⌉2\\lceil\\log\_\{2\}M\\rceil\)\. Then

Titer≈α​R​\(M\)\+2​\(1−1M\)​s​β\.T\_\{\\mathrm\{iter\}\}\\approx\\alpha R\(M\)\+2\\Bigl\(1\-\\frac\{1\}\{M\}\\Bigr\)s\\beta\.
In Appendix[B](https://arxiv.org/html/2605.16311#A2)we provide a detailed accounting and comparisons to full\-precision allreduce\.

## 5Numerical Experiments

We testedSign\-Muonfor two different tasks: CIFAR\-10 image classification with CIFAR\-style ResNets and nanoGPT language modeling\. We look for signs of how well Sign\-Muon optimises, its final results, and practical costs \(iteration time, persistent memory, and scaling\)\.

### 5\.1Common experimental setup

##### Optimizers\.

We compareSign\-MuonagainstMuon,signSGD, SGD \(Nesterov momentum\)\[[27](https://arxiv.org/html/2605.16311#bib.bib2)\], Adam\[[13](https://arxiv.org/html/2605.16311#bib.bib3)\], and AdamW\[[19](https://arxiv.org/html/2605.16311#bib.bib16)\]\. Muon/Sign\-Muon maintain a momentum buffer \(β=0\.9\\beta=0\.9\) and compute a polar\-factor direction using Newton\-Schulz iterations; the number of NS iterations and the scaling scheme spectral or Frobenius are specified per experiment\. For distributed sign methods, we have implemented majority vote by packing signs into anint8buffer, performing an integerSUMallreduce, and applyingsign⁡\(⋅\)\\operatorname\{sign\}\(\\cdot\)locally\.

SignSGDSGDMuonSign\-MuonAdamAdamW05050100100Persistent Memory \(MiB\)Figure 4:Persistent memory usage comparison for CIFAR\-10 \(ResNet\-18\)\. Excludes transient orthogonalization buffers\. Here persistent memory refers to the memory across iteration; Adam/AdamW have higher persistent memory because they maintain two moment vectors\. Sign\-Muon maintains the same persistent state size as SGD \(one momentum\-like buffer\)\.![Refer to caption](https://arxiv.org/html/2605.16311v1/x10.png)Figure 5:Weak scaling comparison of All\-Gather and All\-Reduce for nanoGPT\.
##### Metrics\.

We report accuracy \(CIFAR\-10\) and perplexity \(nanoGPT\), along with wall\-clock timing\. For CIFAR\-10 we have additionally reported persistent optimizer memory excluding persistent orthogonalization workspaces in Figure[4](https://arxiv.org/html/2605.16311#S5.F4)\.

### 5\.2CIFAR\-10

CIFAR\-10 consists of 50,000 training images and 10,000 test images over 10 classes, with32×3232\\times 32RGB inputs\. We train with standard random flipping and cropping \(with 4\-pixel padding\), and with input normalization by channel\-wise mean and standard deviation \(empirically computed over the training data\)\.

#### 5\.2\.1Single\-worker results across ResNet depths

Models\.We use torchvision ResNet\-18/34/50/101 adapted for CIFAR inputs by replacing the initial7×77\\times 7stride\-2 convolution with a3×33\\times 3stride\-1 convolution, removing the initial max\-pooling layer, and setting the classifier head to 10 outputs\.

Training and tuning\.All single\-worker experiments train for 30 epochs with a constant learning rate\. For each optimizer, we sweep learning rates over\{10−1,5×10−2,10−2,2×10−3,10−3,5×10−4,10−4\}\\\{10^\{\-1\},\\,5\\\!\\times\\\!10^\{\-2\},\\,10^\{\-2\},\\,2\\\!\\times\\\!10^\{\-3\},\\,10^\{\-3\},\\,5\\\!\\times\\\!10^\{\-4\},\\,10^\{\-4\}\\\}\. Muon uses 7 Newton–Schulz iterations and Sign\-Muon uses one iteration; both use momentumβ=0\.9\\beta=0\.9\. We use Frobenius scaling for Muon and spectral scaling for Sign\-Muon\. SGD uses Nesterov momentum \(μ=0\.9\\mu=0\.9\), and Adam/AdamW use default momentum parameters\.

##### Findings\.

The best learning rates for each method and architecture is summarized in Figure[2](https://arxiv.org/html/2605.16311#S2.F2)\. Muon starts to show strong early\-epoch progress, and then maintains its steady trajectory, which is impressive\. Sign\-Muon, on the other hand, initially follows Muon, but exhibits a lot of oscillations, something that we believe is consistent with the additional stochasticity that comes with entrywise sign quantization\. Adam and AdamW steadily get better, but tend to be a bit slow in the initial stages\.

#### 5\.2\.2ResNet\-18 cost summary

For completeness we also report a longer ResNet\-18 run that summarizes final accuracy, iteration time, and persistent optimizer memory\. To keep the main paper focused on the ResNet\-50 sweep and scaling behavior, we place the full table and memory breakdown in Appendix[A](https://arxiv.org/html/2605.16311#A1)\(Table[2](https://arxiv.org/html/2605.16311#A1.T2), Figure[9](https://arxiv.org/html/2605.16311#A1.F9)\)\.

#### 5\.2\.3Results for ResNet\-50: hyperparameter sweep and distributed setting

We perform a larger CIFAR\-10 study using ResNet\-50 to examine tuning and distributed behavior\. All experiments use NVIDIA RTX 4090 GPUs \(24GB VRAM\) and PyTorch with NCCL for distributed training\.

##### Setup\.

We train for 30 epochs with a cosine learning\-rate schedule \(no warmup\) and global gradient clipping at norm 1\.0\. For Muon/SignMuon we usens\_scale=spectralwithpower\_iters=2, and momentumβ=0\.9\\beta=0\.9\. Distributed experiments usetorchrunwithDistributedSampler; the specifiedbatch\_sizeis per GPU\.

Table 1:Top\-10 of 330 CIFAR\-10/ResNet\-50 configurations tested, ranked by validation accuracy\.
##### Findings\.

Table[1](https://arxiv.org/html/2605.16311#S5.T1)above summarizes the top\-10 configurations by validation accuracy\. SignMuon variants occupy the top\-3 positions with consistent hyperparameters \(LR=10−310^\{\-3\}, NS=1=1, WD=0\.0=0\.0\)\. In the matched\-effective\-batch setting \(single GPU with BS=512=512vs\. 4 GPUs with BS=128=128/GPU\), the distributed SignMuon configuration preserves accuracy \(92\.02% vs\. 92\.15%\) while reducing training time by 37% due to parallelism and reduced communication volume\.

#### 5\.2\.4Scaling behavior \(ResNet\-50\)

We next examine distributed weak\-scaling behavior of ResNet\-50 on CIFAR\-10 across 1–16 GPUs, as shown in Figure[3](https://arxiv.org/html/2605.16311#S3.F3)\. In this setting, the per\-GPU workload is held fixed and end\-to\-end training time is reported as the number of GPUs increases\. Under All\-Gather communication, SignMuon consistently incurs lower training\-time growth than other signed optimizers across the entire scaling range, with training\-time overheads of\+11\.3%\+11\.3\\%,\+25\.7%\+25\.7\\%, and\+77\.8%\+77\.8\\%at 4, 8, and 16 GPUs, respectively, compared to\+52\+52–62%62\\%at 8 GPUs and\+150\+150–163%163\\%at 16 GPUs for SignAdam and SignSGD\. A similar trend holds for All\-Reduce communication, where SignMuon exhibits smaller growth factors \(\+7\.1%\+7\.1\\%at 4 GPUs and\+60\.2%\+60\.2\\%at 16 GPUs\) relative to competing methods, which exceed\+36%\+36\\%at 8 GPUs and\+117%\+117\\%at 16 GPUs\. Overall, these findings show that All\-Gather is still competitive while SignMuon maintains better weak\-scaling behaviour across the entire GPU range as compared to other signed variants\.

Algorithm 3Sign\-Muon\(distributed with 1\-bit communication with All Gather\)1:Input:Learning rates

\{ηt\}\\\{\\eta\_\{t\}\\\},

MMworkers, momentum

β∈\[0,1\)\\beta\\in\[0,1\), weight decay

λ≥0\\lambda\\geq 0, NS iterations

KK, tolerance

ε\>0\\varepsilon\>0, scale

∈\{spectral,fro\}\\in\\\{\\textsc\{spectral\},\\textsc\{fro\}\\\}, power iterations

PP
2:Initialize:

M0\(m\)←0M\_\{0\}^\{\(m\)\}\\leftarrow 0for all workers

m∈\{1,…,M\}m\\in\\\{1,\\ldots,M\\\}
3:for

t=0,1,…,T−1t=0,1,\\ldots,T\-1do

4:Each workermmindependently:

5:Compute local gradient

Gt\(m\)G\_\{t\}^\{\(m\)\}for parameters

WtW\_\{t\}
6:Apply weight decay:

G~t\(m\)←Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\leftarrow G\_\{t\}^\{\(m\)\}\+\\lambda W\_\{t\}
7:Update local moment:

Mt\+1\(m\)←β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\leftarrow\\beta M\_\{t\}^\{\(m\)\}\+\(1\-\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}
8:Compute polar decomposition:

Ut\(m\)←PolarNS​\(Mt\+1\(m\);K,ε,scale,P\)U\_\{t\}^\{\(m\)\}\\leftarrow\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\};K,\\varepsilon,\\textsc\{scale\},P\)
9:Extract local sign:

St\(m\)←sign⁡\(Ut\(m\)\)∈\{−1,\+1\}dS\_\{t\}^\{\(m\)\}\\leftarrow\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)\\in\\\{\-1,\+1\\\}^\{d\}
10:Pack signs to bits:

Bt\(m\)←PackBits​\(St\(m\)\)B\_\{t\}^\{\(m\)\}\\leftarrow\\mathrm\{PackBits\}\(S\_\{t\}^\{\(m\)\}\)\(8 signs per byte\)

11:All\-gather \(collective\):

12:All workers participate in gathering packed bits:

13:

\{Bt\(1\),Bt\(2\),…,Bt\(M\)\}←all​\_​gather​\(Bt\(m\)\)\\\{B\_\{t\}^\{\(1\)\},B\_\{t\}^\{\(2\)\},\\ldots,B\_\{t\}^\{\(M\)\}\\\}\\leftarrow\\mathrm\{all\\\_gather\}\(B\_\{t\}^\{\(m\)\}\)\(gather uint8\)

14:Each workermmindependently:

15:Unpack all workers’ signs:

St\(m′\)←UnpackBits​\(Bt\(m′\)\)S\_\{t\}^\{\(m^\{\\prime\}\)\}\\leftarrow\\mathrm\{UnpackBits\}\(B\_\{t\}^\{\(m^\{\\prime\}\)\}\)for

m′∈\{1,…,M\}m^\{\\prime\}\\in\\\{1,\\ldots,M\\\}
16:Compute majority vote:

S¯t←sign⁡\(∑m′=1MSt\(m′\)\)∈\{−1,\+1\}d\\bar\{S\}\_\{t\}\\leftarrow\\operatorname\{sign\}\\left\(\\sum\_\{m^\{\\prime\}=1\}^\{M\}S\_\{t\}^\{\(m^\{\\prime\}\)\}\\right\)\\in\\\{\-1,\+1\\\}^\{d\}\(ties default to \+1\)

17:Update parameters:

Wt\+1←Wt−ηt​S¯tW\_\{t\+1\}\\leftarrow W\_\{t\}\-\\eta\_\{t\}\\bar\{S\}\_\{t\}
18:endfor

19:Communication cost:each worker sends and receives

\(M−1\)​d/8\(M\-1\)d/8bytes per step \(total

2​\(M−1\)​d/82\(M\-1\)d/8; 1\-bit encoding,

dd= dimension\)

20:Note:Encoding:

≥0→1\\geq 0\\to 1,

<0→0<0\\to 0; decoding:

0→−10\\to\-1,

1→\+11\\to\+1

Worker11G~t\(m\)=Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\\!=\\\!G\_\{t\}^\{\(m\)\}\\\!\+\\\!\\lambda W\_\{t\}Mt\+1\(m\)=β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\\!=\\\!\\beta M\_\{t\}^\{\(m\)\}\\\!\+\\\!\(1\{\-\}\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}Ut\(m\)=PolarNS​\(Mt\+1\(m\)\)U\_\{t\}^\{\(m\)\}=\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\}\)St\(m\)=sign⁡\(Ut\(m\)\)S\_\{t\}^\{\(m\)\}=\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)Bt\(m\)=PackBits​\(St\(m\)\)B\_\{t\}^\{\(m\)\}=\\mathrm\{PackBits\}\(S\_\{t\}^\{\(m\)\}\)⌈d/8⌉\\lceil d/8\\rceilbytesWorkerMMG~t\(m\)=Gt\(m\)\+λ​Wt\\widetilde\{G\}\_\{t\}^\{\(m\)\}\\\!=\\\!G\_\{t\}^\{\(m\)\}\\\!\+\\\!\\lambda W\_\{t\}Mt\+1\(m\)=β​Mt\(m\)\+\(1−β\)​G~t\(m\)M\_\{t\+1\}^\{\(m\)\}\\\!=\\\!\\beta M\_\{t\}^\{\(m\)\}\\\!\+\\\!\(1\{\-\}\\beta\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}Ut\(m\)=PolarNS​\(Mt\+1\(m\)\)U\_\{t\}^\{\(m\)\}=\\mathrm\{PolarNS\}\(M\_\{t\+1\}^\{\(m\)\}\)St\(m\)=sign⁡\(Ut\(m\)\)S\_\{t\}^\{\(m\)\}=\\operatorname\{sign\}\(U\_\{t\}^\{\(m\)\}\)Bt\(m\)=PackBits​\(St\(m\)\)B\_\{t\}^\{\(m\)\}=\\mathrm\{PackBits\}\(S\_\{t\}^\{\(m\)\}\)⌈d/8⌉\\lceil d/8\\rceilbytes⋯\\cdots⋯\\cdots⋯\\cdots⋯\\cdots⋯\\cdots⋯\\cdotsAllGather\(1\-bit packed\): each worker receives\{Bt\(1\),Bt\(2\),…,Bt\(M\)\}\\\{B\_\{t\}^\{\(1\)\},B\_\{t\}^\{\(2\)\},\\ldots,B\_\{t\}^\{\(M\)\}\\\}Unpack\{Bt\(m′\)\}\\\{B\_\{t\}^\{\(m^\{\\prime\}\)\}\\\}S¯t=sign⁡\(∑m′St\(m′\)\)\\bar\{S\}\_\{t\}=\\operatorname\{sign\}\\\!\\bigl\(\\sum\_\{m^\{\\prime\}\}S\_\{t\}^\{\(m^\{\\prime\}\)\}\\bigr\)Unpack\{Bt\(m′\)\}\\\{B\_\{t\}^\{\(m^\{\\prime\}\)\}\\\}S¯t=sign⁡\(∑m′St\(m′\)\)\\bar\{S\}\_\{t\}=\\operatorname\{sign\}\\\!\\bigl\(\\sum\_\{m^\{\\prime\}\}S\_\{t\}^\{\(m^\{\\prime\}\)\}\\bigr\)⋯\\cdotsEach worker \(locally, sameS¯t\\bar\{S\}\_\{t\}everywhere\):Wt\+1=Wt−ηt​S¯tW\_\{t\+1\}=W\_\{t\}\-\\eta\_\{t\}\\,\\bar\{S\}\_\{t\}■\\blacksquare1 collective / iter■\\blacksquarepayloads1=⌈d/8⌉s\_\{1\}=\\lceil d/8\\rceilBFigure 6:Schematic of distributedSign\-Muonwith 1\-bitAllGather\(Algorithm[3](https://arxiv.org/html/2605.16311#alg3)\)\. Each worker computes the same local pipeline as in the AllReduce variant, then*packs*its sign vector into one bit per entry \(⌈d/8⌉\\lceil d/8\\rceilbytes\)\. A singleAllGatherdisseminates every worker’s packed buffer to every other worker\. Each worker independently unpacks the gathered buffers and computes the majority voteS¯t=sign⁡\(∑m′St\(m′\)\)\\bar\{S\}\_\{t\}=\\operatorname\{sign\}\(\\sum\_\{m^\{\\prime\}\}S\_\{t\}^\{\(m^\{\\prime\}\)\}\)*locally*; the parameter update is then applied identically on all workers\. The reduction has been shifted from the network \(inAllReduce\) to local memory\.\(10−3,10\)\(10^\{\-3\},10\)\(10−2,10\)\(10^\{\-2\},10\)\(10−3,5\)\(10^\{\-3\},5\)\(10−2,5\)\(10^\{\-2\},5\)\(10−3,1\)\(10^\{\-3\},1\)7\.47\.47\.67\.67\.87\.888SignMuon ConfigurationsBest Perplexity \(↓\\downarrow\)Frobenius scalingSpectral scalingFigure 7:Comparison of Frobenius and spectral scaling across different learning rates \(η\\eta\) and Newton\-Schulz iteration counts \(nsn\_\{\\mathrm\{s\}\}\) in nanoGPT\. We show \(η,\\eta,nsn\_\{\\mathrm\{s\}\}\) asxx\-labels\. Both scaling strategies achieve nearly identical best perplexity across all configurations\.![Refer to caption](https://arxiv.org/html/2605.16311v1/x11.png)\(a\)Perplexity vs\. iterations
![Refer to caption](https://arxiv.org/html/2605.16311v1/x12.png)\(b\)Perplexity vs\. time

Figure 8:NanoGPT log\-perplexity comparison across optimization methods\.Algorithm 4PolarNS: Newton\-Schulz polar\-factor approximation1:Input:

X∈ℝr×cX\\in\\mathbb\{R\}^\{r\\times c\}, iterations

KK,

ε\>0\\varepsilon\>0,

scale∈\{spectral,fro\}\\textsc\{scale\}\\in\\\{\\textsc\{spectral\},\\textsc\{fro\}\\\}, power iters

PP\.

2:if

scale=spectral\\textsc\{scale\}=\\textsc\{spectral\}then

3:

σ←PowerIter​\(X,P,ε\)\\sigma\\leftarrow\\mathrm\{PowerIter\}\(X,P,\\varepsilon\)\(approx\.‖X‖op\\\|X\\\|\_\{\\mathrm\{op\}\}\)

4:else

5:

σ←‖X‖F\\sigma\\leftarrow\\\|X\\\|\_\{F\}
6:endif

7:

Y←X/max⁡\(σ,ε\)Y\\leftarrow X/\\max\(\\sigma,\\varepsilon\)
8:

I←IcI\\leftarrow I\_\{c\}\(c×cc\\times cidentity\)

9:for

k=1,…,Kk=1,\\ldots,Kdo

10:

Y←12​Y​\(3​I−Y⊤​Y\)Y\\leftarrow\\tfrac\{1\}\{2\}\\,Y\\left\(3I\-Y^\{\\top\}Y\\right\)
11:endfor

12:Return

YY

### 5\.3nanoGPT

We next study Sign\-Muon on autoregressive language modeling using the nanoGPT codebase of Karpathy\[[12](https://arxiv.org/html/2605.16311#bib.bib19)\], a minimal GPT\-2\-style transformer implementation\. We modify the training script to support our optimizers \(Muon,SignMuon,signSGD,SignAdam, and distributed variants\) and log training/validation loss, perplexity, sign agreement ratios, communication volume, and wall\-clock time\.

#### 5\.3\.1Setup and hyperparameter sweeps

##### Dataset\.

We train on OpenWebText\[[28](https://arxiv.org/html/2605.16311#bib.bib18)\], preprocessed with the GPT\-2 tokenizer vocabulary \(50,257 tokens\) and stored as memory\-mapped binaries\.

##### Model\.

We use a smaller GPT\-2 configuration withnlayer=6n\_\{\\text\{layer\}\}=6,nhead=6n\_\{\\text\{head\}\}=6, embedding dimensionnembd=384n\_\{\\text\{embd\}\}=384, context lengthblock\_size=512=512, and∼\\sim29\.94M non\-embedding parameters\. Training uses mixed precision \(float16\) with AMP\.

##### Training configuration\.

Unless otherwise stated, we train formax\_iters=1500=1500iterations with evaluation every 100 iterations and logging every 10 iterations\. We use a cosine learning\-rate schedule withmin\_lr=6×10−5=6\\times 10^\{\-5\}and linear warmup \(warmup\_iters=2000=2000\); becausewarmup\_iters\>max\_iters\>\\texttt\{max\\\_iters\}, the learning rate remains in the warmup phase throughout training\. We apply global\-norm gradient clipping atgrad\_clip=1\.0=1\.0\. We fix seed 1337 for determinism\.

##### Hardware and distributed environment\.

Systematic hyperparameter sweeps are conducted on NVIDIA RTX 4060 Ti GPUs\. Weak\-scaling benchmarks \(up to 16 GPUs\) are performed on NVIDIA RTX 4090 GPUs\. Distributed experiments usetorchrunwith NCCL; full\-precision optimizers use standard allreduce, while sign\-based methods use sign allreduce with majority vote\.

##### Batching\.

- •Single GPU:batch\_size=12=12withgrad\_accum=5=5\(effective batch 60 sequences, 30,720 tokens/iter\)\.
- •Distributed weak scaling:per\-devicebatch\_size=15=15with per\-GPUgrad\_accum=4=4\(after division by world size\), yielding 30,720 tokens/iter*per GPU*\.

##### Hyperparameter grids\.

We sweep learning rates in\{10−1,10−2,10−3,10−4,10−5\}\\\{10^\{\-1\},10^\{\-2\},10^\{\-3\},10^\{\-4\},10^\{\-5\}\\\}across SGD/SignSGD, Adam/SignAdam, and AdamW\. For Muon/SignMuon we additionally sweepns\_iters∈\{1,5,10\}\\in\\\{1,5,10\\\}and weight decay in\{0\.0,0\.1,0\.2\}\\\{0\.0,0\.1,0\.2\\\}, fixingβ=0\.9\\beta=0\.9,ε=10−12\\varepsilon=10^\{\-12\},ns\_scale=spectral, andpower\_iters=2\.

#### 5\.3\.2Normalization sensitivity: Frobenius vs\. spectral scaling

To study sensitivity to the normalization scheme, we repeat the SignMuon sweep using Frobenius\-norm scaling \(ns\_scale=fro\), which avoids power iteration but may behave differently on ill\-conditioned matrices\. Figure[7](https://arxiv.org/html/2605.16311#S5.F7)compares best perplexity across configurations for Frobenius and spectral scaling; performance is nearly identical across the tested settings \(e\.g\.,η=10−3\\eta=10^\{\-3\},n​s=10ns=10: 7\.45 vs\. 7\.50\), with maximum gaps under 2\.5%\.

Algorithm 5PowerIter: spectral\-norm estimate1:Input:

X∈ℝr×cX\\in\\mathbb\{R\}^\{r\\times c\}, steps

PP,

ε\>0\\varepsilon\>0\.

2:Sample

v∈ℝcv\\in\\mathbb\{R\}^\{c\}, set

v←v/\(‖v‖2\+ε\)v\\leftarrow v/\(\\\|v\\\|\_\{2\}\+\\varepsilon\)
3:for

p=1,…,Pp=1,\\ldots,Pdo

4:

u←X​vu\\leftarrow Xv,

u←u/\(‖u‖2\+ε\)u\\leftarrow u/\(\\\|u\\\|\_\{2\}\+\\varepsilon\)
5:

v←X⊤​uv\\leftarrow X^\{\\top\}u,

v←v/\(‖v‖2\+ε\)v\\leftarrow v/\(\\\|v\\\|\_\{2\}\+\\varepsilon\)
6:endfor

7:Return

‖X​v‖2\\\|Xv\\\|\_\{2\}

#### 5\.3\.3Perplexity vs\. iterations and wall\-clock time

Sign\-based methods were compared with log perplexity as the metric, as seen in Figure[8](https://arxiv.org/html/2605.16311#S5.F8), when training nanoGPT\. Among these, Sign\-Muon initially reduces the perplexity faster and ends up with the lowest final perplexity out of the sign\-based methods being compared\. The anytime\-best view \(running minimum\) in Figure[8\(b\)](https://arxiv.org/html/2605.16311#S5.F8.sf2)shows the same ordering in wall\-clock time, indicating that the improvement is not solely due to taking more iterations\.

#### 5\.3\.4Weak scaling

To quantify communication behavior under increasing worker count, in left subfigure in Figure[5](https://arxiv.org/html/2605.16311#S5.F5), we perform weak\-scaling experiments with 1, 4, 8, and 16 GPUs, keeping per\-GPU workload fixed at 30,720 tokens per iteration \(so total workload scales linearly with workers\)\. We use tuned configurations: SignMuon withη=10−3\\eta=10^\{\-3\},ns\_iters=10=10,weight\_decay=0\.0=0\.0,ns\_scale=spectral; SignAdam and SignSGD withη=10−3\\eta=10^\{\-3\}andweight\_decay=0\.0=0\.0\.

##### Findings\.

Figure[5](https://arxiv.org/html/2605.16311#S5.F5)shows that SignSGD and SignAdam scale similarly, while SignMuon has a higher baseline per\-iteration cost due to Newton\-Schulz orthogonalization\. Nonetheless, all three methods exhibit substantially sublinear growth in total time as GPU count increases, consistent with the reduced communication volume of signed allreduce\.

## 6Conclusion

We introducedSign\-Muon, a 1\-bit, matrix\-aware optimizer that fuses majority\-vote sign aggregation with Muon’s polar\-step geometry\. Our analysis provides an𝒪​\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)nonconvex rate in anℓ1\\ell\_\{1\}\-based stationarity measure under spectral\-norm smoothness, and shows a1/M1/\\sqrt\{M\}improvement in the stochastic term under unimodal symmetric noise, mirroringsignSGD\. Empirically, SignMuon achieves the best accuracy among a large CIFAR\-10/ResNet\-50 sweep and improves perplexity on nanoGPT relative to other sign\-based baselines\.

## References

- \[1\]\(2017\)QSGD: communication\-efficient SGD via gradient quantization and encoding\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p2.1)\.
- \[2\]J\. Bernstein, J\. Zhao, K\. Azizzadenesheli, and A\. Anandkumar\(2018\)signSGD with majority vote is communication efficient and fault tolerant\.CoRRabs/1810\.05291\.External Links:1810\.05291,[Link](https://arxiv.org/abs/1810.05291)Cited by:[§C\.4\.4](https://arxiv.org/html/2605.16311#A3.SS4.SSS4.2.p1.1),[§C\.4\.4](https://arxiv.org/html/2605.16311#A3.SS4.SSS4.p1.1),[§C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3.p2.6),[§C\.8\.1](https://arxiv.org/html/2605.16311#A3.SS8.SSS1.Px3.p1.4),[§C\.9\.4](https://arxiv.org/html/2605.16311#A3.SS9.SSS4.1.p1.1),[§C\.9\.4](https://arxiv.org/html/2605.16311#A3.SS9.SSS4.Px2.p1.4),[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px5.p1.6),[§2](https://arxiv.org/html/2605.16311#S2.p1.1),[§3\.1](https://arxiv.org/html/2605.16311#S3.SS1.p1.1),[§4](https://arxiv.org/html/2605.16311#S4.SS0.SSS0.Px2.p1.3)\.
- \[3\]Å\. Björck and C\. Bowie\(1971\)An iterative algorithm for computing the best estimate of an orthogonal matrix\.SIAM Journal on Numerical Analysis8\(2\),pp\. 358–364\.External Links:[Document](https://dx.doi.org/10.1137/0708036)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[4\]X\. Chen, C\. Liang, D\. Huang, E\. Real, K\. Wang, H\. Pham, X\. Dong, T\. Luong, C\. Hsieh, Y\. Lu, and Q\. V\. Le\(2023\)Symbolic discovery of optimization algorithms\.InAdvances in Neural Information Processing Systems 36,External Links:[Link](http://papers.nips.cc/paper_files/paper/2023/hash/9a39b4925e35cf447ccba8757137d84f-Abstract-Conference.html)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p4.1)\.
- \[5\]S\. K\. Danisetty, S\. R\. Mylaram, and P\. Kumar\(2023\)Adaptive consensus optimization method for gans\.Note:arXiv:2304\.10317External Links:2304\.10317,[Link](https://arxiv.org/abs/2304.10317)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[6\]V\. Gupta, T\. Koren, and Y\. Singer\(2018\)Shampoo: preconditioned stochastic tensor optimization\.Note:arXiv:1802\.09568External Links:1802\.09568,[Link](https://arxiv.org/abs/1802.09568)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[7\]K\. He, X\. Zhang, S\. Ren, and J\. Sun\(2016\)Deep residual learning for image recognition\.InProceedings of the IEEE conference on computer vision and pattern recognition,pp\. 770–778\.Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px6.p1.1)\.
- \[8\]N\. J\. Higham\(1986\)Computing the polar decomposition—with applications\.SIAM Journal on Scientific and Statistical Computing7\(4\),pp\. 1160–1174\.Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[9\]N\. J\. Higham\(2008\)Functions of matrices: theory and computation\.SIAM,Philadelphia, PA\.Cited by:[§C\.7\.2](https://arxiv.org/html/2605.16311#A3.SS7.SSS2.1.p1.6),[§C\.9\.11](https://arxiv.org/html/2605.16311#A3.SS9.SSS11.3.p3.4)\.
- \[10\]T\. Hoefler, T\. Schneider, and A\. Lumsdaine\(2010\)Characterizing the influence of system noise on large\-scale applications by simulation\.InProceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis \(SC\),pp\. 1–11\.Cited by:[§B\.2](https://arxiv.org/html/2605.16311#A2.SS2.p2.1)\.
- \[11\]K\. Jordan\(2024\)Muon: an optimizer for hidden layers in neural networks\.Note:[https://kellerjordan\.github\.io/posts/muon/](https://kellerjordan.github.io/posts/muon/)Blog post\. Accessed: 2025\-12\-26Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px5.p1.6),[§2](https://arxiv.org/html/2605.16311#S2.p3.1),[§3\.1](https://arxiv.org/html/2605.16311#S3.SS1.p1.1)\.
- \[12\]A\. Karpathy\(2022\)NanoGPT\.Note:[https://github\.com/karpathy/nanoGPT](https://github.com/karpathy/nanoGPT)Accessed: 2025\-12\-26Cited by:[§5\.3](https://arxiv.org/html/2605.16311#S5.SS3.p1.1)\.
- \[13\]D\. P\. Kingma and J\. Ba\(2014\)Adam: a method for stochastic optimization\.arXiv preprint arXiv:1412\.6980\.Cited by:[§5\.1](https://arxiv.org/html/2605.16311#S5.SS1.SSS0.Px1.p1.2)\.
- \[14\]A\. Krizhevsky\(2009\)Learning multiple layers of features from tiny images\.Technical reportUniversity of Toronto\.Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px6.p1.1)\.
- \[15\]P\. Kumar, S\. Markidis, G\. Lapenta, K\. Meerbergen, and D\. Roose\(2013\)High performance solvers for implicit particle in cell simulation\.Procedia Computer Science18,pp\. 2251–2258\.Note:2013 International Conference on Computational ScienceExternal Links:ISSN 1877\-0509,[Document](https://dx.doi.org/10.1016/j.procs.2013.05.396),[Link](https://www.sciencedirect.com/science/article/pii/S1877050913005395)Cited by:[§4](https://arxiv.org/html/2605.16311#S4.SS0.SSS0.Px4.p1.11)\.
- \[16\]P\. Kumar\(2014\)Communication optimal least squares solver\.In2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst \(HPCC,CSS,ICESS\),pp\. 316–319\.External Links:[Document](https://dx.doi.org/10.1109/HPCC.2014.55)Cited by:[§4](https://arxiv.org/html/2605.16311#S4.SS0.SSS0.Px4.p1.11)\.
- \[17\]P\. Kumar\(2015\)Multilevel communication optimal least squares\.Procedia Computer Science51,pp\. 1838–1847\.Note:International Conference On Computational Science, ICCS 2015External Links:ISSN 1877\-0509,[Document](https://dx.doi.org/10.1016/j.procs.2015.05.410),[Link](https://www.sciencedirect.com/science/article/pii/S1877050915012181)Cited by:[§4](https://arxiv.org/html/2605.16311#S4.SS0.SSS0.Px4.p1.11)\.
- \[18\]Y\. Lin, S\. Han, H\. Mao, Y\. Wang, and W\. J\. Dally\(2017\)Deep gradient compression: reducing the communication bandwidth for distributed training\.CoRRabs/1712\.01887\.External Links:1712\.01887,[Link](https://arxiv.org/abs/1712.01887)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p2.1)\.
- \[19\]I\. Loshchilov and F\. Hutter\(2017\)Decoupled weight decay regularization\.CoRRabs/1711\.05101\.External Links:1711\.05101,[Link](https://arxiv.org/abs/1711.05101)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1),[§5\.1](https://arxiv.org/html/2605.16311#S5.SS1.SSS0.Px1.p1.2)\.
- \[20\]P\. Mandlecha, S\. K\. Chatakonda, N\. Kollepara, and P\. Kumar\(2022\)Hybrid tokenization and datasets for solving mathematics and science problems using transformers\.InProceedings of the 2022 SIAM International Conference on Data Mining \(SDM\),pp\. 289–297\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611977172.33),[Link](https://epubs.siam.org/doi/abs/10.1137/1.9781611977172.33)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[21\]J\. Martens and R\. Grosse\(2015\)Optimizing neural networks with kronecker\-factored approximate curvature\.InProceedings of the 32nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.37,pp\. 2408–2417\.Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[22\]K\. Mehta, A\. Mahajan, and P\. Kumar\(2023\)Effects of spectral normalization in multi\-agent reinforcement learning\.Note:arXiv:2212\.05331External Links:2212\.05331,[Link](https://arxiv.org/abs/2212.05331)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[23\]E\. Mengoli, L\. Moll, V\. Strozzi, and E\. El\-Mhamdi\(2025\)On the byzantine fault tolerance of signSGD with majority vote\.CoRRabs/2502\.19170\.External Links:2502\.19170,[Document](https://dx.doi.org/10.48550/ARXIV.2502.19170),[Link](https://doi.org/10.48550/arXiv.2502.19170)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p4.1)\.
- \[24\]I\. Mishra, A\. Dasgupta, P\. Jawanpuria, B\. Mishra, and P\. Kumar\(2023\)Light\-weight deep extreme multilabel classification\.Note:arXiv:2304\.11045External Links:2304\.11045,[Link](https://arxiv.org/abs/2304.11045)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[25\]N\. Mishra and P\. Kumar\(2023\)Angle based dynamic learning rate for gradient descent\.Note:arXiv:2304\.10457External Links:2304\.10457,[Link](https://arxiv.org/abs/2304.10457)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[26\]N\. Mishra, B\. Mishra, P\. Jawanpuria, and P\. Kumar\(2024\)A gauss\-newton approach for min\-max optimization in generative adversarial networks\.Note:arXiv:2404\.07172External Links:2404\.07172,[Link](https://arxiv.org/abs/2404.07172)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[27\]Y\. Nesterov\(2018\)Lectures on convex optimization\.2 edition,Springer Optimization and Its Applications,Springer Cham,Cham, Switzerland\.External Links:ISBN 978\-3\-319\-91577\-7,[Document](https://dx.doi.org/10.1007/978-3-319-91578-4)Cited by:[§5\.1](https://arxiv.org/html/2605.16311#S5.SS1.SSS0.Px1.p1.2)\.
- \[28\]J\. Peterson, S\. Meylan, and D\. Bourgin\(2019\)OpenWebText corpus\.Note:[https://github\.com/jcpeterson/openwebtext](https://github.com/jcpeterson/openwebtext)Accessed: 2025\-12\-26Cited by:[§5\.3\.1](https://arxiv.org/html/2605.16311#S5.SS3.SSS1.Px1.p1.1)\.
- \[29\]B\. T\. Polyak\(1964\)Some methods of speeding up the convergence of iteration methods\.USSR Computational Mathematics and Mathematical Physics4\(5\),pp\. 1–17\.External Links:[Document](https://dx.doi.org/10.1016/0041-5553%2864%2990137-5)Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[30\]R\. Rabenseifner\(2004\)Optimization of collective reduction operations\.InInternational Conference on Computational Science \(ICCS\),pp\. 1–9\.Cited by:[§B\.2](https://arxiv.org/html/2605.16311#A2.SS2.p2.1)\.
- \[31\]W\. Shen, R\. Huang, M\. Huang, C\. Shen, and J\. Zhang\(2025\)On the convergence analysis of muon\.Note:arXiv:2505\.23737External Links:2505\.23737,[Link](https://arxiv.org/abs/2505.23737)Cited by:[§C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3.p2.6),[§C\.7\.2](https://arxiv.org/html/2605.16311#A3.SS7.SSS2.1.p1.6),[§C\.8\.1](https://arxiv.org/html/2605.16311#A3.SS8.SSS1.Px3.p1.4),[§2](https://arxiv.org/html/2605.16311#S2.p3.1),[§3\.1](https://arxiv.org/html/2605.16311#S3.SS1.p1.1)\.
- \[32\]S\. U\. Stich, J\. Cordonnier, and M\. Jaggi\(2018\)Sparsified sgd with memory\.Advances in neural information processing systems31\.Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p2.1)\.
- \[33\]I\. Sutskever, J\. Martens, G\. Dahl, and G\. Hinton\(2013\)On the importance of initialization and momentum in deep learning\.InProceedings of the 30th International Conference on Machine Learning,S\. Dasgupta and D\. McAllester \(Eds\.\),Proceedings of Machine Learning Research, Vol\.28,pp\. 1139–1147\.Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p3.1)\.
- \[34\]R\. Thakur, R\. Rabenseifner, and W\. Gropp\(2005\)Optimization of collective communication operations in MPICH\.International Journal of High Performance Computing Applications19\(1\),pp\. 49–66\.Cited by:[§B\.2](https://arxiv.org/html/2605.16311#A2.SS2.p2.1)\.
- \[35\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. Polosukhin\(2023\)Attention is all you need\.Note:arXiv:1706\.03762External Links:1706\.03762,[Link](https://arxiv.org/abs/1706.03762)Cited by:[§1](https://arxiv.org/html/2605.16311#S1.SS0.SSS0.Px1.p1.1)\.
- \[36\]T\. Vogels, S\. P\. Karimireddy, and M\. Jaggi\(2019\)PowerSGD: practical low\-rank gradient compression for distributed optimization\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p2.1)\.
- \[37\]W\. Wen, C\. Xu, F\. Yan, C\. Wu, Y\. Wang, Y\. Chen, and H\. Li\(2017\)Terngrad: ternary gradients to reduce communication in distributed deep learning\.Advances in neural information processing systems30\.Cited by:[§2](https://arxiv.org/html/2605.16311#S2.p2.1)\.

## Appendix AAdditional CIFAR\-10 results

This appendix reports the ResNet\-18 cost summary referenced in Section[5\.2\.2](https://arxiv.org/html/2605.16311#S5.SS2.SSS2)\.

SignSGDSGDMuonSign\-MuonAdamAdamW05050100100Persistent Memory \(MiB\)Figure 9:Persistent memory usage comparison for CIFAR\-10 \(ResNet\-18\)\. Excludes transient orthogonalization buffers\. Here persistent memory refers to the memory across iteration; Adam/AdamW have higher persistent memory because they maintain two moment vectors\. Sign\-Muon maintains the same persistent state size as SGD \(one momentum\-like buffer\)\.Table 2:CIFAR\-10 \(ResNet\-18\) single\-worker results\. Best values are taken over4040epochs\. Here acc\* is the best accuracy, and epoch\* is the best epoch\. Here mem is persistent memory\. Persistent memory excludes any transient orthogonalization buffers\.
## Appendix BCommunication complexity ofSign\-Muonunder theα\\alpha–β\\betamodel

This appendix provides a self\-contained communication\-complexity analysis for*distributed*Sign\-Muon\(“Spectral\-Norm Normalized Sign Descent”\) in the classicalα\\alpha–β\\beta\(latency–bandwidth\) model\. The key observation is thatSign\-MuonretainssignSGD’s*majority vote*primitive \(1\-bit sign aggregation\), while all spectral\-norm normalization and polar/orthogonalization \(SVD or Newton–Schulz\) are*purely local*post\-processing steps that incur*zero additional network communication*\.

LetMMbe the number of data\-parallel workers and letd=∑ℓ=1Lmℓ​nℓd=\\sum\_\{\\ell=1\}^\{L\}m\_\{\\ell\}n\_\{\\ell\}be the total number of communicated parameter entries \(including vector\-shaped parameters, if any\)\. Letbbbe the number of bits used to encode each sign entry \(b=1b=1with bit\-packing;b=8b=8for the common int8 implementation\)\. Denotings≔\(b​d\)/8s\\coloneqq\(bd\)/8bytes, we show that implementing majority vote via an*integer allreduce*yields per\-iteration time

Titerallreduce≈α⋅R​\(M\)\+2​\(1−1M\)​s​β,T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{allreduce\}\}\\;\\approx\\;\\alpha\\cdot R\(M\)\\;\+\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\\,\\beta,whereR​\(M\)R\(M\)is the number of communication rounds in the chosen allreduce algorithm:R​\(M\)=2​⌈log2⁡M⌉R\(M\)=2\\lceil\\log\_\{2\}M\\rceilfor recursive\-halving/doubling \(tree/butterfly\) andR​\(M\)=2​\(M−1\)R\(M\)=2\(M\-1\)for ring\. In either case, the*bandwidth term*scales linearly in the compressed payload sizessand is independent of layer structure once all tensors are packed\.

We also derive the corresponding costs for a parameter\-server star and tree \(reduce\+broadcast\) realizations, and we compareSign\-Muonwith full\-precision distributed training \(e\.g\., float32\) and withsignSGD\. For large models where bandwidth dominates, bit\-packedSign\-Muonreduces theβ\\betaterm by a factor of32×32\\timesrelative to float32 allreduce; int8 encoding yields a4×4\\timesreduction\.

### B\.1Setting, notation, and theSign\-Muoncommunication primitive

##### Model partition and notation\.

We consider data\-parallel training onMMworkers\. The model hasLLmatrix \(or tensor\-flattened\-to\-matrix\) parameter blocks

Wℓ,t∈ℝmℓ×nℓ,ℓ=1,…,L,t=0,1,2,…,W\_\{\\ell,t\}\\in\\mathbb\{R\}^\{m\_\{\\ell\}\\times n\_\{\\ell\}\},\\qquad\\ell=1,\\dots,L,\\quad t=0,1,2,\\dots,with total number of entries

d≔∑ℓ=1Lmℓ​nℓ\.d\\;\\coloneqq\\;\\sum\_\{\\ell=1\}^\{L\}m\_\{\\ell\}n\_\{\\ell\}\.We writeddfor the total communicated dimension; vector\-shaped parameters can be included by treating them asmℓ​nℓm\_\{\\ell\}n\_\{\\ell\}with one dimension equal to11\.

##### Sign\-Muonmajority\-vote step\.

At iterationtt, each workerm∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}computes a local matrix direction \(e\.g\., a Newton–Schulz/polar direction as inMuon\), denoted here by

Uℓ,t\(m\)∈ℝmℓ×nℓ\.U\_\{\\ell,t\}^\{\(m\)\}\\in\\mathbb\{R\}^\{m\_\{\\ell\}\\times n\_\{\\ell\}\}\.Then the worker transmits its*entrywise sign*matrix

Sℓ,t\(m\)≔sign⁡\(Uℓ,t\(m\)\)∈\{−1,\+1\}mℓ×nℓ\.S\_\{\\ell,t\}^\{\(m\)\}\\;\\coloneqq\\;\\operatorname\{sign\}\\\!\\bigl\(U\_\{\\ell,t\}^\{\(m\)\}\\bigr\)\\in\\\{\-1,\+1\\\}^\{m\_\{\\ell\}\\times n\_\{\\ell\}\}\.The distributed majority vote is the entrywise aggregation

S¯ℓ,t≔sign⁡\(∑m=1MSℓ,t\(m\)\)∈\{−1,\+1\}mℓ×nℓ,\\bar\{S\}\_\{\\ell,t\}\\;\\coloneqq\\;\\operatorname\{sign\}\\\!\\Bigl\(\\sum\_\{m=1\}^\{M\}S\_\{\\ell,t\}^\{\(m\)\}\\Bigr\)\\in\\\{\-1,\+1\\\}^\{m\_\{\\ell\}\\times n\_\{\\ell\}\},\(5\)\(with some fixed tie\-breaking convention, e\.g\. mapping zero to\+1\+1or0; tie\-breaking does not change message size\)\.

##### Spectral normalization and polar decomposition are local\.

AfterS¯ℓ,t\\bar\{S\}\_\{\\ell,t\}is available on each worker,Sign\-Muonforms a spectral\-norm controlled update direction\. Two common choices are:

\(normalized sign\)Dℓ,t\\displaystyle\\text\{\(normalized sign\)\}\\qquad D\_\{\\ell,t\}=S¯ℓ,t‖S¯ℓ,t‖op\(or a safe upper bound on‖S¯ℓ,t‖op\),\\displaystyle=\\frac\{\\bar\{S\}\_\{\\ell,t\}\}\{\\\|\\bar\{S\}\_\{\\ell,t\}\\\|\_\{\\mathrm\{op\}\}\}\\quad\\text\{\(or a safe upper bound on $\\\|\\bar\{S\}\_\{\\ell,t\}\\\|\_\{\\mathrm\{op\}\}$\)\},\(6\)\(polar / orthogonalized sign\)Dℓ,t\\displaystyle\\text\{\(polar / orthogonalized sign\)\}\\qquad D\_\{\\ell,t\}=polar​\(S¯ℓ,t\),\\displaystyle=\\mathrm\{polar\}\(\\bar\{S\}\_\{\\ell,t\}\),\(7\)and the parameter update is

Wℓ,t\+1=Wℓ,t−ηt​Dℓ,t\.W\_\{\\ell,t\+1\}\\;=\\;W\_\{\\ell,t\}\-\\eta\_\{t\}\\,D\_\{\\ell,t\}\.Crucially,*all*operations that produceDℓ,tD\_\{\\ell,t\}fromS¯ℓ,t\\bar\{S\}\_\{\\ell,t\}\(operator\-norm scaling, SVD\-based polar, Newton–Schulz iterations, etc\.\) are computed*locally on each worker*, hence they contribute*zero*to the network communication volume and latency\. Communication is entirely characterized by moving\{Sℓ,t\(m\)\}\\\{S\_\{\\ell,t\}^\{\(m\)\}\\\}to obtain\{S¯ℓ,t\}\\\{\\bar\{S\}\_\{\\ell,t\}\\\}\.

### B\.2α\\alpha–β\\betacommunication model and collective building blocks

\{definition\}

\[α\\alpha–β\\betamodel\] A point\-to\-point message of sizessbytes is modeled as taking time

Tα,β​\(s\)=α\+β​s,T\_\{\\alpha,\\beta\}\(s\)\\;=\\;\\alpha\+\\beta s,whereα\>0\\alpha\>0is a per\-message startup/latency cost andβ\>0\\beta\>0is the reciprocal bandwidth \(seconds per byte\)\.

We will express costs for standard collectives in terms of \(i\) a number of*rounds*\(messages on the critical path\) and \(ii\) a*bandwidth term*proportional to the total bytes injected/received per worker on the critical path\. These models and the specific algorithms below are standard in MPI/NCCL performance analyses; see, e\.g\.,\[[30](https://arxiv.org/html/2605.16311#bib.bib26),[34](https://arxiv.org/html/2605.16311#bib.bib27),[10](https://arxiv.org/html/2605.16311#bib.bib28)\]\.

##### Allreduce\.

Two common allreduce families are:

- •Recursive halving/doubling \(tree/butterfly; latency\-optimized\)\.For power\-of\-twoMM, this can be seen as a reduce\-scatter \(recursive halving\) followed by an allgather \(recursive doubling\)\. The critical path uses2​log2⁡M2\\log\_\{2\}Mrounds\. The total bytes sent per worker is approximately2​\(1−1/M\)​s2\(1\-1/M\)s\(each phase sends\(1−1/M\)​s\(1\-1/M\)s\)\.
- •Ring \(bandwidth\-optimized\)\.A reduce\-scatter ring plus an allgather ring uses2​\(M−1\)2\(M\-1\)rounds\. The total bytes sent per worker is again2​\(1−1/M\)​s2\(1\-1/M\)s\.

##### Broadcast and reduce \(tree\)\.

A binomial\-tree broadcast or reduction uses⌈log2⁡M⌉\\lceil\\log\_\{2\}M\\rceilrounds\. With pipelining/segmentation \(common for large payloads\), a useful model is

Tbcast​\(s,M\)≈α​⌈log2⁡M⌉\+β​s,Treduce​\(s,M\)≈α​⌈log2⁡M⌉\+β​s,T\_\{\\mathrm\{bcast\}\}\(s,M\)\\;\\approx\\;\\alpha\\lceil\\log\_\{2\}M\\rceil\+\\beta s,\\qquad T\_\{\\mathrm\{reduce\}\}\(s,M\)\\;\\approx\\;\\alpha\\lceil\\log\_\{2\}M\\rceil\+\\beta s,where theβ​s\\beta sterm reflects streaming thess\-byte payload through the tree\.111If no pipelining is available and each round sends a fullss\-byte message, then the bandwidth term scales asβ​s​⌈log2⁡M⌉\\beta s\\lceil\\log\_\{2\}M\\rceil\. In modern GPU collectives, pipelined/tree/ring hybrids typically reduce the bandwidth term toΘ​\(β​s\)\\Theta\(\\beta s\)for largess; our allreduce results below remain valid up to constant factors\.

### B\.3Majority vote as a sum\-reduction: mappingSign\-Muonto collectives

\{lemma\}

\[Majority vote equals sign of a sum\-reduction\] For each iterationttand parameter blockℓ\\ell, the majority\-vote aggregate \([5](https://arxiv.org/html/2605.16311#A2.E5)\) can be implemented by:

1. 1\.encodingSℓ,t\(m\)∈\{−1,\+1\}mℓ×nℓS\_\{\\ell,t\}^\{\(m\)\}\\in\\\{\-1,\+1\\\}^\{m\_\{\\ell\}\\times n\_\{\\ell\}\}as integers \(e\.g\. int8\),
2. 2\.performing an elementwiseSUMreduction across workers to obtain∑m=1MSℓ,t\(m\)\\sum\_\{m=1\}^\{M\}S\_\{\\ell,t\}^\{\(m\)\}, and
3. 3\.applyingsign⁡\(⋅\)\\operatorname\{sign\}\(\\cdot\)elementwise locally\.

###### Proof\.

For each entry\(i,j\)\(i,j\),S¯ℓ,t​\[i,j\]\\bar\{S\}\_\{\\ell,t\}\[i,j\]is by definition the sign of∑m=1MSℓ,t\(m\)​\[i,j\]\\sum\_\{m=1\}^\{M\}S\_\{\\ell,t\}^\{\(m\)\}\[i,j\]\. SinceSℓ,t\(m\)​\[i,j\]∈\{−1,\+1\}S\_\{\\ell,t\}^\{\(m\)\}\[i,j\]\\in\\\{\-1,\+1\\\}, the sum is an integer in\{−M,−M\+2,…,M\}\\\{\-M,\-M\+2,\\dots,M\\\}and can be computed exactly by integer addition\. Applyingsign⁡\(⋅\)\\operatorname\{sign\}\(\\cdot\)yields the majority vote \(up to tie\-breaking at0\)\. All steps after the reduction are local\. ∎

##### Consequence\.

By Lemma[B\.3](https://arxiv.org/html/2605.16311#A2.SS3),Sign\-Muonin synchronous data\-parallel training performs*exactly one*collective reduction of a sign\-encoded buffer per iteration \(either an allreduce, or a reduce\-to\-server followed by broadcast\), and no further communication is required by the spectral normalization or polar step\.

### B\.4Per\-iteration costs forSign\-Muon

#### B\.4\.1Payload size: 1\-bit vs int8

Letbbbe the encoding bits per sign entry:

b=\{1,ideal bit\-packed signs \(1 bit/entry\),8,practical int8 signs \(1 byte/entry\)\.b=\\begin\{cases\}1,&\\text\{ideal bit\-packed signs \(1 bit/entry\)\},\\\\ 8,&\\text\{practical int8 signs \(1 byte/entry\)\}\.\\end\{cases\}The communicated payload size per iteration \(for the full model, packed across layers\) is

s≔b​d8bytes\.s\\;\\coloneqq\\;\\frac\{b\\,d\}\{8\}\\quad\\text\{bytes\}\.\(8\)Packing all layers into one buffer does*not*changess; it reduces the number of distinct collective calls, and therefore reduces latency\.

#### B\.4\.2Decentralized allreduce \(recommended\)

\{theorem\}

\[Allreduce communication cost forDist\-SignMuon\] Assume that at each iteration, all workers pack the layerwise sign tensors into one buffer of sizes=\(b​d\)/8s=\(bd\)/8bytes and perform a singleSUMallreduce, followed by local thresholding \(Sign\-Muonmajority vote\)\. Then the per\-iteration time satisfies

Titerallreduce≈α⋅R​\(M\)\+2​\(1−1M\)​s​β,T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{allreduce\}\}\\;\\approx\\;\\alpha\\cdot R\(M\)\\;\+\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\\,\\beta,\(9\)whereR​\(M\)R\(M\)is the number of communication rounds on the critical path:

R​\(M\)=\{2​⌈log2⁡M⌉,recursive\-halving/doubling allreduce \(tree/butterfly\),2​\(M−1\),ring allreduce\.R\(M\)=\\begin\{cases\}2\\lceil\\log\_\{2\}M\\rceil,&\\text\{recursive\-halving/doubling allreduce \(tree/butterfly\)\},\\\\\[2\.5pt\] 2\(M\-1\),&\\text\{ring allreduce\}\.\\end\{cases\}Moreover, the*per\-worker*communicated volume \(send\+receive\) is approximately2​\(1−1/M\)​s2\(1\-1/M\)sbytes per iteration\.

###### Proof\.

By Lemma[B\.3](https://arxiv.org/html/2605.16311#A2.SS3), majority vote is implemented by an integer allreduce of thess\-byte buffer\. Standard allreduce decompositions \(reduce\-scatter \+ allgather\) send\(1−1/M\)​s\(1\-1/M\)sbytes per phase per worker, hence2​\(1−1/M\)​s2\(1\-1/M\)sbytes total; this yields the bandwidth term2​\(1−1/M\)​s​β2\(1\-1/M\)s\\beta\. The number of rounds is2​log2⁡M2\\log\_\{2\}Mfor recursive halving/doubling, and2​\(M−1\)2\(M\-1\)for ring\. Summing latency and bandwidth contributions yields \([9](https://arxiv.org/html/2605.16311#A2.E9)\)\. ∎

##### Layerwise versus packed collectives\.

If theLLlayers are reduced separately \(one allreduce per layer\), the payload remains∑ℓ\(b​mℓ​nℓ\)/8=\(b​d\)/8\\sum\_\{\\ell\}\(bm\_\{\\ell\}n\_\{\\ell\}\)/8=\(bd\)/8, but the latency cost multiplies byLL:

Titerlayerwise≈α⋅L​R​\(M\)\+2​\(1−1M\)​s​β\.T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{layerwise\}\}\\;\\approx\\;\\alpha\\cdot L\\,R\(M\)\\;\+\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\\,\\beta\.Packing layers is therefore essential whenα\\alphais non\-negligible\.

#### B\.4\.3Parameter server \(PS\) star

We model a single logical parameter server that computes the majority vote and disseminates the aggregated sign to workers\.

\{theorem\}

\[Naive PS\-star cost forDist\-SignMuon\] Consider a parameter\-server star in which each worker sends anss\-byte sign buffer to the server, the server computes the elementwise sum and majority sign, and the server broadcasts the resultingss\-byte buffer back to workers\. In theα\\alpha–β\\betamodel, a conservative synchronous bound on iteration time is

TiterPS​\-​star≈M​\(α\+β​s\)\+Tbcast​\(s,M\)≈M​\(α\+β​s\)\+α​⌈log2⁡M⌉\+β​s\.T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{PS\\text\{\-\}star\}\}\\;\\approx\\;M\(\\alpha\+\\beta s\)\\;\+\\;T\_\{\\mathrm\{bcast\}\}\(s,M\)\\;\\approx\\;M\(\\alpha\+\\beta s\)\\;\+\\;\\alpha\\lceil\\log\_\{2\}M\\rceil\+\\beta s\.The server injects/receivesΘ​\(M​s\)\\Theta\(Ms\)bytes per iteration, making the server a bandwidth bottleneck whenMMis large\.

###### Proof\.

The uplink consists ofMMworker\-to\-server messages of sizess; under a star, the server must receive allMMmessages, incurringM​\(α\+β​s\)M\(\\alpha\+\\beta s\)on the critical path in the worst case \(no perfect overlap\)\. The downlink is a broadcast of sizesstoMMworkers with costTbcast​\(s,M\)T\_\{\\mathrm\{bcast\}\}\(s,M\)\. The server’s total ingress\+egress volume isM​s\+M​s=2​M​sMs\+Ms=2Msbytes \(up to constants\), whereas each worker sends/receives2​s2sbytes\. ∎

#### B\.4\.4Tree\-based PS: reduce \+ broadcast \(server as root\)

Instead of collecting all workers independently, the uplink can be organized as a reduction tree that sums sign buffers*in\-network*\(each internal node sums partial buffers\)\.

\{theorem\}

\[Tree reduce \+ broadcast cost\] If the uplink is implemented as a treeSUMreduction of anss\-byte sign buffer to a root \(server\), followed by a broadcast of thess\-byte aggregated buffer, then

TiterPS​\-​tree≈Treduce​\(s,M\)\+Tbcast​\(s,M\)≈2​α​⌈log2⁡M⌉\+2​β​s\.T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{PS\\text\{\-\}tree\}\}\\;\\approx\\;T\_\{\\mathrm\{reduce\}\}\(s,M\)\+T\_\{\\mathrm\{bcast\}\}\(s,M\)\\;\\approx\\;2\\alpha\\lceil\\log\_\{2\}M\\rceil\+2\\beta s\.This matches the allreduce latency order \(up to constants\) but still centralizes computation at the root\.

###### Proof\.

A tree reduction and a tree broadcast each takeα​⌈log2⁡M⌉\+β​s\\alpha\\lceil\\log\_\{2\}M\\rceil\+\\beta sunder a pipelined tree model; adding yields the result\. The aggregation itself is integer addition, local at intermediate nodes and/or the root\. ∎

### B\.5Comparison with full\-precision distributed training and withSignSGD

#### B\.5\.1Allreduce bandwidth comparison

In standard data\-parallel SGD/Adam \(and in full\-precision distributedMuonvariants\), workers typically allreduce float32 gradients or updates, corresponding to payload

sfp32=4​dbytes\.s\_\{\\mathrm\{fp32\}\}=4d\\quad\\text\{bytes\.\}By contrast,Dist\-SignMuoncommunicates only sign information:

sSign​\-​Muon=b​d8byteswith​b∈\{1,8\}\.s\_\{\\mathrm\{Sign\\text\{\-\}Muon\}\}=\\frac\{bd\}\{8\}\\quad\\text\{bytes\}\\quad\\text\{with \}b\\in\\\{1,8\\\}\.Thus, for the bandwidth term in Theorem[B\.4\.2](https://arxiv.org/html/2605.16311#A2.SS4.SSS2),

sfp32sSign​\-​Muon=4​d\(b​d\)/8=32b=\{32,b=1​\(bit\-packed\),4,b=8​\(int8\)\.\\frac\{s\_\{\\mathrm\{fp32\}\}\}\{s\_\{\\mathrm\{Sign\\text\{\-\}Muon\}\}\}=\\frac\{4d\}\{\(bd\)/8\}=\\frac\{32\}\{b\}=\\begin\{cases\}32,&b=1\\ \\text\{\(bit\-packed\)\},\\\\ 4,&b=8\\ \\text\{\(int8\)\}\.\\end\{cases\}In the bandwidth\-dominated regime \(largedd\), the allreduce time improves by approximately the same factor\.

#### B\.5\.2Relationship toSignSGD

DistributedSignSGDwith majority vote communicates*exactly*the same sign payload size \(11bit per entry uplink and downlink in a PS formulation\), and can likewise be implemented via an integer allreduce of\{±1\}\\\{\\pm 1\\\}signs \(Lemma[B\.3](https://arxiv.org/html/2605.16311#A2.SS3)\)\. Therefore, from a*pure communication*standpoint,Dist\-SignMuonand distributedSignSGDhave the same asymptoticα\\alpha–β\\betacosts for the sign aggregation primitive; any practical differences arise from:

- •local computation:Dist\-SignMuonperforms spectral normalization / polar decomposition locally \(SVD or Newton–Schulz\), whereasSignSGDdoes not; and
- •payload encoding:implementations may use bit\-packing or int8\.

### B\.6Worked example: ResNet\-50

ResNet\-50 has approximately 23\.5M parameters \(d≈2\.35×107d\\approx 2\.35\\times 10^\{7\}\)\. A float32 allreduce would communicatesfp32=4​d≈94​MBs\_\{\\mathrm\{fp32\}\}=4d\\approx 94~\\mathrm\{MB\}per step \(ignoring protocol overhead here\)\. A bit\-packed sign buffer would communicatessign,1​b=d/8≈2\.8​MiBs\_\{\\mathrm\{sign\},1\\mathrm\{b\}\}=d/8\\approx 2\.8~\\mathrm\{MiB\}per step, a32×32\\timesreduction in the bandwidth term\. With int8 encoding \(as we show in our implementation\), the payload would boil down tossign,8​b=d≈23\.5​MBs\_\{\\mathrm\{sign\},8\\mathrm\{b\}\}=d\\approx 23\.5~\\mathrm\{MB\}, corresponding to a4×4\\timesreduction relative to float32\.

### B\.7Practical guidance \(systems\-facing\)

The analysis above suggests or motivates the following implementation principles, that inspired our work:

- •Pack sign buffers\.Aggregate all \(gradient\) parameter signs into a single buffer to pay the allreduce latency term once per iteration\.
- •Prefer decentralized collectives\.Allreduce avoids a parameter\-server bandwidth hotspot when scaling to many workers\.
- •Exploit local compute\.Polar normalization \(NS/SVD\) trades local matrix multiplications on local batch of samples for reduced communication; this is most attractive when network bandwidth is the bottleneck and even more effective if overlapping of computation and communication is implemented\.
- •Consider bit\-packing\.Using true 1\-bit packing can further reduce the bandwidth term by an additional factor of8×8\\timesrelative to int8 signs, at the cost of packing/unpacking overhead\.
- •Polar decomposition is communication\-free\.ChoosingDℓ,t=polar​\(S¯ℓ,t\)D\_\{\\ell,t\}=\\mathrm\{polar\}\(\\bar\{S\}\_\{\\ell,t\}\)improves the*geometry*of the step but does not affect the communication complexity, since it is computed locally after aggregation\.
- •Avoid PS\-star at scale\.A naive PS\-star introduces anΘ​\(M\)\\Theta\(M\)server bottleneck in both latency and bandwidth \(Theorem[B\.4\.3](https://arxiv.org/html/2605.16311#A2.SS4.SSS3)\); allreduce avoids this by distributing the work across workers\.

### B\.8Communication analysis: 1\-bit AllGather vs\. int8 AllReduce

In this appendix, we analyze communication cost of the 1\-bit*AllGather\-then\-local\-reduce*variant \(Algorithm[3](https://arxiv.org/html/2605.16311#alg3)\) and we compare it to the existing*SUM AllReduce*implementation \(Algorithm[2](https://arxiv.org/html/2605.16311#alg2)\)\.

##### Notation\.

LetMMbe the number of data\-parallel workers and letddbe the number of scalar entries communicated per iteration after flattening/concatenating all parameter blocks\. At iterationtt, workermmbasically forms an entrywise sign vectorSt\(m\)∈\{−1,\+1\}dS\_\{t\}^\{\(m\)\}\\in\\\{\-1,\+1\\\}^\{d\}\.

As before, we use the standardα\\alpha\-β\\betamodel for communication time: sendingssbytes costs

T​\(s\)≈α\+β​s,T\(s\)\\;\\approx\\;\\alpha\+\\beta s,where as beforeα\\alphais a per\-message latency term andβ\\betais the inverse bandwidth \(seconds/byte\)\. For collectives, the latency term scales with the number of rounds on the critical path\.

##### Packed 1\-bit representation\.

In Algorithm[3](https://arxiv.org/html/2605.16311#alg3), we recall that each sign entry is encoded into one bit, e\.g\., as follows:

bi\(m\)=\{1,St\(m\)​\[i\]=\+1,0,St\(m\)​\[i\]=−1,i=1,…,db\_\{i\}^\{\(m\)\}\\;=\\;\\begin\{cases\}1,&S^\{\(m\)\}\_\{t\}\[i\]=\+1,\\\\ 0,&S^\{\(m\)\}\_\{t\}\[i\]=\-1,\\end\{cases\}\\qquad i=1,\\dots,dand then packed into a contiguous byte arrayBt\(m\)∈\{0,1\}s1B\_\{t\}^\{\(m\)\}\\in\\\{0,1\\\}^\{s\_\{1\}\}with

s1≔⌈d8⌉bytes\.s\_\{1\}\\;\\coloneqq\\;\\left\\lceil\\frac\{d\}\{8\}\\right\\rceil\\quad\\text\{bytes\.\}\(10\)\(When8∣d8\\mid d,s1=d/8s\_\{1\}=d/8exactly\.\)

##### Majority vote from gathered bits \(local computation, no extra communication\)\.

After doing an all gather, each worker has\{Bt\(1\),…,Bt\(M\)\}\\\{B\_\{t\}^\{\(1\)\},\\dots,B\_\{t\}^\{\(M\)\}\\\}and can reconstruct\{St\(1\),…,St\(M\)\}\\\{S\_\{t\}^\{\(1\)\},\\dots,S\_\{t\}^\{\(M\)\}\\\}\(explicit unpack\) or compute the vote implicitly\. Letci≔∑m=1Mbi\(m\)c\_\{i\}\\coloneqq\\sum\_\{m=1\}^\{M\}b\_\{i\}^\{\(m\)\}be the number of\+1\+1signs in coordinateii\. Then the signed sum is given as follows

∑m=1MSt\(m\)​\[i\]=∑m=1M\(2​bi\(m\)−1\)=2​ci−M,\\sum\_\{m=1\}^\{M\}S\_\{t\}^\{\(m\)\}\[i\]\\;=\\;\\sum\_\{m=1\}^\{M\}\(2b\_\{i\}^\{\(m\)\}\-1\)\\;=\\;2c\_\{i\}\-M,so the majority vote with the same tie\-breaking convention as the algorithm can be basically written as follows

S¯t​\[i\]=sign⁡\(2​ci−M\)\\bar\{S\}\_\{t\}\[i\]\\;=\\;\\operatorname\{sign\}\(2c\_\{i\}\-M\)\(withsign⁡\(0\)\\operatorname\{sign\}\(0\)interpreted according to the chosen tie\-breaking rule\)\. We note that this reduction is purely local once the all\-gather operation completes\.

#### B\.8\.1AllGather 1\-bit: volume and time

##### Per\-worker communication volume\.

An all\-gather of a per\-worker payload ofs1s\_\{1\}bytes produces a gathered buffer of sizeM​s1Ms\_\{1\}bytes on every worker\. Necessarily, each worker must receive at least\(M−1\)​s1\(M\-1\)s\_\{1\}bytes \(the other workers’ payloads\)\. A standard bandwidth\-optimal implementation achieves the following per\-worker volume:

VsendAG\\displaystyle V\_\{\\mathrm\{send\}\}^\{\\mathrm\{AG\}\}=\(M−1\)​s1,\\displaystyle\\;=\\;\(M\-1\)s\_\{1\},\(11\)VrecvAG\\displaystyle V\_\{\\mathrm\{recv\}\}^\{\\mathrm\{AG\}\}=\(M−1\)​s1,\\displaystyle\\;=\\;\(M\-1\)s\_\{1\},\(12\)VbidirAG\\displaystyle V\_\{\\mathrm\{bidir\}\}^\{\\mathrm\{AG\}\}=2​\(M−1\)​s1\.\\displaystyle\\;=\\;2\(M\-1\)s\_\{1\}\.\(13\)The*total*system\-wide payload injected into the network \(summing over all workers\) scales asM​\(M−1\)​s1M\(M\-1\)s\_\{1\}bytes sent and the same amount received\. Note that we have reportedVbidirV\_\{\\mathrm\{bidir\}\}\(bidirectional volume\) as well because real interconnects are basically*full\-duplex*\.

Table 3:Communication comparison for distributed majority vote inSign\-Muon\. Hereddis the number of sign entries,MMis the number of workers,s1=⌈d/8⌉s\_\{1\}=\\lceil d/8\\rceil\(packed 1\-bit bytes\), ands8=ds\_\{8\}=d\(int8 bytes\)\.
##### Latency rounds andα\\alpha\-β\\betaiteration time\.

LetRAG​\(M\)R\_\{\\mathrm\{AG\}\}\(M\)denote the number of rounds on the critical path for the chosen all\-gather:

RAG​\(M\)=\{⌈log2⁡M⌉,recursive doubling / tree,M−1,ring\.R\_\{\\mathrm\{AG\}\}\(M\)\\;=\\;\\begin\{cases\}\\lceil\\log\_\{2\}M\\rceil,&\\text\{recursive doubling / tree\},\\\\ M\-1,&\\text\{ring\}\.\\end\{cases\}We then have a convenientα\\alpha\-β\\betaapproximation for the all\-gather time as follows

TiterAG​\(1​b​i​t\)≈α⋅RAG​\(M\)\+\(M−1\)​s1​β\.T\_\{\\mathrm\{iter\}\}^\{\\mathrm\{AG\(1bit\)\}\}\\;\\approx\\;\\alpha\\cdot R\_\{\\mathrm\{AG\}\}\(M\)\\;\+\\;\(M\-1\)s\_\{1\}\\,\\beta\.\(14\)

##### Local compute and memory overhead\.

When we compare with AllReduce, the AllGather shifts the reduction into local computation\. After all\-gather step, each worker must read \(at least\) the gathered buffer of sizeM​s1Ms\_\{1\}bytes\. A straightforward unpack\-then\-sum implementation would performO​\(M​d\)O\(Md\)integer operations\. However, more efficient bit\-level implementations \(e\.g\., per\-byte popcount / lookup tables\) still have anO​\(M​s1\)O\(Ms\_\{1\}\)memory\-read footprint andO​\(M​s1\)O\(Ms\_\{1\}\)lightweight integer work\. This does not change network cost, but it does introduce anMM\-dependent local overhead\.

#### B\.8\.2AllReduce int8: volume and time

Algorithm[2](https://arxiv.org/html/2605.16311#alg2)performs aSUMAllReduce over anint8sign vector \(one byte per entry\)\. Again, the per\-worker payload size is given as follows

s8:=dbytess\_\{8\}:=d\\quad\\text\{bytes\}\(15\)
##### Per\-worker communication volume \(bandwidth\-optimal AllReduce\)\.

A bandwidth\-optimal AllReduce implementation \(e\.g\., reduce\-scatter \+ all\-gather\) moves

VsendAR\\displaystyle V\_\{\\mathrm\{send\}\}^\{\\mathrm\{AR\}\}=2​\(1−1M\)​s8,\\displaystyle\\;=\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\_\{8\},VrecvAR\\displaystyle V\_\{\\mathrm\{recv\}\}^\{\\mathrm\{AR\}\}=2​\(1−1M\)​s8,\\displaystyle\\;=\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\_\{8\},VbidirAR\\displaystyle V\_\{\\mathrm\{bidir\}\}^\{\\mathrm\{AR\}\}=4​\(1−1M\)​s8\\displaystyle\\;=\\;4\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\_\{8\}per worker per iteration on the critical path\. Notably, the bandwidth term would beO​\(s8\)O\(s\_\{8\}\)per worker and this is essentially independent ofMMfor largeM\.M\.

##### Latency rounds andα\\alpha\-β\\betaiteration time\.

As before, letRAR​\(M\)R\_\{\\mathrm\{AR\}\}\(M\)denote the number of communication rounds:

RAR​\(M\)=\{2​⌈log2⁡M⌉,recursive half/double \(tree/butterfly\),2​\(M−1\),ring\.R\_\{\\mathrm\{AR\}\}\(M\)\\;=\\;\\begin\{cases\}2\\lceil\\log\_\{2\}M\\rceil,&\\text\{recursive half/double \(tree/butterfly\)\},\\\\ 2\(M\-1\),&\\text\{ring\}\.\\end\{cases\}Anα\\alpha\-β\\betaapproximation for AllReduce time is

TiterAR​\(int8\)≈α⋅RAR​\(M\)\+2​\(1−1M\)​s8​βT\_\{\\mathrm\{iter\}\}^\{\\mathrm\{AR\(int8\)\}\}\\;\\approx\\;\\alpha\\cdot R\_\{\\mathrm\{AR\}\}\(M\)\\;\+\\;2\\Bigl\(1\-\\tfrac\{1\}\{M\}\\Bigr\)s\_\{8\}\\,\\beta\(16\)

#### B\.8\.3Comparison and break\-even behavior

##### Bandwidth\-term comparison \(dominant for largedd\)\.

Usings1≈d/8s\_\{1\}\\approx d/8ands8=ds\_\{8\}=d, the bandwidth terms of \([14](https://arxiv.org/html/2605.16311#A2.E14)\) and \([16](https://arxiv.org/html/2605.16311#A2.E16)\) satisfy

\(M−1\)​s12​\(1−1M\)​s8≈\(M−1\)⋅\(d/8\)2​\(1−1M\)⋅d=M16\\frac\{\(M\-1\)s\_\{1\}\}\{2\(1\-\\tfrac\{1\}\{M\}\)s\_\{8\}\}\\;\\approx\\;\\frac\{\(M\-1\)\\cdot\(d/8\)\}\{2\(1\-\\tfrac\{1\}\{M\}\)\\cdot d\}\\;=\\;\\frac\{M\}\{16\}\(17\)Thus, purely in terms of bandwidth:

- •ForM<16M<16, the 1\-bit AllGather bandwidth term can be smaller than int8 AllReduce\.
- •AtM≈16M\\approx 16, the two are comparable \(up to ceilings and implementation constants\)\.
- •ForM\>16M\>16, the AllGather bandwidth term grows linearly inMMand becomes larger than AllReduce\.

This reflects a fundamental trade\-off: AllGather benefits from8×8\\timespayload compression but replicates the payload to all workers, whereas AllReduce aggregates in\-network and keeps per\-worker communicated bytesO​\(d\)O\(d\)\.

##### Latency\-term comparison \(dominant for smalldd\)\.

Under ring implementations, AllGather uses\(M−1\)\(M\-1\)rounds while AllReduce uses2​\(M−1\)2\(M\-1\)rounds\. Hence, when latency dominates, AllGather can be advantaged relative to ring AllReduce\. However, we note that tree/butterfly AllReduce reduces latency toO​\(log⁡M\)O\(\\log M\)rounds, which may remove this advantage depending on the backend\.

##### Memory and local\-reduction overhead\.

AllGather needs each worker to hold a gathered buffer of sizeM​s1≈M​d/8Ms\_\{1\}\\approx Md/8bytes and to perform anMM\-dependent local reduction, while AllReduce returns only a single reduced buffer of sizes8=ds\_\{8\}=dbytes and performs the reduction inside the collective\. Consequently, for largeMM, AllReduce is preferable both for network scaling and for per\-worker memory/compute overhead\.

## Appendix CSign\-Muon: spectral\-norm normalized sign descent \(standalone theoretical analysis\)

This appendix provides a self\-contained, research\-grade theoretical analysis for*Sign\-Muon*, a sign\-based optimizer designed for matrix\-structured parameters and motivated by the spectral\-geometry analysis of Muon and the sign\-reliability/majority\-vote analysis of signSGD\. We state theorems and provide proof sketches inline, with fully detailed proofs at the end of this appendix\.

The analysis matches the notation used in the main text: parameters are matricesW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}, the smoothness constant is spectral \(L∗L\_\{\\ast\}\), and progress is measured using theℓ1\\ell\_\{1\}\-geometry proxy‖∇f​\(W\)‖1/m​n\\left\\lVert\\nabla f\(W\)\\right\\rVert\_\{1\}/\\sqrt\{mn\}\. We also include a detailed discussion of the role of the polar decomposition \(and its Newton–Schulz approximation\) and compare convergence guarantees between full Muon \(polar directions\) and Sign\-Muon \(sign\-quantized directions\)\.

### C\.1Problem setup, norms, and assumptions

We consider minimization of the population objective

minW∈ℝm×n⁡f​\(W\),f​\(W\):=𝔼ξ​\[f​\(W;ξ\)\],\\min\_\{W\\in\\mathbb\{R\}^\{m\\times n\}\}f\(W\),\\qquad f\(W\):=\\mathbb\{E\}\_\{\\xi\}\\big\[f\(W;\\xi\)\\big\],\(18\)whereWWdenotes a*matrix\-structured*parameter block \(e\.g\., a weight matrix of a layer\)\. Set the ambient dimension to be

##### Inner product and norms\.

For matricesA,B∈ℝm×nA,B\\in\\mathbb\{R\}^\{m\\times n\}, the Frobenius inner product is

⟨A,B⟩:=tr⁡\(A⊤​B\)=∑i=1m∑j=1nAi​j​Bi​j\.\\left\\langle A,B\\right\\rangle:=\\operatorname\{tr\}\(A^\{\\top\}B\)=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}A\_\{ij\}B\_\{ij\}\.We use:

‖A‖F:=⟨A,A⟩,‖A‖op:=sup‖x‖F=1‖A​x‖F,‖A‖∗:=∑kσk​\(A\),\\left\\lVert A\\right\\rVert\_\{\\mathrm\{F\}\}:=\\sqrt\{\\left\\langle A,A\\right\\rangle\},\\qquad\\left\\lVert A\\right\\rVert\_\{\\mathrm\{op\}\}:=\\sup\_\{\\left\\lVert x\\right\\rVert\_\{\\mathrm\{F\}\}=1\}\\left\\lVert Ax\\right\\rVert\_\{\\mathrm\{F\}\},\\qquad\\left\\lVert A\\right\\rVert\_\{\*\}:=\\sum\_\{k\}\\sigma\_\{k\}\(A\),whereσk​\(A\)\\sigma\_\{k\}\(A\)are the singular values, and∥⋅∥∗\\left\\lVert\\cdot\\right\\rVert\_\{\*\}is the nuclear norm\. Recall the duality relation

‖G‖∗=max‖D‖op≤1⁡⟨G,D⟩\.\\left\\lVert G\\right\\rVert\_\{\*\}=\\max\_\{\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\left\\langle G,D\\right\\rangle\.\(19\)We also use the entrywiseℓ1\\ell\_\{1\}norm

‖A‖1:=∑i,j\|Ai​j\|\.\\left\\lVert A\\right\\rVert\_\{1\}:=\\sum\_\{i,j\}\|A\_\{ij\}\|\.We will repeatedly use the elementary inequalities

1d​‖A‖1≤‖A‖F≤‖A‖∗\.\\frac\{1\}\{\\sqrt\{d\}\}\\left\\lVert A\\right\\rVert\_\{1\}\\;\\leq\\;\\left\\lVert A\\right\\rVert\_\{\\mathrm\{F\}\}\\;\\leq\\;\\left\\lVert A\\right\\rVert\_\{\*\}\.\(20\)

##### Sign map\.

For a scalarx∈ℝx\\in\\mathbb\{R\}, define

sign⁡\(x\):=\{\+1,x\>0,0,x=0,−1,x<0\.\\operatorname\{sign\}\(x\):=\\begin\{cases\}\+1,&x\>0,\\\\ 0,&x=0,\\\\ \-1,&x<0\.\\end\{cases\}For a matrixAA,sign⁡\(A\)\\operatorname\{sign\}\(A\)is applied entrywise\.

\{assumption\}

\[Lower bounded objective\] There existsf∗\>−∞f^\{\\ast\}\>\-\\inftysuch thatf​\(W\)≥f∗f\(W\)\\geq f^\{\\ast\}for allWW\.

\{assumption\}

\[Spectral\-norm smoothness\] There existsL∗\>0L\_\{\\ast\}\>0such that for allW,W′∈ℝm×nW,W^\{\\prime\}\\in\\mathbb\{R\}^\{m\\times n\},

‖∇f​\(W\)−∇f​\(W′\)‖∗≤L∗​‖W−W′‖op\.\\left\\lVert\\nabla f\(W\)\-\\nabla f\(W^\{\\prime\}\)\\right\\rVert\_\{\*\}\\;\\leq\\;L\_\{\\ast\}\\left\\lVert W\-W^\{\\prime\}\\right\\rVert\_\{\\mathrm\{op\}\}\.\(21\)
\{assumption\}

\[Unbiased bounded\-variance stochastic gradients\] At steptt, letgt:=∇f​\(Wt\)g\_\{t\}:=\\nabla f\(W\_\{t\}\)and letG~t∈ℝm×n\\widetilde\{G\}\_\{t\}\\in\\mathbb\{R\}^\{m\\times n\}be an unbiased mini\-batch gradient estimator:

𝔼​\[G~t∣Wt\]=gt\.\\mathbb\{E\}\\big\[\\widetilde\{G\}\_\{t\}\\mid W\_\{t\}\\big\]=g\_\{t\}\.Assume that there exist nonnegative constants\{σi​j\}i∈\[m\],j∈\[n\]\\\{\\sigma\_\{ij\}\\\}\_\{i\\in\[m\],j\\in\[n\]\}such that, for each entry and for a mini\-batch sizenbn\_\{b\},

Var⁡\(G~t,i​j∣Wt\)≤σi​j2nb\.\\operatorname\{Var\}\\\!\\big\(\\widetilde\{G\}\_\{t,ij\}\\mid W\_\{t\}\\big\)\\;\\leq\\;\\frac\{\\sigma\_\{ij\}^\{2\}\}\{n\_\{b\}\}\.\(22\)Letσ∈ℝm×n\\sigma\\in\\mathbb\{R\}^\{m\\times n\}denote the matrix with entriesσi​j\\sigma\_\{ij\}and define‖σ‖1:=∑i,jσi​j\\left\\lVert\\sigma\\right\\rVert\_\{1\}:=\\sum\_\{i,j\}\\sigma\_\{ij\}\.

\{assumption\}

\[Unimodal symmetric noise \(for majority vote\)\] In addition to Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2), suppose that for each\(i,j\)\(i,j\)the centered noise

G~t,i​j−gt,i​j\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}has a distribution \(conditioned onWtW\_\{t\}\) that is unimodal and symmetric about0\.

\{remark\}

\[Why spectral smoothness?\] Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)is the matrix\-geometry counterpart of standardLL\-smoothness\. It is the natural assumption for*spectral\-norm constrained*update directions \(i\.e\.‖Dt‖op≤1\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\), and matches the analysis style used for Muon\.

### C\.2Algorithms and update directions

We separate \(i\) the*sign acquisition*mechanism \(which determines a sign matrix to communicate\) and \(ii\) the*spectral normalization / local shaping*mechanism \(which determines the final directionDtD\_\{t\}\)\.

#### C\.2\.1Generic Sign\-Muon update template

At iterationtt, the algorithm constructs a random sign matrixSt∈\{−1,0,\+1\}m×nS\_\{t\}\\in\\\{\-1,0,\+1\\\}^\{m\\times n\}and then sets

Dt:=1m​n​St\(so that‖Dt‖op≤1whenever‖St‖op≤m​n\)\.D\_\{t\}:=\\frac\{1\}\{\\sqrt\{mn\}\}S\_\{t\}\\qquad\\text\{\(so that $\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1$ whenever $\\left\\lVert S\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\sqrt\{mn\}$\)\.\}\(23\)The parameter update is

Wt\+1=Wt−ηt​Dt,W\_\{t\+1\}=W\_\{t\}\-\\eta\_\{t\}D\_\{t\},\(24\)with step sizeηt\>0\\eta\_\{t\}\>0\.

##### Two natural choices forStS\_\{t\}\.

We consider \(at least\) two concrete instantiations:

- •Gradient\-sign \(signSGD\-style\)\.SetSt=sign⁡\(G~t\)S\_\{t\}=\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t\}\)\(single worker\), or apply majority vote across workers \(distributed\)\. This is the closest analogue of signSGD, but the update uses the*spectral*descent lemma via \([23](https://arxiv.org/html/2605.16311#A3.E23)\)\.
- •Muon\-direction\-sign \(Newton–Schulz / polar direction, then sign\)\.Maintain a momentumMtM\_\{t\}and compute an \(approximate\) polar factorUt≈polar⁡\(Mt\)U\_\{t\}\\approx\\operatorname\{polar\}\(M\_\{t\}\)via Newton–Schulz; then setSt=sign⁡\(Ut\)S\_\{t\}=\\operatorname\{sign\}\(U\_\{t\}\)\. This is the “sign of Newton–Schulz direction” variant described in the algorithmic section of the main text\.

Our core convergence theorems below are stated for a*generic sign oracle*through its sign\-error probabilities, and then specialized to the gradient\-sign case using Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\(and to distributed majority vote using Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\)\.

#### C\.2\.2Distributed aggregation: majority vote

Suppose there areMMworkers, and each workerm∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}constructs a local sign matrixSt\(m\)∈\{−1,0,\+1\}m×nS\_\{t\}^\{\(m\)\}\\in\\\{\-1,0,\+1\\\}^\{m\\times n\}\. The aggregated sign is defined entrywise by a majority rule:

S¯t,i​j:=sign⁡\(∑m=1MSt,i​j\(m\)\)\.\\bar\{S\}\_\{t,ij\}:=\\operatorname\{sign\}\\\!\\left\(\\sum\_\{m=1\}^\{M\}S^\{\(m\)\}\_\{t,ij\}\\right\)\.\(25\)Then all workers update usingDt=S¯t/m​nD\_\{t\}=\\bar\{S\}\_\{t\}/\\sqrt\{mn\}\.

\{remark\}

\[Tie\-breaking\] If the sum in \([25](https://arxiv.org/html/2605.16311#A3.E25)\) equals0, thensign⁡\(0\)=0\\operatorname\{sign\}\(0\)=0\. Many implementations break ties deterministically \(e\.g\. to\+1\+1\); under continuous noise models, ties occur with probability0, so convergence bounds are unaffected\.

### C\.3Core descent lemma in spectral geometry

\{lemma\}

\[Spectral descent lemma\] Assume Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. LetW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}andD∈ℝm×nD\\in\\mathbb\{R\}^\{m\\times n\}\. For anyη≥0\\eta\\geq 0,

f​\(W−η​D\)≤f​\(W\)−η​⟨∇f​\(W\),D⟩\+L∗2​η2​‖D‖op2\.f\(W\-\\eta D\)\\;\\leq\\;f\(W\)\-\\eta\\left\\langle\\nabla f\(W\),D\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.\(26\)In particular, if‖D‖op≤1\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1then

f​\(W−η​D\)≤f​\(W\)−η​⟨∇f​\(W\),D⟩\+L∗2​η2\.f\(W\-\\eta D\)\\;\\leq\\;f\(W\)\-\\eta\\left\\langle\\nabla f\(W\),D\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.\(27\)
###### Proof sketch\.

Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)implies that the gradient map isL∗L\_\{\\ast\}\-Lipschitz from\(ℝm×n,∥⋅∥op\)\(\\mathbb\{R\}^\{m\\times n\},\\left\\lVert\\cdot\\right\\rVert\_\{\\mathrm\{op\}\}\)to\(ℝm×n,∥⋅∥∗\)\(\\mathbb\{R\}^\{m\\times n\},\\left\\lVert\\cdot\\right\\rVert\_\{\*\}\)\. Integrate⟨∇f​\(W\+τ​Δ\),Δ⟩\\left\\langle\\nabla f\(W\+\\tau\\Delta\),\\Delta\\right\\ranglealong the segment fromWWtoW\+ΔW\+\\Delta, and use duality⟨A,B⟩≤‖A‖∗​‖B‖op\\left\\langle A,B\\right\\rangle\\leq\\left\\lVert A\\right\\rVert\_\{\*\}\\left\\lVert B\\right\\rVert\_\{\\mathrm\{op\}\}to control the remainder term\. A detailed proof is in Appendix[C\.9\.1](https://arxiv.org/html/2605.16311#A3.SS9.SSS1)\. ∎

### C\.4Sign progress identity and sign\-reliability bounds

Throughout, write the true gradient at timettas

gt:=∇f​\(Wt\)\.g\_\{t\}:=\\nabla f\(W\_\{t\}\)\.
#### C\.4\.1Entrywise sign error probabilities

LetSt∈\{−1,0,\+1\}m×nS\_\{t\}\\in\\\{\-1,0,\+1\\\}^\{m\\times n\}denote the \(possibly aggregated\) sign matrix used to build the direction\. Define the conditional sign error probability for each entry:

qi​j,t:=ℙ​\(St,i​j≠sign⁡\(gt,i​j\)\|Wt\)\.q\_\{ij,t\}:=\\mathbb\{P\}\\\!\\big\(S\_\{t,ij\}\\neq\\operatorname\{sign\}\(g\_\{t,ij\}\)\\,\\big\|\\,W\_\{t\}\\big\)\.\(28\)\(Whengt,i​j=0g\_\{t,ij\}=0, the definition is immaterial; bounds below hold trivially\.\)

#### C\.4\.2Inner\-product identity for normalized sign directions

\{lemma\}

\[Expected inner product with normalized sign direction\] LetDt:=St/m​nD\_\{t\}:=S\_\{t\}/\\sqrt\{mn\}withSt∈\{−1,0,\+1\}m×nS\_\{t\}\\in\\\{\-1,0,\+1\\\}^\{m\\times n\}\. Then, conditionally onWtW\_\{t\},

𝔼​\[⟨gt,Dt⟩∣Wt\]=1m​n​∑i=1m∑j=1n\|gt,i​j\|​\(1−2​qi​j,t\)\.\\mathbb\{E\}\\big\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\\big\]=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}\|g\_\{t,ij\}\|\\big\(1\-2q\_\{ij,t\}\\big\)\.\(29\)
###### Proof sketch\.

Expand⟨gt,Dt⟩=1m​n​∑i​jgt,i​j​St,i​j\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{ij\}g\_\{t,ij\}S\_\{t,ij\}\. Condition onWtW\_\{t\}so thatgt,i​jg\_\{t,ij\}is fixed, and use𝔼​\[St,i​j∣Wt\]=sign⁡\(gt,i​j\)​\(1−2​qi​j,t\)\\mathbb\{E\}\[S\_\{t,ij\}\\mid W\_\{t\}\]=\\operatorname\{sign\}\(g\_\{t,ij\}\)\\big\(1\-2q\_\{ij,t\}\\big\), becauseSt,i​jS\_\{t,ij\}equals the correct sign with probability\(1−qi​j,t\)\(1\-q\_\{ij,t\}\)and the wrong sign with probabilityqi​j,tq\_\{ij,t\}\. Full details are in Appendix[C\.9\.2](https://arxiv.org/html/2605.16311#A3.SS9.SSS2)\. ∎

#### C\.4\.3Boundingqi​j,tq\_\{ij,t\}for gradient\-sign Sign\-Muon

The next lemma is the standard Markov\+Jensen bound used in signSGD \(applied entrywise to matrices\)\.

\{lemma\}

\[Markov\+Jensen sign\-failure bound \(single worker\)\] Assume Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)and setSt:=sign⁡\(G~t\)S\_\{t\}:=\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t\}\)\. Then for any entry\(i,j\)\(i,j\)withgt,i​j≠0g\_\{t,ij\}\\neq 0,

qi​j,t=ℙ​\(sign⁡\(G~t,i​j\)≠sign⁡\(gt,i​j\)\|Wt\)≤σi​jnb​\|gt,i​j\|\.q\_\{ij,t\}=\\mathbb\{P\}\\\!\\big\(\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t,ij\}\)\\neq\\operatorname\{sign\}\(g\_\{t,ij\}\)\\,\\big\|\\,W\_\{t\}\\big\)\\;\\leq\\;\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\\,\|g\_\{t,ij\}\|\}\.\(30\)
###### Proof sketch\.

A sign error requires\|G~t,i​j−gt,i​j\|≥\|gt,i​j\|\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\geq\|g\_\{t,ij\}\|\. Apply Markov’s inequality to\|G~t,i​j−gt,i​j\|\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|, then Jensen/Cauchy–Schwarz to relate𝔼​\|G~t,i​j−gt,i​j\|\\mathbb\{E\}\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|to the variance boundVar⁡\(G~t,i​j∣Wt\)≤σi​j2/nb\\operatorname\{Var\}\(\\widetilde\{G\}\_\{t,ij\}\\mid W\_\{t\}\)\\leq\\sigma\_\{ij\}^\{2\}/n\_\{b\}\. A complete step\-by\-step proof is in Appendix[C\.9\.3](https://arxiv.org/html/2605.16311#A3.SS9.SSS3)\. ∎

#### C\.4\.4Boundingqi​j,tq\_\{ij,t\}for majority vote

The next lemma formalizes the classical “1/M1/\\sqrt\{M\}variance reduction” for majority vote under unimodal symmetric noise, as established in signSGD\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\. We state a version directly suitable for our matrix\-entry setting\.

\{lemma\}

\[Majority vote improves sign reliability under unimodal symmetric noise\] Assume Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. LetSt,i​j\(1\),…,St,i​j\(M\)S\_\{t,ij\}^\{\(1\)\},\\dots,S\_\{t,ij\}^\{\(M\)\}be independent across workers conditioned onWtW\_\{t\}, withSt,i​j\(m\)=sign⁡\(G~t,i​j\(m\)\)S\_\{t,ij\}^\{\(m\)\}=\\operatorname\{sign\}\(\\widetilde\{G\}^\{\(m\)\}\_\{t,ij\}\)andG~t,i​j\(m\)\\widetilde\{G\}^\{\(m\)\}\_\{t,ij\}satisfying the unimodal symmetry condition and variance bound \([22](https://arxiv.org/html/2605.16311#A3.E22)\) \(with the sameσi​j\\sigma\_\{ij\}andnbn\_\{b\}\)\. LetS¯t,i​j\\bar\{S\}\_\{t,ij\}be the majority vote \([25](https://arxiv.org/html/2605.16311#A3.E25)\)\. Then forgt,i​j≠0g\_\{t,ij\}\\neq 0,

qi​j,tMV:=ℙ​\(S¯t,i​j≠sign⁡\(gt,i​j\)\|Wt\)≤1M⋅σi​jnb​\|gt,i​j\|\.q^\{\\mathrm\{MV\}\}\_\{ij,t\}:=\\mathbb\{P\}\\\!\\big\(\\bar\{S\}\_\{t,ij\}\\neq\\operatorname\{sign\}\(g\_\{t,ij\}\)\\,\\big\|\\,W\_\{t\}\\big\)\\;\\leq\\;\\frac\{1\}\{\\sqrt\{M\}\}\\cdot\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\\,\|g\_\{t,ij\}\|\}\.\(31\)
###### Proof sketch\.

This is the matrix\-entry analogue of Lemma D\.1 and Theorem 2\(b\) in signSGD\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\. The proof uses \(i\) Gauss’ inequality to upper bound the single\-worker sign\-failure probability under unimodal symmetry, and \(ii\) a repetition\-code/majority\-decoding argument with a binomial tail bound \(e\.g\. via Cantelli’s inequality or standard Chernoff bounds\) to show that the majority vote reduces the effective failure probability by a factor of order1/M1/\\sqrt\{M\}in the final progress bound\. We provide a complete, self\-contained proof specialized to \([31](https://arxiv.org/html/2605.16311#A3.E31)\) in Appendix[C\.9\.4](https://arxiv.org/html/2605.16311#A3.SS9.SSS4)\. ∎

### C\.5Main convergence theorems for Sign\-Muon

We measure progress using theℓ1\\ell\_\{1\}\-geometry stationarity proxy

𝒢T:=1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]\.\\mathcal\{G\}\_\{T\}:=\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\.\(32\)This matches the signSGD analysis \(up to matrix reshaping\) but with*spectral*smoothness in the descent lemma\.

#### C\.5\.1A generic theorem parameterized by sign\-error probabilities

\{theorem\}

\[Generic Sign\-Muon bound in spectral geometry\] Assume Assumptions[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)–[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Consider the update \([24](https://arxiv.org/html/2605.16311#A3.E24)\) with directionDt=St/m​nD\_\{t\}=S\_\{t\}/\\sqrt\{mn\}whereSt∈\{−1,0,\+1\}m×nS\_\{t\}\\in\\\{\-1,0,\+1\\\}^\{m\\times n\}\. Letqi​j,tq\_\{ij,t\}be defined as in \([28](https://arxiv.org/html/2605.16311#A3.E28)\)\. Supposeηt≡η\\eta\_\{t\}\\equiv\\etais constant and satisfiesη\>0\\eta\>0\. Then

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗η​T\+L∗2​η\+2T​∑t=0T−1𝔼​\[1m​n​∑i,j\|gt,i​j\|​qi​j,t\]\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{2\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\right\]\.\(33\)
###### Proof sketch\.

Apply the spectral descent lemma \([27](https://arxiv.org/html/2605.16311#A3.E27)\) withDt=St/m​nD\_\{t\}=S\_\{t\}/\\sqrt\{mn\}, so‖Dt‖op≤1\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. Then take conditional expectation givenWtW\_\{t\}and invoke Lemma[C\.4\.2](https://arxiv.org/html/2605.16311#A3.SS4.SSS2)to express𝔼​\[⟨gt,Dt⟩∣Wt\]\\mathbb\{E\}\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\]in terms of\(1−2​qi​j,t\)\(1\-2q\_\{ij,t\}\)\. Rearrange to isolate‖gt‖1/m​n\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}, sum overt=0,…,T−1t=0,\\dots,T\-1, and telescope using Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Full details are in Appendix[C\.9\.5](https://arxiv.org/html/2605.16311#A3.SS9.SSS5)\. ∎

#### C\.5\.2Specialization: single\-worker gradient\-sign Sign\-Muon

\{theorem\}

\[Single\-worker Sign\-Muon \(gradient\-sign instantiation\)\] Assume Assumptions[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)–[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Run Sign\-Muon forTTiterations with

St:=sign⁡\(G~t\),Dt:=1m​n​St,Wt\+1=Wt−η​Dt,S\_\{t\}:=\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t\}\),\\qquad D\_\{t\}:=\\frac\{1\}\{\\sqrt\{mn\}\}S\_\{t\},\\qquad W\_\{t\+1\}=W\_\{t\}\-\\eta D\_\{t\},whereη\>0\\eta\>0is constant and eachG~t\\widetilde\{G\}\_\{t\}uses a mini\-batch of sizenbn\_\{b\}\. Then

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗η​T\+L∗2​η\+2​‖σ‖1m​n​nb\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{2\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,n\_\{b\}\}\}\.\(34\)Choosing

η:=2​\(f​\(W0\)−f∗\)L∗​Tandnb:=T\\eta:=\\sqrt\{\\frac\{2\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{L\_\{\\ast\}T\}\}\\qquad\\text\{and\}\\qquad n\_\{b\}:=Tyields the rate

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤L∗​\(f​\(W0\)−f∗\)T\+2​‖σ‖1m​n​T\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\;\\leq\\;\\sqrt\{\\frac\{L\_\{\\ast\}\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{T\}\}\+\\frac\{2\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,T\}\}\.\(35\)
###### Proof sketch\.

Apply Theorem[C\.5\.1](https://arxiv.org/html/2605.16311#A3.SS5.SSS1)and bound the final “sign error” term using Lemma[C\.4\.3](https://arxiv.org/html/2605.16311#A3.SS4.SSS3):\|gt,i​j\|​qi​j,t≤σi​j/nb\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\leq\\sigma\_\{ij\}/\\sqrt\{n\_\{b\}\}\. Summing overi,ji,jgives∑i​j\|gt,i​j\|​qi​j,t≤‖σ‖1/nb\\sum\_\{ij\}\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\leq\\left\\lVert\\sigma\\right\\rVert\_\{1\}/\\sqrt\{n\_\{b\}\}\. Then optimizeη\\etafor the\(f​\(W0\)−f∗\)/\(η​T\)\+\(L∗/2\)​η\(f\(W\_\{0\}\)\-f^\{\\ast\}\)/\(\\eta T\)\+\(L\_\{\\ast\}/2\)\\etatrade\-off\. See Appendix[C\.9\.6](https://arxiv.org/html/2605.16311#A3.SS9.SSS6)\. ∎

#### C\.5\.3Specialization: distributed majority vote Sign\-Muon

\{theorem\}

\[Distributed Sign\-Muon with majority vote\] Assume Assumptions[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)–[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. ConsiderMMworkers, each forming an unbiased mini\-batch gradientG~t\(m\)\\widetilde\{G\}\_\{t\}^\{\(m\)\}of sizenbn\_\{b\}and sendingSt\(m\):=sign⁡\(G~t\(m\)\)S\_\{t\}^\{\(m\)\}:=\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t\}^\{\(m\)\}\)\. LetS¯t\\bar\{S\}\_\{t\}be the majority vote \([25](https://arxiv.org/html/2605.16311#A3.E25)\) and set

Dt:=1m​n​S¯t,Wt\+1=Wt−η​Dt\.D\_\{t\}:=\\frac\{1\}\{\\sqrt\{mn\}\}\\,\\bar\{S\}\_\{t\},\\qquad W\_\{t\+1\}=W\_\{t\}\-\\eta D\_\{t\}\.Then for constantη\>0\\eta\>0,

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗η​T\+L∗2​η\+2​‖σ‖1m​n​M​nb\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{2\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,M\\,n\_\{b\}\}\}\.\(36\)Withη:=2​\(f​\(W0\)−f∗\)L∗​T\\eta:=\\sqrt\{\\frac\{2\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{L\_\{\\ast\}T\}\}andnb:=Tn\_\{b\}:=T, this becomes

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤L∗​\(f​\(W0\)−f∗\)T\+2​‖σ‖1m​n​M​T\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\;\\leq\\;\\sqrt\{\\frac\{L\_\{\\ast\}\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{T\}\}\+\\frac\{2\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,M\\,T\}\}\.\(37\)
###### Proof sketch\.

Same as Theorem[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2), but use Lemma[C\.4\.4](https://arxiv.org/html/2605.16311#A3.SS4.SSS4)in place of Lemma[C\.4\.3](https://arxiv.org/html/2605.16311#A3.SS4.SSS3)\. The only difference relative to signSGD is that the smoothness constant in the descent lemma is spectral \(L∗L\_\{\\ast\}\), because the update direction is normalized to have‖Dt‖op≤1\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. See Appendix[C\.9\.7](https://arxiv.org/html/2605.16311#A3.SS9.SSS7)\. ∎

\{remark\}

\[What improved relative to signSGD?\] Theorems[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)–[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)mirror signSGD’sℓ1\\ell\_\{1\}\-based rates\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\], but with the curvature term governed by*spectral*smoothnessL∗L\_\{\\ast\}\(as in Muon’s analysis\) rather than anℓ∞\\ell\_\{\\infty\}\-to\-ℓ1\\ell\_\{1\}smoothness constant\. When the Hessian has blockwise\-diagonal / low\-effective\-rank structure, Muon\-type results relateL∗L\_\{\\ast\}to a*nuclear norm*of a block\-Lipschitz matrix, which can be substantially smaller than the corresponding Frobenius\-geometry constant; this improves constants in theO​\(1/T\)O\(1/\\sqrt\{T\}\)rate\[[31](https://arxiv.org/html/2605.16311#bib.bib21)\]\.

### C\.6Full Muon and the role of the polar decomposition

We now formalize the role of the polar decomposition in spectral\-geometry descent and compare “full Muon” \(polar directions\) against Sign\-Muon \(sign\-quantized directions\)\.

#### C\.6\.1Polar decomposition as a spectral steepest\-descent direction

\{definition\}

\[Polar factor\] LetX∈ℝm×nX\\in\\mathbb\{R\}^\{m\\times n\}\. A \(thin\) singular value decomposition isX=U​Σ​V⊤X=U\\Sigma V^\{\\top\}, whereU∈ℝm×rU\\in\\mathbb\{R\}^\{m\\times r\},V∈ℝn×rV\\in\\mathbb\{R\}^\{n\\times r\}have orthonormal columns andΣ∈ℝr×r\\Sigma\\in\\mathbb\{R\}^\{r\\times r\}is diagonal with positive entries, withr=rank⁡\(X\)r=\\operatorname\{rank\}\(X\)\. A*polar factor*\(also called the orthogonal factor\) ofXXis

polar⁡\(X\):=U​V⊤\.\\operatorname\{polar\}\(X\):=UV^\{\\top\}\.It satisfies‖polar⁡\(X\)‖op=1\\left\\lVert\\operatorname\{polar\}\(X\)\\right\\rVert\_\{\\mathrm\{op\}\}=1and is the solution of

polar⁡\(X\)∈arg​minQ:‖Q‖op≤1⁡‖X−Q‖F\.\\operatorname\{polar\}\(X\)\\in\\operatorname\*\{arg\\,min\}\_\{Q:\\ \\left\\lVert Q\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\left\\lVert X\-Q\\right\\rVert\_\{\\mathrm\{F\}\}\.
\{proposition\}

\[Dual optimality of the polar factor\] For anyG∈ℝm×nG\\in\\mathbb\{R\}^\{m\\times n\},

max‖D‖op≤1⁡⟨G,D⟩=‖G‖∗\.\\max\_\{\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\left\\langle G,D\\right\\rangle=\\left\\lVert G\\right\\rVert\_\{\*\}\.Moreover, ifG=U​Σ​V⊤G=U\\Sigma V^\{\\top\}is an SVD, thenD⋆:=U​V⊤=polar⁡\(G\)D^\{\\star\}:=UV^\{\\top\}=\\operatorname\{polar\}\(G\)achieves the maximum, and

⟨G,polar⁡\(G\)⟩=‖G‖∗\.\\left\\langle G,\\operatorname\{polar\}\(G\)\\right\\rangle=\\left\\lVert G\\right\\rVert\_\{\*\}\.\(38\)
###### Proof sketch\.

This is the standard nuclear/spectral duality \([19](https://arxiv.org/html/2605.16311#A3.E19)\)\. For the attainment claim, expand⟨U​Σ​V⊤,D⟩=⟨Σ,U⊤​D​V⟩\\left\\langle U\\Sigma V^\{\\top\},D\\right\\rangle=\\left\\langle\\Sigma,U^\{\\top\}DV\\right\\rangleand note that‖U⊤​D​V‖op≤‖D‖op≤1\\left\\lVert U^\{\\top\}DV\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1, so the trace is maximized by choosingU⊤​D​V=IU^\{\\top\}DV=Ion the support ofΣ\\Sigma, i\.e\.D=U​V⊤D=UV^\{\\top\}\. Detailed proof is in Appendix[C\.9\.8](https://arxiv.org/html/2605.16311#A3.SS9.SSS8)\. ∎

#### C\.6\.2Deterministic “Muon” step and its convergence in nuclear norm

Consider the*deterministic*update

Wt\+1=Wt−η​Qt,Qt:=polar⁡\(gt\)=polar⁡\(∇f​\(Wt\)\)\.W\_\{t\+1\}=W\_\{t\}\-\\eta\\,Q\_\{t\},\\qquad Q\_\{t\}:=\\operatorname\{polar\}\(g\_\{t\}\)=\\operatorname\{polar\}\(\\nabla f\(W\_\{t\}\)\)\.\(39\)This is the spectral\-geometry analogue of gradient descent: it chooses the steepest descent direction over the unit spectral\-norm ball\.

\{theorem\}

\[Deterministic Muon step:O​\(1/T\)O\(1/\\sqrt\{T\}\)nuclear\-norm stationarity\] Assume Assumptions[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)–[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Let\{Wt\}\\\{W\_\{t\}\\\}be generated by \([39](https://arxiv.org/html/2605.16311#A3.E39)\) with constantη\>0\\eta\>0\. Then

1T​∑t=0T−1𝔼​\[‖gt‖∗\]≤f​\(W0\)−f∗η​T\+L∗2​η\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\big\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\big\]\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\.\(40\)Choosingη:=2​\(f​\(W0\)−f∗\)L∗​T\\eta:=\\sqrt\{\\frac\{2\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{L\_\{\\ast\}T\}\}gives

1T​∑t=0T−1𝔼​\[‖gt‖∗\]≤L∗​\(f​\(W0\)−f∗\)T\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\big\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\big\]\\;\\leq\\;\\sqrt\{\\frac\{L\_\{\\ast\}\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{T\}\}\.\(41\)
###### Proof sketch\.

Apply Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)withD=QtD=Q\_\{t\}and‖Qt‖op=1\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}=1\. Then use Proposition[C\.6\.1](https://arxiv.org/html/2605.16311#A3.SS6.SSS1)to replace the inner product⟨gt,Qt⟩\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangleby‖gt‖∗\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\. Sum overttand telescope using Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Full details are in Appendix[C\.9\.9](https://arxiv.org/html/2605.16311#A3.SS9.SSS9)\. ∎

\{remark\}

\[Muon guarantees implyℓ1\\ell\_\{1\}\-geometry stationarity\] By \([20](https://arxiv.org/html/2605.16311#A3.E20)\),‖gt‖1/m​n≤‖gt‖∗\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}\\leq\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}, hence Theorem[C\.6\.2](https://arxiv.org/html/2605.16311#A3.SS6.SSS2)implies the sameO​\(1/T\)O\(1/\\sqrt\{T\}\)rate for1T​∑t𝔼​\[‖gt‖1/m​n\]\\frac\{1\}\{T\}\\sum\_\{t\}\\mathbb\{E\}\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}\]in the deterministic setting\. In that sense, the nuclear\-norm stationarity guarantee is*strictly stronger*\.

### C\.7Newton–Schulz approximation and inexact polar factors

We now formalize how approximation error from Newton–Schulz iterations affects convergence guarantees\.

#### C\.7\.1Inexact polar steps

\{theorem\}

\[Inexact Muon step\] Assume Assumptions[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)–[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)\. Consider an update

Wt\+1=Wt−η​Qt,W\_\{t\+1\}=W\_\{t\}\-\\eta Q\_\{t\},whereQtQ\_\{t\}satisfies‖Qt‖op≤1\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1and

‖Qt−polar⁡\(gt\)‖op≤εt\.\\left\\lVert Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\varepsilon\_\{t\}\.\(42\)Then for any constantη\>0\\eta\>0,

1T​∑t=0T−1𝔼​\[‖gt‖∗\]≤f​\(W0\)−f∗η​T\+L∗2​η\+1T​∑t=0T−1𝔼​\[εt​‖gt‖∗\]\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\big\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\big\]\\;\\leq\\;\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\big\[\\varepsilon\_\{t\}\\,\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\big\]\.\(43\)In particular, ifεt≤ε¯<1\\varepsilon\_\{t\}\\leq\\bar\{\\varepsilon\}<1for alltt, then

1T​∑t=0T−1𝔼​\[‖gt‖∗\]≤11−ε¯​\(f​\(W0\)−f∗η​T\+L∗2​η\)\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\big\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\big\]\\;\\leq\\;\\frac\{1\}\{1\-\\bar\{\\varepsilon\}\}\\left\(\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\\right\)\.
###### Proof sketch\.

Use Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)and decompose⟨gt,Qt⟩=⟨gt,polar⁡\(gt\)⟩\+⟨gt,Qt−polar⁡\(gt\)⟩\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle=\\left\\langle g\_\{t\},\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle\+\\left\\langle g\_\{t\},Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle\. The first term equals‖gt‖∗\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}by \([38](https://arxiv.org/html/2605.16311#A3.E38)\)\. The second term is bounded in absolute value by‖gt‖∗​‖Qt−polar⁡\(gt\)‖op≤εt​‖gt‖∗\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\left\\lVert Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\varepsilon\_\{t\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}via duality\. Telescope as usual\. Full proof is in Appendix[C\.9\.10](https://arxiv.org/html/2605.16311#A3.SS9.SSS10)\. ∎

#### C\.7\.2Newton–Schulz iteration for the polar factor

We analyze the classical Newton–Schulz iteration \(as used in Muon and in the main text\)\.

Algorithm 6Newton–Schulz polar iteration \(idealized\)1:Input:Matrix

X∈ℝm×nX\\in\\mathbb\{R\}^\{m\\times n\}and iteration count

K≥0K\\geq 0\.

2:Choose scaling

α\>0\\alpha\>0and set

Y0←X/αY\_\{0\}\\leftarrow X/\\alpha\.

3:for

k=0,1,…,K−1k=0,1,\\dots,K\-1do

4:

Yk\+1←12​Yk​\(3​I−Yk⊤​Yk\)Y\_\{k\+1\}\\leftarrow\\frac\{1\}\{2\}Y\_\{k\}\\big\(3I\-Y\_\{k\}^\{\\top\}Y\_\{k\}\\big\)\.

5:endfor

6:Return

YKY\_\{K\}\.

\{theorem\}

\[Quadratic convergence of Newton–Schulz to the polar factor\] LetX∈ℝm×nX\\in\\mathbb\{R\}^\{m\\times n\}and letQ:=polar⁡\(X\)Q:=\\operatorname\{polar\}\(X\)\. Assumeα\>0\\alpha\>0is chosen so that

‖I−\(X/α\)⊤​\(X/α\)‖op≤ρfor some​ρ∈\(0,1\)\.\\left\\lVert I\-\(X/\\alpha\)^\{\\top\}\(X/\\alpha\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho\\qquad\\text\{for some \}\\rho\\in\(0,1\)\.\(44\)LetYKY\_\{K\}be the output of Algorithm[6](https://arxiv.org/html/2605.16311#alg6)\. ThenYKY\_\{K\}satisfies‖YK‖op≤1\\left\\lVert Y\_\{K\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1and

‖YK−Q‖op≤ρ2K\.\\left\\lVert Y\_\{K\}\-Q\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho^\{2^\{K\}\}\.\(45\)
###### Proof sketch\.

The Newton–Schulz map is a matrix analogue of the scalar iteration for1/z1/\\sqrt\{z\}\. Under the scaling condition \([44](https://arxiv.org/html/2605.16311#A3.E44)\), one can show that the error matrixEk:=I−Yk⊤​YkE\_\{k\}:=I\-Y\_\{k\}^\{\\top\}Y\_\{k\}satisfies the recursionEk\+1=Ek2E\_\{k\+1\}=E\_\{k\}^\{2\}, hence‖Ek\+1‖op≤‖Ek‖op2\\left\\lVert E\_\{k\+1\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert E\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}, giving‖Ek‖op≤ρ2k\\left\\lVert E\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho^\{2^\{k\}\}\. A standard argument then transfers this to‖Yk−Q‖op\\left\\lVert Y\_\{k\}\-Q\\right\\rVert\_\{\\mathrm\{op\}\}\. A complete proof is in Appendix[C\.9\.11](https://arxiv.org/html/2605.16311#A3.SS9.SSS11); see also Higham’s monograph on matrix functions\[[9](https://arxiv.org/html/2605.16311#bib.bib25)\]and discussions in Muon\[[31](https://arxiv.org/html/2605.16311#bib.bib21)\]\. ∎

### C\.8Comparing full Muon vs Sign\-Muon

We now summarize what the theory implies about the advantages and limitations of Sign\-Muon relative to \(i\) signSGD and \(ii\) full Muon\.

#### C\.8\.1Stationarity measures and what improves

##### Full Muon\.

The deterministic polar step \([39](https://arxiv.org/html/2605.16311#A3.E39)\) drives the*nuclear norm*of the gradient to0at rateO​\(1/T\)O\(1/\\sqrt\{T\}\)\(Theorem[C\.6\.2](https://arxiv.org/html/2605.16311#A3.SS6.SSS2)\)\. Because‖g‖1/m​n≤‖g‖∗\\left\\lVert g\\right\\rVert\_\{1\}/\\sqrt\{mn\}\\leq\\left\\lVert g\\right\\rVert\_\{\*\}, this is a strictly stronger stationarity guarantee than theℓ1\\ell\_\{1\}\-proxy used for sign methods\.

##### Sign\-Muon\.

Sign\-Muon in Theorems[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)–[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)drives theℓ1\\ell\_\{1\}\-proxy‖gt‖1/m​n\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}to0atO​\(1/T\)O\(1/\\sqrt\{T\}\)but with an additional*noise term*proportional to‖σ‖1/m​n​nb\\left\\lVert\\sigma\\right\\rVert\_\{1\}/\\sqrt\{mn\\,n\_\{b\}\}\(and improved to‖σ‖1/m​n​M​nb\\left\\lVert\\sigma\\right\\rVert\_\{1\}/\\sqrt\{mn\\,M\\,n\_\{b\}\}under unimodal symmetric noise and majority vote\)\.

##### What improves relative to signSGD\.

The improvement is in the curvature term: signSGD’s analysis uses anℓ∞→ℓ1\\ell\_\{\\infty\}\\\!\\to\\\!\\ell\_\{1\}smoothness constant \(typically denoted‖L~‖1\\\|\\widetilde\{L\}\\\|\_\{1\}in\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\)\. Sign\-Muon normalizes the update to unit*spectral norm*and thus uses the*spectral smoothness*constantL∗L\_\{\\ast\}\. When the Hessian exhibits low\-effective\-rank structure across matrix blocks, Muon\-type results relateL∗L\_\{\\ast\}to a nuclear norm of blockwise Lipschitz constants, which may be substantially smaller than Frobenius/coordinatewise constants\[[31](https://arxiv.org/html/2605.16311#bib.bib21)\]\.

#### C\.8\.2Role of polar decomposition

The polar decomposition enters the theory in two complementary ways:

1. 1\.Optimality of the polar direction in spectral geometry\.Proposition[C\.6\.1](https://arxiv.org/html/2605.16311#A3.SS6.SSS1)showspolar⁡\(gt\)\\operatorname\{polar\}\(g\_\{t\}\)maximizes⟨gt,D⟩\\left\\langle g\_\{t\},D\\right\\rangleamong all directions with‖D‖op≤1\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. This yields the clean descent⟨gt,polar⁡\(gt\)⟩=‖gt‖∗\\left\\langle g\_\{t\},\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle=\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}and the nuclear\-norm stationarity rate\.
2. 2\.Practical orthogonalization with 1\-bit communication\.After majority vote, the server broadcastsS¯t∈\{−1,\+1\}m×n\\bar\{S\}\_\{t\}\\in\\\{\-1,\+1\\\}^\{m\\times n\}\(1\-bit per entry\)\. Each worker may computeQt=polar⁡\(S¯t\)Q\_\{t\}=\\operatorname\{polar\}\(\\bar\{S\}\_\{t\}\)locally \(e\.g\. via Newton–Schulz\) and step withQtQ\_\{t\}\. This retains 1\-bit communication and imports Muon\-like orthogonalized steps\. Theorems[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)–[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)already guarantee descent forDt=S¯t/m​nD\_\{t\}=\\bar\{S\}\_\{t\}/\\sqrt\{mn\}; usingQtQ\_\{t\}can improve alignment in practice, while preserving the spectral\-norm control‖Qt‖op=1\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}=1\.

#### C\.8\.3A conservative theoretical comparison

The cleanest guarantee for Muon is the deterministic nuclear\-norm result \(Theorem[C\.6\.2](https://arxiv.org/html/2605.16311#A3.SS6.SSS2)\)\. The cleanest guarantee for Sign\-Muon is the stochasticℓ1\\ell\_\{1\}\-proxy result \(Theorem[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)and Theorem[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)\)\.

A direct*ordering*between these bounds is not generally possible, because they control different stationarity measures and because Sign\-Muon uses sign compression \(hence a noise floor term appears\)\. However, two implications hold unconditionally:

- •If full Muon achieves1T​∑t𝔼​\[‖gt‖∗\]→0\\frac\{1\}\{T\}\\sum\_\{t\}\\mathbb\{E\}\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\]\\to 0, then automatically1T​∑t𝔼​\[‖gt‖1/m​n\]→0\\frac\{1\}\{T\}\\sum\_\{t\}\\mathbb\{E\}\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}\]\\to 0by \([20](https://arxiv.org/html/2605.16311#A3.E20)\)\.
- •Sign\-Muon inherits the1/M1/\\sqrt\{M\}*distributed speedup*from signSGD under unimodal symmetric noise \(Theorem[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)\), while maintaining spectral geometry in the descent lemma\.

### C\.9Detailed proofs

#### C\.9\.1Proof of Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)

###### Proof\.

FixW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}and a directionD∈ℝm×nD\\in\\mathbb\{R\}^\{m\\times n\}\. Define the scalar functionϕ:\[0,1\]→ℝ\\phi:\[0,1\]\\to\\mathbb\{R\}by

ϕ​\(τ\):=f​\(W−τ​η​D\)\.\\phi\(\\tau\):=f\(W\-\\tau\\eta D\)\.By the chain rule,

ϕ′​\(τ\)=⟨∇f​\(W−τ​η​D\),−η​D⟩=−η​⟨∇f​\(W−τ​η​D\),D⟩\.\\phi^\{\\prime\}\(\\tau\)=\\left\\langle\\nabla f\(W\-\\tau\\eta D\),\-\\eta D\\right\\rangle=\-\\eta\\,\\left\\langle\\nabla f\(W\-\\tau\\eta D\),D\\right\\rangle\.Integrating from0to11yields

f​\(W−η​D\)−f​\(W\)\\displaystyle f\(W\-\\eta D\)\-f\(W\)=ϕ​\(1\)−ϕ​\(0\)=∫01ϕ′​\(τ\)​dτ\\displaystyle=\\phi\(1\)\-\\phi\(0\)=\\int\_\{0\}^\{1\}\\phi^\{\\prime\}\(\\tau\)\\,\\mathrm\{d\}\\tau=−η​∫01⟨∇f​\(W−τ​η​D\),D⟩​dτ\.\\displaystyle=\-\\eta\\int\_\{0\}^\{1\}\\left\\langle\\nabla f\(W\-\\tau\\eta D\),D\\right\\rangle\\,\\mathrm\{d\}\\tau\.Add and subtract∇f​\(W\)\\nabla f\(W\)inside the inner product:

f​\(W−η​D\)−f​\(W\)\\displaystyle f\(W\-\\eta D\)\-f\(W\)=−η​⟨∇f​\(W\),D⟩−η​∫01⟨∇f​\(W−τ​η​D\)−∇f​\(W\),D⟩​dτ\.\\displaystyle=\-\\eta\\,\\left\\langle\\nabla f\(W\),D\\right\\rangle\-\\eta\\int\_\{0\}^\{1\}\\left\\langle\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\),D\\right\\rangle\\,\\mathrm\{d\}\\tau\.We bound the remainder term using nuclear/spectral duality:

⟨A,D⟩≤‖A‖∗​‖D‖op\.\\left\\langle A,D\\right\\rangle\\leq\\left\\lVert A\\right\\rVert\_\{\*\}\\,\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\.Therefore,

\|⟨∇f​\(W−τ​η​D\)−∇f​\(W\),D⟩\|≤‖∇f​\(W−τ​η​D\)−∇f​\(W\)‖∗​‖D‖op\.\\left\|\\left\\langle\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\),D\\right\\rangle\\right\|\\leq\\left\\lVert\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\)\\right\\rVert\_\{\*\}\\,\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\.By Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2)applied toW′=W−τ​η​DW^\{\\prime\}=W\-\\tau\\eta D,

‖∇f​\(W−τ​η​D\)−∇f​\(W\)‖∗≤L∗​‖\(W−τ​η​D\)−W‖op=L∗​τ​η​‖D‖op\.\\left\\lVert\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\)\\right\\rVert\_\{\*\}\\leq L\_\{\\ast\}\\left\\lVert\(W\-\\tau\\eta D\)\-W\\right\\rVert\_\{\\mathrm\{op\}\}=L\_\{\\ast\}\\tau\\eta\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\.Combining the last two displays gives

\|⟨∇f​\(W−τ​η​D\)−∇f​\(W\),D⟩\|≤L∗​τ​η​‖D‖op2\.\\left\|\\left\\langle\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\),D\\right\\rangle\\right\|\\leq L\_\{\\ast\}\\tau\\eta\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.Hence

−η​∫01⟨∇f​\(W−τ​η​D\)−∇f​\(W\),D⟩​dτ\\displaystyle\-\\eta\\int\_\{0\}^\{1\}\\left\\langle\\nabla f\(W\-\\tau\\eta D\)\-\\nabla f\(W\),D\\right\\rangle\\,\\mathrm\{d\}\\tau≤η​∫01L∗​τ​η​‖D‖op2​dτ=L∗2​η2​‖D‖op2\.\\displaystyle\\leq\\eta\\int\_\{0\}^\{1\}L\_\{\\ast\}\\tau\\eta\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\\,\\mathrm\{d\}\\tau=\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.Therefore,

f​\(W−η​D\)−f​\(W\)≤−η​⟨∇f​\(W\),D⟩\+L∗2​η2​‖D‖op2,f\(W\-\\eta D\)\-f\(W\)\\leq\-\\eta\\,\\left\\langle\\nabla f\(W\),D\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\},which is exactly \([26](https://arxiv.org/html/2605.16311#A3.E26)\)\. If‖D‖op≤1\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1, we obtain \([27](https://arxiv.org/html/2605.16311#A3.E27)\)\. ∎

#### C\.9\.2Proof of Lemma[C\.4\.2](https://arxiv.org/html/2605.16311#A3.SS4.SSS2)

###### Proof\.

RecallDt=St/m​nD\_\{t\}=S\_\{t\}/\\sqrt\{mn\}and⟨gt,Dt⟩=∑i​jgt,i​j​Dt,i​j\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle=\\sum\_\{ij\}g\_\{t,ij\}D\_\{t,ij\}\. Thus

⟨gt,Dt⟩=1m​n​∑i=1m∑j=1ngt,i​j​St,i​j\.\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}g\_\{t,ij\}\\,S\_\{t,ij\}\.Fixttand condition onWtW\_\{t\}, sogtg\_\{t\}is fixed\. Taking conditional expectation gives

𝔼​\[⟨gt,Dt⟩∣Wt\]=1m​n​∑i=1m∑j=1ngt,i​j​𝔼​\[St,i​j∣Wt\]\.\\mathbb\{E\}\\big\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\\big\]=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}g\_\{t,ij\}\\,\\mathbb\{E\}\[S\_\{t,ij\}\\mid W\_\{t\}\]\.Now fix an entry\(i,j\)\(i,j\)and assumegt,i​j≠0g\_\{t,ij\}\\neq 0\. Letsi​j:=sign⁡\(gt,i​j\)∈\{−1,\+1\}s\_\{ij\}:=\\operatorname\{sign\}\(g\_\{t,ij\}\)\\in\\\{\-1,\+1\\\}\. By definition ofqi​j,tq\_\{ij,t\}in \([28](https://arxiv.org/html/2605.16311#A3.E28)\),

ℙ​\(St,i​j=si​j∣Wt\)=1−qi​j,t,ℙ​\(St,i​j=−si​j∣Wt\)=qi​j,t\.\\mathbb\{P\}\(S\_\{t,ij\}=s\_\{ij\}\\mid W\_\{t\}\)=1\-q\_\{ij,t\},\\qquad\\mathbb\{P\}\(S\_\{t,ij\}=\-s\_\{ij\}\\mid W\_\{t\}\)=q\_\{ij,t\}\.Hence

𝔼​\[St,i​j∣Wt\]=\(1−qi​j,t\)​si​j\+qi​j,t​\(−si​j\)=si​j​\(1−2​qi​j,t\)\.\\mathbb\{E\}\[S\_\{t,ij\}\\mid W\_\{t\}\]=\(1\-q\_\{ij,t\}\)\\,s\_\{ij\}\+q\_\{ij,t\}\\,\(\-s\_\{ij\}\)=s\_\{ij\}\(1\-2q\_\{ij,t\}\)\.Therefore

gt,i​j​𝔼​\[St,i​j∣Wt\]=gt,i​j​sign⁡\(gt,i​j\)​\(1−2​qi​j,t\)=\|gt,i​j\|​\(1−2​qi​j,t\)\.g\_\{t,ij\}\\,\\mathbb\{E\}\[S\_\{t,ij\}\\mid W\_\{t\}\]=g\_\{t,ij\}\\,\\operatorname\{sign\}\(g\_\{t,ij\}\)\(1\-2q\_\{ij,t\}\)=\|g\_\{t,ij\}\|\(1\-2q\_\{ij,t\}\)\.Substituting into the conditional expectation expansion yields

𝔼​\[⟨gt,Dt⟩∣Wt\]=1m​n​∑i=1m∑j=1n\|gt,i​j\|​\(1−2​qi​j,t\),\\mathbb\{E\}\\big\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\\big\]=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}\|g\_\{t,ij\}\|\(1\-2q\_\{ij,t\}\),which is \([29](https://arxiv.org/html/2605.16311#A3.E29)\)\. ∎

#### C\.9\.3Proof of Lemma[C\.4\.3](https://arxiv.org/html/2605.16311#A3.SS4.SSS3)

###### Proof\.

Fix\(i,j\)\(i,j\)and condition onWtW\_\{t\}\. Assumegt,i​j≠0g\_\{t,ij\}\\neq 0\. A sign mismatch occurs only ifG~t,i​j\\widetilde\{G\}\_\{t,ij\}has opposite sign togt,i​jg\_\{t,ij\}, which implies

\|G~t,i​j−gt,i​j\|≥\|gt,i​j\|\.\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\geq\|g\_\{t,ij\}\|\.Therefore,

qi​j,t\\displaystyle q\_\{ij,t\}=ℙ​\(sign⁡\(G~t,i​j\)≠sign⁡\(gt,i​j\)\|Wt\)\\displaystyle=\\mathbb\{P\}\\\!\\big\(\\operatorname\{sign\}\(\\widetilde\{G\}\_\{t,ij\}\)\\neq\\operatorname\{sign\}\(g\_\{t,ij\}\)\\,\\big\|\\,W\_\{t\}\\big\)≤ℙ​\(\|G~t,i​j−gt,i​j\|≥\|gt,i​j\|\|Wt\)\.\\displaystyle\\leq\\mathbb\{P\}\\\!\\big\(\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\geq\|g\_\{t,ij\}\|\\,\\big\|\\,W\_\{t\}\\big\)\.Apply Markov’s inequality to the nonnegative random variable\|G~t,i​j−gt,i​j\|\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|:

ℙ​\(\|G~t,i​j−gt,i​j\|≥\|gt,i​j\|\|Wt\)≤𝔼​\[\|G~t,i​j−gt,i​j\|∣Wt\]\|gt,i​j\|\.\\mathbb\{P\}\\\!\\big\(\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\geq\|g\_\{t,ij\}\|\\,\\big\|\\,W\_\{t\}\\big\)\\leq\\frac\{\\mathbb\{E\}\\big\[\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\mid W\_\{t\}\\big\]\}\{\|g\_\{t,ij\}\|\}\.Next, apply Cauchy–Schwarz \(or Jensen\) to bound the first absolute moment by the square root of the second moment:

𝔼​\[\|G~t,i​j−gt,i​j\|∣Wt\]≤𝔼​\[\(G~t,i​j−gt,i​j\)2∣Wt\]=Var⁡\(G~t,i​j∣Wt\)\.\\mathbb\{E\}\\big\[\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\mid W\_\{t\}\\big\]\\leq\\sqrt\{\\mathbb\{E\}\\big\[\(\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\)^\{2\}\\mid W\_\{t\}\\big\]\}=\\sqrt\{\\operatorname\{Var\}\(\\widetilde\{G\}\_\{t,ij\}\\mid W\_\{t\}\)\}\.By Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2),Var⁡\(G~t,i​j∣Wt\)≤σi​j2/nb\\operatorname\{Var\}\(\\widetilde\{G\}\_\{t,ij\}\\mid W\_\{t\}\)\\leq\\sigma\_\{ij\}^\{2\}/n\_\{b\}, so

𝔼​\[\|G~t,i​j−gt,i​j\|∣Wt\]≤σi​jnb\.\\mathbb\{E\}\\big\[\|\\widetilde\{G\}\_\{t,ij\}\-g\_\{t,ij\}\|\\mid W\_\{t\}\\big\]\\leq\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\}\.Combining the displayed inequalities yields

qi​j,t≤1\|gt,i​j\|⋅σi​jnb,q\_\{ij,t\}\\leq\\frac\{1\}\{\|g\_\{t,ij\}\|\}\\cdot\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\},which is \([30](https://arxiv.org/html/2605.16311#A3.E30)\)\. ∎

#### C\.9\.4Proof of Lemma[C\.4\.4](https://arxiv.org/html/2605.16311#A3.SS4.SSS4)

###### Proof\.

We give a self\-contained proof following the structure of the signSGD analysis\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\], specialized to a fixed entry\(i,j\)\(i,j\)and then applied entrywise\.

##### Step 1: reduce to a scalar problem\.

Fix an iterationttand an entry\(i,j\)\(i,j\), and condition onWtW\_\{t\}\. Write

g:=gt,i​j∈ℝ,σ:=σi​j≥0\.g:=g\_\{t,ij\}\\in\\mathbb\{R\},\\qquad\\sigma:=\\sigma\_\{ij\}\\geq 0\.For workermm, let

g~\(m\):=G~t,i​j\(m\),S\(m\):=sign⁡\(g~\(m\)\)\.\\widetilde\{g\}^\{\(m\)\}:=\\widetilde\{G\}^\{\(m\)\}\_\{t,ij\},\\qquad S^\{\(m\)\}:=\\operatorname\{sign\}\(\\widetilde\{g\}^\{\(m\)\}\)\.By Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2), the noiseg~\(m\)−g\\widetilde\{g\}^\{\(m\)\}\-gis unimodal and symmetric about0\. The majority vote bit is

S¯:=sign⁡\(∑m=1MS\(m\)\)\.\\bar\{S\}:=\\operatorname\{sign\}\\\!\\left\(\\sum\_\{m=1\}^\{M\}S^\{\(m\)\}\\right\)\.We need to bound

qMV:=ℙ​\(S¯≠sign⁡\(g\)∣Wt\)\.q^\{\\mathrm\{MV\}\}:=\\mathbb\{P\}\\big\(\\bar\{S\}\\neq\\operatorname\{sign\}\(g\)\\mid W\_\{t\}\\big\)\.

##### Step 2: bound the single\-worker failure probability under unimodal symmetry\.

Define the signal\-to\-noise ratio

S:=\|g\|σ/nb=nb​\|g\|σ\(interpretingS=\+∞ifσ=0\)\.S:=\\frac\{\|g\|\}\{\\sigma/\\sqrt\{n\_\{b\}\}\}=\\frac\{\\sqrt\{n\_\{b\}\}\\,\|g\|\}\{\\sigma\}\\qquad\\text\{\(interpreting $S=\+\\infty$ if $\\sigma=0$\)\.\}Lemma D\.1 in signSGD\[[2](https://arxiv.org/html/2605.16311#bib.bib10)\]\(derived from Gauss’ inequality\) states that for unimodal symmetric noise, the single\-worker failure probability

q:=ℙ​\(sign⁡\(g~\(m\)\)≠sign⁡\(g\)∣Wt\)q:=\\mathbb\{P\}\\big\(\\operatorname\{sign\}\(\\widetilde\{g\}^\{\(m\)\}\)\\neq\\operatorname\{sign\}\(g\)\\mid W\_\{t\}\\big\)satisfies the explicit upper bound

q≤\{29⋅1S2,S\>23,12−S2​3,otherwise\.q\\leq\\begin\{cases\}\\displaystyle\\frac\{2\}\{9\}\\cdot\\frac\{1\}\{S^\{2\}\},&S\>\\sqrt\{\\frac\{2\}\{3\}\},\\\\\[8\.00003pt\] \\displaystyle\\frac\{1\}\{2\}\-\\frac\{S\}\{2\\sqrt\{3\}\},&\\text\{otherwise\}\.\\end\{cases\}\(46\)In particular,q<12q<\\frac\{1\}\{2\}for allS\>0S\>0\.

##### Step 3: majority vote as repetition\-code decoding\.

Conditional onWtW\_\{t\}, the bitsS\(1\),…,S\(M\)S^\{\(1\)\},\\dots,S^\{\(M\)\}are independent and identically distributed with failure probabilityqq\. LetBBdenote the number of workers whose sign is wrong:

B:=\#​\{m∈\{1,…,M\}:S\(m\)≠sign⁡\(g\)\}\.B:=\\\#\\\{m\\in\\\{1,\\dots,M\\\}:S^\{\(m\)\}\\neq\\operatorname\{sign\}\(g\)\\\}\.ThenB∼Binomial​\(M,q\)B\\sim\\mathrm\{Binomial\}\(M,q\)\. For oddMM, the event “majority vote is wrong” is exactly\{B≥\(M\+1\)/2\}\\\{B\\geq\(M\+1\)/2\\\}\. For evenMM, the same is true up to a tie event; our tie convention issign⁡\(0\)=0\\operatorname\{sign\}\(0\)=0, which can only make the error probability smaller than a worst\-case tie\-breaking\. Thus, in all cases,

qMV≤ℙ​\(B≥M2\)\.q^\{\\mathrm\{MV\}\}\\leq\\mathbb\{P\}\\\!\\left\(B\\geq\\frac\{M\}\{2\}\\right\)\.\(47\)

##### Step 4: binomial tail bound \(Hoeffding/Chernoff\)\.

Forq<1/2q<1/2, a standard Hoeffding bound yields

ℙ​\(B≥M2\)≤exp⁡\(−2​M​\(1/2−q\)2\)\.\\mathbb\{P\}\\\!\\left\(B\\geq\\frac\{M\}\{2\}\\right\)\\leq\\exp\\\!\\big\(\-2M\(1/2\-q\)^\{2\}\\big\)\.\(48\)Combining \([47](https://arxiv.org/html/2605.16311#A3.E47)\) and \([48](https://arxiv.org/html/2605.16311#A3.E48)\),

qMV≤exp⁡\(−2​M​\(1/2−q\)2\)\.q^\{\\mathrm\{MV\}\}\\leq\\exp\\\!\\big\(\-2M\(1/2\-q\)^\{2\}\\big\)\.

##### Step 5: convert to the desired1/M1/\\sqrt\{M\}form\.

We now show that

qMV≤1M⋅1Sfor all​M≥1​and all​S\>0,q^\{\\mathrm\{MV\}\}\\leq\\frac\{1\}\{\\sqrt\{M\}\}\\cdot\\frac\{1\}\{S\}\\qquad\\text\{for all \}M\\geq 1\\text\{ and all \}S\>0,which is equivalent to \([31](https://arxiv.org/html/2605.16311#A3.E31)\) after substitutingS=nb​\|g\|/σS=\\sqrt\{n\_\{b\}\}\|g\|/\\sigma\.

We treat two regimes\.

Regime A:S≤1/MS\\leq 1/\\sqrt\{M\}\.Then1M​S≥1\\frac\{1\}\{\\sqrt\{M\}S\}\\geq 1, so the claim holds trivially becauseqMV≤1q^\{\\mathrm\{MV\}\}\\leq 1\.

Regime B:S\>1/MS\>1/\\sqrt\{M\}\.We use the unimodal\-symmetry bound \([46](https://arxiv.org/html/2605.16311#A3.E46)\) to lower bound\(1/2−q\)\(1/2\-q\)\. WhenS≤2/3S\\leq\\sqrt\{2/3\}, the second case in \([46](https://arxiv.org/html/2605.16311#A3.E46)\) implies

12−q≥S2​3\.\\frac\{1\}\{2\}\-q\\geq\\frac\{S\}\{2\\sqrt\{3\}\}\.WhenS\>2/3S\>\\sqrt\{2/3\}, the first case impliesq≤2/\(9​S2\)q\\leq 2/\(9S^\{2\}\), hence

12−q≥12−29​S2≥12−29⋅32=16,\\frac\{1\}\{2\}\-q\\geq\\frac\{1\}\{2\}\-\\frac\{2\}\{9S^\{2\}\}\\geq\\frac\{1\}\{2\}\-\\frac\{2\}\{9\}\\cdot\\frac\{3\}\{2\}=\\frac\{1\}\{6\},where we usedS2\>23S^\{2\}\>\\frac\{2\}\{3\}to obtain1S2<32\\frac\{1\}\{S^\{2\}\}<\\frac\{3\}\{2\}\. Thus, in all cases,

12−q≥min⁡\{S2​3,16\}\.\\frac\{1\}\{2\}\-q\\geq\\min\\left\\\{\\frac\{S\}\{2\\sqrt\{3\}\},\\,\\frac\{1\}\{6\}\\right\\\}\.\(49\)Plugging \([49](https://arxiv.org/html/2605.16311#A3.E49)\) into \([48](https://arxiv.org/html/2605.16311#A3.E48)\) yields

qMV≤exp⁡\(−2​M⋅min⁡\{S212,136\}\)=max⁡\{exp⁡\(−M​S26\),exp⁡\(−M18\)\}\.q^\{\\mathrm\{MV\}\}\\leq\\exp\\\!\\left\(\-2M\\cdot\\min\\left\\\{\\frac\{S^\{2\}\}\{12\},\\,\\frac\{1\}\{36\}\\right\\\}\\right\)=\\max\\left\\\{\\exp\\\!\\left\(\-\\frac\{MS^\{2\}\}\{6\}\\right\),\\ \\exp\\\!\\left\(\-\\frac\{M\}\{18\}\\right\)\\right\\\}\.SinceS\>1/MS\>1/\\sqrt\{M\}in this regime, the first term satisfies

exp⁡\(−M​S26\)≤exp⁡\(−16\)<1\.\\exp\\\!\\left\(\-\\frac\{MS^\{2\}\}\{6\}\\right\)\\leq\\exp\\\!\\left\(\-\\frac\{1\}\{6\}\\right\)<1\.Moreover, for anya\>0a\>0and anyx\>0x\>0,

e−a​x2≤12​a​x,e^\{\-ax^\{2\}\}\\leq\\frac\{1\}\{2\\sqrt\{a\}\\,x\},which follows by maximizingx​e−a​x2xe^\{\-ax^\{2\}\}overx\>0x\>0\. Applying this witha=M/6a=M/6andx=Sx=Sgives

exp⁡\(−M​S26\)≤62⋅1M​S\.\\exp\\\!\\left\(\-\\frac\{MS^\{2\}\}\{6\}\\right\)\\leq\\frac\{\\sqrt\{6\}\}\{2\}\\cdot\\frac\{1\}\{\\sqrt\{M\}\\,S\}\.Finally,exp⁡\(−M/18\)≤1≤1M​S\\exp\(\-M/18\)\\leq 1\\leq\\frac\{1\}\{\\sqrt\{M\}S\}in Regime B wheneverS≥1/MS\\geq 1/\\sqrt\{M\}\. Combining the two bounds yields

qMV≤62⋅1M​S\.q^\{\\mathrm\{MV\}\}\\leq\\frac\{\\sqrt\{6\}\}\{2\}\\cdot\\frac\{1\}\{\\sqrt\{M\}\\,S\}\.Thus \([31](https://arxiv.org/html/2605.16311#A3.E31)\) holds with a universal constant factor6/2<2\\sqrt\{6\}/2<2\. Absorbing this constant into the theorem statement yields the simplified bound \([31](https://arxiv.org/html/2605.16311#A3.E31)\)\. ∎

#### C\.9\.5Proof of Theorem[C\.5\.1](https://arxiv.org/html/2605.16311#A3.SS5.SSS1)

###### Proof\.

Fixttand apply Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)withW=WtW=W\_\{t\}andD=DtD=D\_\{t\}:

f​\(Wt\+1\)=f​\(Wt−η​Dt\)≤f​\(Wt\)−η​⟨∇f​\(Wt\),Dt⟩\+L∗2​η2​‖Dt‖op2\.f\(W\_\{t\+1\}\)=f\(W\_\{t\}\-\\eta D\_\{t\}\)\\leq f\(W\_\{t\}\)\-\\eta\\left\\langle\\nabla f\(W\_\{t\}\),D\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.SinceDt=St/m​nD\_\{t\}=S\_\{t\}/\\sqrt\{mn\}andStS\_\{t\}has entries in\{−1,0,\+1\}\\\{\-1,0,\+1\\\}, we have‖St‖op≤m​n\\left\\lVert S\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\sqrt\{mn\}, hence‖Dt‖op≤1\\left\\lVert D\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1and therefore

f​\(Wt\+1\)≤f​\(Wt\)−η​⟨gt,Dt⟩\+L∗2​η2\.f\(W\_\{t\+1\}\)\\leq f\(W\_\{t\}\)\-\\eta\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.\(50\)Now take conditional expectation givenWtW\_\{t\}:

𝔼​\[f​\(Wt\+1\)∣Wt\]≤f​\(Wt\)−η​𝔼​\[⟨gt,Dt⟩∣Wt\]\+L∗2​η2\.\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\\mid W\_\{t\}\]\\leq f\(W\_\{t\}\)\-\\eta\\mathbb\{E\}\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\]\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Apply Lemma[C\.4\.2](https://arxiv.org/html/2605.16311#A3.SS4.SSS2)to the conditional inner product term:

𝔼​\[⟨gt,Dt⟩∣Wt\]=1m​n​∑i,j\|gt,i​j\|​\(1−2​qi​j,t\)\.\\mathbb\{E\}\[\\left\\langle g\_\{t\},D\_\{t\}\\right\\rangle\\mid W\_\{t\}\]=\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\(1\-2q\_\{ij,t\}\)\.Substitute:

𝔼​\[f​\(Wt\+1\)∣Wt\]≤f​\(Wt\)−η⋅1m​n​∑i,j\|gt,i​j\|​\(1−2​qi​j,t\)\+L∗2​η2\.\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\\mid W\_\{t\}\]\\leq f\(W\_\{t\}\)\-\\eta\\cdot\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\(1\-2q\_\{ij,t\}\)\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Rearrange terms to isolate‖gt‖1/m​n\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}/\\sqrt\{mn\}:

η⋅‖gt‖1m​n≤f​\(Wt\)−𝔼​\[f​\(Wt\+1\)∣Wt\]\+L∗2​η2\+2​η⋅1m​n​∑i,j\|gt,i​j\|​qi​j,t\.\\eta\\cdot\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\leq f\(W\_\{t\}\)\-\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\\mid W\_\{t\}\]\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\+2\\eta\\cdot\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|q\_\{ij,t\}\.Now take full expectation over all randomness \(including the trajectory\):

η​𝔼​\[‖gt‖1m​n\]≤𝔼​\[f​\(Wt\)\]−𝔼​\[f​\(Wt\+1\)\]\+L∗2​η2\+2​η​𝔼​\[1m​n​∑i,j\|gt,i​j\|​qi​j,t\]\.\\eta\\,\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\leq\\mathbb\{E\}\[f\(W\_\{t\}\)\]\-\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\]\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\+2\\eta\\,\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|q\_\{ij,t\}\\right\]\.Sum the inequality fromt=0t=0toT−1T\-1:

η​∑t=0T−1𝔼​\[‖gt‖1m​n\]\\displaystyle\\eta\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]≤∑t=0T−1\(𝔼​\[f​\(Wt\)\]−𝔼​\[f​\(Wt\+1\)\]\)\+T⋅L∗2​η2\\displaystyle\\leq\\sum\_\{t=0\}^\{T\-1\}\\big\(\\mathbb\{E\}\[f\(W\_\{t\}\)\]\-\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\]\\big\)\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\+2​η​∑t=0T−1𝔼​\[1m​n​∑i,j\|gt,i​j\|​qi​j,t\]\.\\displaystyle\\qquad\+2\\eta\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|q\_\{ij,t\}\\right\]\.The sum telescopes:

∑t=0T−1\(𝔼​\[f​\(Wt\)\]−𝔼​\[f​\(Wt\+1\)\]\)=𝔼​\[f​\(W0\)\]−𝔼​\[f​\(WT\)\]\.\\sum\_\{t=0\}^\{T\-1\}\\big\(\\mathbb\{E\}\[f\(W\_\{t\}\)\]\-\\mathbb\{E\}\[f\(W\_\{t\+1\}\)\]\\big\)=\\mathbb\{E\}\[f\(W\_\{0\}\)\]\-\\mathbb\{E\}\[f\(W\_\{T\}\)\]\.Using Assumption[C\.1](https://arxiv.org/html/2605.16311#A3.SS1.SSS0.Px2),𝔼​\[f​\(WT\)\]≥f∗\\mathbb\{E\}\[f\(W\_\{T\}\)\]\\geq f^\{\\ast\}, so

𝔼​\[f​\(W0\)\]−𝔼​\[f​\(WT\)\]≤f​\(W0\)−f∗\.\\mathbb\{E\}\[f\(W\_\{0\}\)\]\-\\mathbb\{E\}\[f\(W\_\{T\}\)\]\\leq f\(W\_\{0\}\)\-f^\{\\ast\}\.Therefore,

η​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗\+T⋅L∗2​η2\+2​η​∑t=0T−1𝔼​\[1m​n​∑i,j\|gt,i​j\|​qi​j,t\]\.\\eta\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\leq f\(W\_\{0\}\)\-f^\{\\ast\}\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\+2\\eta\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|q\_\{ij,t\}\\right\]\.Divide byη​T\\eta Tto obtain \([33](https://arxiv.org/html/2605.16311#A3.E33)\)\. ∎

#### C\.9\.6Proof of Theorem[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)

###### Proof\.

Theorem[C\.5\.1](https://arxiv.org/html/2605.16311#A3.SS5.SSS1)yields

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗η​T\+L∗2​η\+2T​∑t=0T−1𝔼​\[1m​n​∑i,j\|gt,i​j\|​qi​j,t\]\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\leq\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{2\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\right\]\.In the single\-worker gradient\-sign case, Lemma[C\.4\.3](https://arxiv.org/html/2605.16311#A3.SS4.SSS3)gives, for each\(i,j\)\(i,j\)withgt,i​j≠0g\_\{t,ij\}\\neq 0,

qi​j,t≤σi​jnb​\|gt,i​j\|\.q\_\{ij,t\}\\leq\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\\,\|g\_\{t,ij\}\|\}\.Therefore

\|gt,i​j\|​qi​j,t≤σi​jnb\.\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\leq\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\}\.Summing over\(i,j\)\(i,j\)yields

∑i,j\|gt,i​j\|​qi​j,t≤1nb​∑i,jσi​j=‖σ‖1nb\.\\sum\_\{i,j\}\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\leq\\frac\{1\}\{\\sqrt\{n\_\{b\}\}\}\\sum\_\{i,j\}\\sigma\_\{ij\}=\\frac\{\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{n\_\{b\}\}\}\.Thus, for everytt,

1m​n​∑i,j\|gt,i​j\|​qi​j,t≤‖σ‖1m​n​nb\.\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\\,q\_\{ij,t\}\\leq\\frac\{\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,n\_\{b\}\}\}\.Plugging this into the generic bound yields \([34](https://arxiv.org/html/2605.16311#A3.E34)\):

1T​∑t=0T−1𝔼​\[‖gt‖1m​n\]≤f​\(W0\)−f∗η​T\+L∗2​η\+2​‖σ‖1m​n​nb\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\frac\{\\left\\lVert g\_\{t\}\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\}\}\\right\]\\leq\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{2\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,n\_\{b\}\}\}\.To obtain \([35](https://arxiv.org/html/2605.16311#A3.E35)\), choose

η=2​\(f​\(W0\)−f∗\)L∗​T,\\eta=\\sqrt\{\\frac\{2\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{L\_\{\\ast\}T\}\},which minimizes the functionη↦f​\(W0\)−f∗η​T\+L∗2​η\\eta\\mapsto\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\. With this choice,

f​\(W0\)−f∗η​T\+L∗2​η=L∗​\(f​\(W0\)−f∗\)T\.\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta=\\sqrt\{\\frac\{L\_\{\\ast\}\(f\(W\_\{0\}\)\-f^\{\\ast\}\)\}\{T\}\}\.Finally, setnb=Tn\_\{b\}=Tto obtain the statedO​\(1/T\)O\(1/\\sqrt\{T\}\)dependence for the noise term\. ∎

#### C\.9\.7Proof of Theorem[C\.5\.3](https://arxiv.org/html/2605.16311#A3.SS5.SSS3)

###### Proof\.

Apply Theorem[C\.5\.1](https://arxiv.org/html/2605.16311#A3.SS5.SSS1)to the aggregated sign matrixSt=S¯tS\_\{t\}=\\bar\{S\}\_\{t\}\(majority vote\), so thatqi​j,tq\_\{ij,t\}is replaced byqi​j,tMVq^\{\\mathrm\{MV\}\}\_\{ij,t\}\. Lemma[C\.4\.4](https://arxiv.org/html/2605.16311#A3.SS4.SSS4)states that for each entry\(i,j\)\(i,j\)withgt,i​j≠0g\_\{t,ij\}\\neq 0,

qi​j,tMV≤1M⋅σi​jnb​\|gt,i​j\|\.q^\{\\mathrm\{MV\}\}\_\{ij,t\}\\leq\\frac\{1\}\{\\sqrt\{M\}\}\\cdot\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\\,\|g\_\{t,ij\}\|\}\.Hence

\|gt,i​j\|​qi​j,tMV≤1M⋅σi​jnb\.\|g\_\{t,ij\}\|\\,q^\{\\mathrm\{MV\}\}\_\{ij,t\}\\leq\\frac\{1\}\{\\sqrt\{M\}\}\\cdot\\frac\{\\sigma\_\{ij\}\}\{\\sqrt\{n\_\{b\}\}\}\.Summing and dividing bym​n\\sqrt\{mn\}gives

1m​n​∑i,j\|gt,i​j\|​qi​j,tMV≤1m​n⋅1M⋅1nb​∑i,jσi​j=‖σ‖1m​n​M​nb\.\\frac\{1\}\{\\sqrt\{mn\}\}\\sum\_\{i,j\}\|g\_\{t,ij\}\|\\,q^\{\\mathrm\{MV\}\}\_\{ij,t\}\\leq\\frac\{1\}\{\\sqrt\{mn\}\}\\cdot\\frac\{1\}\{\\sqrt\{M\}\}\\cdot\\frac\{1\}\{\\sqrt\{n\_\{b\}\}\}\\sum\_\{i,j\}\\sigma\_\{ij\}=\\frac\{\\left\\lVert\\sigma\\right\\rVert\_\{1\}\}\{\\sqrt\{mn\\,M\\,n\_\{b\}\}\}\.Insert this bound into \([33](https://arxiv.org/html/2605.16311#A3.E33)\) to obtain \([36](https://arxiv.org/html/2605.16311#A3.E36)\), and then optimizeη\\etaand choosenb=Tn\_\{b\}=Texactly as in Theorem[C\.5\.2](https://arxiv.org/html/2605.16311#A3.SS5.SSS2)\. ∎

#### C\.9\.8Proof of Proposition[C\.6\.1](https://arxiv.org/html/2605.16311#A3.SS6.SSS1)

###### Proof\.

LetG∈ℝm×nG\\in\\mathbb\{R\}^\{m\\times n\}and letG=U​Σ​V⊤G=U\\Sigma V^\{\\top\}be an SVD with rankrr\. For anyDDwith‖D‖op≤1\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1, defineB:=U⊤​D​V∈ℝr×rB:=U^\{\\top\}DV\\in\\mathbb\{R\}^\{r\\times r\}\. BecauseUUandVVhave orthonormal columns,

‖B‖op=‖U⊤​D​V‖op≤‖U⊤‖op​‖D‖op​‖V‖op≤1\.\\left\\lVert B\\right\\rVert\_\{\\mathrm\{op\}\}=\\left\\lVert U^\{\\top\}DV\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert U^\{\\top\}\\right\\rVert\_\{\\mathrm\{op\}\}\\,\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\,\\left\\lVert V\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\.Now compute the inner product:

⟨G,D⟩=tr⁡\(G⊤​D\)=tr⁡\(V​Σ​U⊤​D\)=tr⁡\(Σ​U⊤​D​V\)=tr⁡\(Σ​B\)\.\\left\\langle G,D\\right\\rangle=\\operatorname\{tr\}\(G^\{\\top\}D\)=\\operatorname\{tr\}\(V\\Sigma U^\{\\top\}D\)=\\operatorname\{tr\}\(\\Sigma U^\{\\top\}DV\)=\\operatorname\{tr\}\(\\Sigma B\)\.SinceΣ\\Sigmais diagonal with nonnegative entries, and‖B‖op≤1\\left\\lVert B\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1, we have\|Bk​k\|≤‖B‖op≤1\|B\_\{kk\}\|\\leq\\left\\lVert B\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1for eachkk, hence

tr⁡\(Σ​B\)=∑k=1rΣk​k​Bk​k≤∑k=1rΣk​k=‖G‖∗\.\\operatorname\{tr\}\(\\Sigma B\)=\\sum\_\{k=1\}^\{r\}\\Sigma\_\{kk\}B\_\{kk\}\\leq\\sum\_\{k=1\}^\{r\}\\Sigma\_\{kk\}=\\left\\lVert G\\right\\rVert\_\{\*\}\.Thus⟨G,D⟩≤‖G‖∗\\left\\langle G,D\\right\\rangle\\leq\\left\\lVert G\\right\\rVert\_\{\*\}for all‖D‖op≤1\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1, provingmax‖D‖op≤1⁡⟨G,D⟩≤‖G‖∗\\max\_\{\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\left\\langle G,D\\right\\rangle\\leq\\left\\lVert G\\right\\rVert\_\{\*\}\.

For the reverse inequality, chooseD⋆=U​V⊤D^\{\\star\}=UV^\{\\top\}\. Then‖D⋆‖op=1\\left\\lVert D^\{\\star\}\\right\\rVert\_\{\\mathrm\{op\}\}=1and

⟨G,D⋆⟩=tr⁡\(G⊤​U​V⊤\)=tr⁡\(V​Σ​U⊤​U​V⊤\)=tr⁡\(V​Σ​V⊤\)=tr⁡\(Σ\)=‖G‖∗\.\\left\\langle G,D^\{\\star\}\\right\\rangle=\\operatorname\{tr\}\(G^\{\\top\}UV^\{\\top\}\)=\\operatorname\{tr\}\(V\\Sigma U^\{\\top\}UV^\{\\top\}\)=\\operatorname\{tr\}\(V\\Sigma V^\{\\top\}\)=\\operatorname\{tr\}\(\\Sigma\)=\\left\\lVert G\\right\\rVert\_\{\*\}\.Thereforemax‖D‖op≤1⁡⟨G,D⟩=‖G‖∗\\max\_\{\\left\\lVert D\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\left\\langle G,D\\right\\rangle=\\left\\lVert G\\right\\rVert\_\{\*\}andD⋆=polar⁡\(G\)D^\{\\star\}=\\operatorname\{polar\}\(G\)attains it, proving \([38](https://arxiv.org/html/2605.16311#A3.E38)\)\. ∎

#### C\.9\.9Proof of Theorem[C\.6\.2](https://arxiv.org/html/2605.16311#A3.SS6.SSS2)

###### Proof\.

RecallQt=polar⁡\(gt\)Q\_\{t\}=\\operatorname\{polar\}\(g\_\{t\}\),‖Qt‖op=1\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}=1, andWt\+1=Wt−η​QtW\_\{t\+1\}=W\_\{t\}\-\\eta Q\_\{t\}\. Apply Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)withW=WtW=W\_\{t\}andD=QtD=Q\_\{t\}:

f​\(Wt\+1\)≤f​\(Wt\)−η​⟨gt,Qt⟩\+L∗2​η2​‖Qt‖op2=f​\(Wt\)−η​⟨gt,Qt⟩\+L∗2​η2\.f\(W\_\{t\+1\}\)\\leq f\(W\_\{t\}\)\-\\eta\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}=f\(W\_\{t\}\)\-\\eta\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.By Proposition[C\.6\.1](https://arxiv.org/html/2605.16311#A3.SS6.SSS1),⟨gt,Qt⟩=‖gt‖∗\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle=\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\. Hence

f​\(Wt\+1\)≤f​\(Wt\)−η​‖gt‖∗\+L∗2​η2\.f\(W\_\{t\+1\}\)\\leq f\(W\_\{t\}\)\-\\eta\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Rearrange:

η​‖gt‖∗≤f​\(Wt\)−f​\(Wt\+1\)\+L∗2​η2\.\\eta\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\leq f\(W\_\{t\}\)\-f\(W\_\{t\+1\}\)\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Sum overt=0,…,T−1t=0,\\dots,T\-1:

η​∑t=0T−1‖gt‖∗≤f​\(W0\)−f​\(WT\)\+T⋅L∗2​η2\.\\eta\\sum\_\{t=0\}^\{T\-1\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\leq f\(W\_\{0\}\)\-f\(W\_\{T\}\)\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Take expectation and usef​\(WT\)≥f∗f\(W\_\{T\}\)\\geq f^\{\\ast\}:

η​∑t=0T−1𝔼​\[‖gt‖∗\]≤f​\(W0\)−f∗\+T⋅L∗2​η2\.\\eta\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\[\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\]\\leq f\(W\_\{0\}\)\-f^\{\\ast\}\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Divide byη​T\\eta Tto obtain \([40](https://arxiv.org/html/2605.16311#A3.E40)\)\. Optimizingη\\etayields \([41](https://arxiv.org/html/2605.16311#A3.E41)\)\. ∎

#### C\.9\.10Proof of Theorem[C\.7\.1](https://arxiv.org/html/2605.16311#A3.SS7.SSS1)

###### Proof\.

Apply Lemma[C\.3](https://arxiv.org/html/2605.16311#A3.SS3)withW=WtW=W\_\{t\}andD=QtD=Q\_\{t\}:

f​\(Wt\+1\)≤f​\(Wt\)−η​⟨gt,Qt⟩\+L∗2​η2​‖Qt‖op2≤f​\(Wt\)−η​⟨gt,Qt⟩\+L∗2​η2,f\(W\_\{t\+1\}\)\\leq f\(W\_\{t\}\)\-\\eta\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\\leq f\(W\_\{t\}\)\-\\eta\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\},since‖Qt‖op≤1\\left\\lVert Q\_\{t\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. Decompose the inner product:

⟨gt,Qt⟩=⟨gt,polar⁡\(gt\)⟩\+⟨gt,Qt−polar⁡\(gt\)⟩\.\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle=\\left\\langle g\_\{t\},\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle\+\\left\\langle g\_\{t\},Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle\.By Proposition[C\.6\.1](https://arxiv.org/html/2605.16311#A3.SS6.SSS1),⟨gt,polar⁡\(gt\)⟩=‖gt‖∗\\left\\langle g\_\{t\},\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle=\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\. For the error term, use nuclear/spectral duality:

\|⟨gt,Qt−polar⁡\(gt\)⟩\|≤‖gt‖∗​‖Qt−polar⁡\(gt\)‖op≤εt​‖gt‖∗\.\\left\|\\left\\langle g\_\{t\},Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rangle\\right\|\\leq\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\,\\left\\lVert Q\_\{t\}\-\\operatorname\{polar\}\(g\_\{t\}\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\varepsilon\_\{t\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\.Therefore

⟨gt,Qt⟩≥‖gt‖∗−εt​‖gt‖∗=\(1−εt\)​‖gt‖∗\.\\left\\langle g\_\{t\},Q\_\{t\}\\right\\rangle\\geq\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\-\\varepsilon\_\{t\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}=\(1\-\\varepsilon\_\{t\}\)\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\.Plug this back into the descent inequality:

f​\(Wt\+1\)≤f​\(Wt\)−η​\(1−εt\)​‖gt‖∗\+L∗2​η2\.f\(W\_\{t\+1\}\)\\leq f\(W\_\{t\}\)\-\\eta\(1\-\\varepsilon\_\{t\}\)\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Rearrange and sum overtt:

η​∑t=0T−1\(1−εt\)​‖gt‖∗≤f​\(W0\)−f​\(WT\)\+T⋅L∗2​η2≤f​\(W0\)−f∗\+T⋅L∗2​η2\.\\eta\\sum\_\{t=0\}^\{T\-1\}\(1\-\\varepsilon\_\{t\}\)\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\leq f\(W\_\{0\}\)\-f\(W\_\{T\}\)\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\\leq f\(W\_\{0\}\)\-f^\{\\ast\}\+T\\cdot\\frac\{L\_\{\\ast\}\}\{2\}\\eta^\{2\}\.Divide byη​T\\eta Tand use\(1−εt\)​‖gt‖∗≥‖gt‖∗−εt​‖gt‖∗\(1\-\\varepsilon\_\{t\}\)\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\geq\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\-\\varepsilon\_\{t\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}to obtain

1T​∑t=0T−1‖gt‖∗≤f​\(W0\)−f∗η​T\+L∗2​η\+1T​∑t=0T−1εt​‖gt‖∗,\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\leq\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\varepsilon\_\{t\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\},which is \([43](https://arxiv.org/html/2605.16311#A3.E43)\)\. Ifεt≤ε¯<1\\varepsilon\_\{t\}\\leq\\bar\{\\varepsilon\}<1, then

\(1−ε¯\)⋅1T​∑t=0T−1‖gt‖∗≤f​\(W0\)−f∗η​T\+L∗2​η,\(1\-\\bar\{\\varepsilon\}\)\\cdot\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\left\\lVert g\_\{t\}\\right\\rVert\_\{\*\}\\leq\\frac\{f\(W\_\{0\}\)\-f^\{\\ast\}\}\{\\eta T\}\+\\frac\{L\_\{\\ast\}\}\{2\}\\eta,giving the stated bound\. ∎

#### C\.9\.11Proof of Theorem[6](https://arxiv.org/html/2605.16311#alg6)

###### Proof\.

We provide an idealized proof that captures the key contraction\. LetY0=X/αY\_\{0\}=X/\\alphaand define the error matrix

Ek:=I−Yk⊤​Yk∈ℝn×n\.E\_\{k\}:=I\-Y\_\{k\}^\{\\top\}Y\_\{k\}\\in\\mathbb\{R\}^\{n\\times n\}\.Assumption \([44](https://arxiv.org/html/2605.16311#A3.E44)\) is exactly‖E0‖op≤ρ<1\\left\\lVert E\_\{0\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho<1\.

Using the Newton–Schulz update

Yk\+1=12​Yk​\(3​I−Yk⊤​Yk\)=12​Yk​\(2​I\+Ek\)=Yk​\(I\+12​Ek\),Y\_\{k\+1\}=\\frac\{1\}\{2\}Y\_\{k\}\(3I\-Y\_\{k\}^\{\\top\}Y\_\{k\}\)=\\frac\{1\}\{2\}Y\_\{k\}\(2I\+E\_\{k\}\)=Y\_\{k\}\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\),we compute

Yk\+1⊤​Yk\+1\\displaystyle Y\_\{k\+1\}^\{\\top\}Y\_\{k\+1\}=\(I\+12​Ek\)⊤​Yk⊤​Yk​\(I\+12​Ek\)\\displaystyle=\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)^\{\\top\}Y\_\{k\}^\{\\top\}Y\_\{k\}\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)=\(I\+12​Ek\)​\(I−Ek\)​\(I\+12​Ek\)\(sinceYk⊤​Yk=I−Ek\)\.\\displaystyle=\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)\(I\-E\_\{k\}\)\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)\\qquad\\text\{\(since $Y\_\{k\}^\{\\top\}Y\_\{k\}=I\-E\_\{k\}$\)\}\.BecauseEkE\_\{k\}commutes with itself, we can multiply the polynomials:

\(I\+12​Ek\)​\(I−Ek\)​\(I\+12​Ek\)=I−Ek2\.\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)\\left\(I\-E\_\{k\}\\right\)\\left\(I\+\\frac\{1\}\{2\}E\_\{k\}\\right\)=I\-E\_\{k\}^\{2\}\.Therefore

Ek\+1:=I−Yk\+1⊤​Yk\+1=Ek2\.E\_\{k\+1\}:=I\-Y\_\{k\+1\}^\{\\top\}Y\_\{k\+1\}=E\_\{k\}^\{2\}\.Taking operator norms,

‖Ek\+1‖op=‖Ek2‖op≤‖Ek‖op2\.\\left\\lVert E\_\{k\+1\}\\right\\rVert\_\{\\mathrm\{op\}\}=\\left\\lVert E\_\{k\}^\{2\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert E\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.By induction,

‖Ek‖op≤‖E0‖op2k≤ρ2k\.\\left\\lVert E\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert E\_\{0\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2^\{k\}\}\\leq\\rho^\{2^\{k\}\}\.In particular,‖Ek‖op→0\\left\\lVert E\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}\\to 0, which impliesYk⊤​Yk→IY\_\{k\}^\{\\top\}Y\_\{k\}\\to Iand‖Yk‖op≤1\\left\\lVert Y\_\{k\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 1for allkk\.

To convert this into a bound on‖Yk−polar⁡\(X\)‖op\\left\\lVert Y\_\{k\}\-\\operatorname\{polar\}\(X\)\\right\\rVert\_\{\\mathrm\{op\}\}, one uses the characterization of the polar factorQ=polar⁡\(X\)Q=\\operatorname\{polar\}\(X\)asQ=X​\(X⊤​X\)−1/2Q=X\(X^\{\\top\}X\)^\{\-1/2\}and the fact that the iteration is precisely performing an inverse\-square\-root iteration onX⊤​XX^\{\\top\}X\. A standard perturbation argument \(see, e\.g\.,\[[9](https://arxiv.org/html/2605.16311#bib.bib25), Chapter 8\]\) yields

‖YK−Q‖op≤‖EK‖op≤ρ2K\.\\left\\lVert Y\_\{K\}\-Q\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert E\_\{K\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho^\{2^\{K\}\}\.This establishes \([45](https://arxiv.org/html/2605.16311#A3.E45)\)\. ∎