Byzantine-Robust Muon: Resilient Momentum Orthogonalization for Distributed Learning
Organizations: King Abdullah University of Science and Technology (KAUST), Saudi Arabia
Abstract
Optimization methods, including the Muon optimizer based on the Linear Minimization Oracle (LMO) and momentum orthogonalization, have shown strong empirical performance in large-scale and distributed learning, yet their robustness to adversarial behavior and data heterogeneity is not well understood. We study these methods within a unified first-order trust-region framework and analyze Muon-based updates with robust aggregation for Byzantine-robust distributed and federated learning. Our analysis does not rely on the i.i.d. assumption and introduces a non-Euclidean notion of heterogeneity consistent with the trust-region geometry. Under this framework, we establish convergence guarantees for both general non-convex and star-convex objectives. Our results provide a theoretical characterization of Byzantine-robust Muon-based optimization, with an additive heterogeneity error floor consistent with known impossibility results, under explicit aggregation assumptions. Under an explicit additive oracle-error condition, the guarantees also cover inexact orthogonalization, with the non-convex Byzantine terms in the bound's numerator unchanged but a smaller progress denominator. In simulated federated training with ResNet-18 and ViT-Tiny on CIFAR-10, additional image benchmarks, and a 38M-parameter byte-level language model on TinyStories, the tested Muon configuration attains higher attacked accuracy (lower perplexity) than the tested SGD and normalized-SGD configurations, and than sign updates on CIFAR-10. Fixed-honest controls further show a substantial RFA advantage over averaging under a bounded RFA-query attack, higher attacked accuracy for Muon-NS than tensorwise Euclidean normalization from shared checkpoints, and lower held-out TinyStories perplexity than a tuned AdamW baseline.
Figures & tables
| Work | Geometry and smoothness | Heterogeneity | Aggregation premise | Update oracle | Convergence criterion |
| Yang et al. (2024) | Euclidean -smooth | i.i.d. | Euclidean second moment | exact normalization | average |
| Bolatov et al. (2026) | Euclidean -smooth | additive second moment | Euclidean first moment | exact normalization | minimum |
| This work | arbitrary norm -smooth | relative/additive first moment | dual-norm first moment | exact/inexact LMO | average star-convex gap |
| Geometry | Clean | Sign-flip | ALIE | IPM | Mimic | Adaptive |
| ResNet-18: SGD | 39.8 2.0 | 29.2 2.3 | 27.1 1.4 | 32.9 4.2 | 29.7 5.5 | 25.1 2.3 |
| ResNet-18: Normalized SGD | 49.0 2.3 | 34.8 2.7 | 34.4 1.8 | 42.3 2.1 | 44.3 1.7 | 30.4 1.7 |
| ResNet-18: Sign | 54.3 1.8 | 41.6 3.7 | 43.3 1.7 | 47.2 2.0 | 49.0 1.1 | 41.3 2.3 |
| ResNet-18: Muon-NS | 88.0 1.4 | 78.4 4.3 | 86.4 0.8 | 83.9 2.5 | 84.3 1.2 | 74.0 3.3 |
| ViT-Tiny: SGD | 35.5 2.0 | 26.6 1.6 | 37.1 1.2 | 29.7 1.2 | 30.8 1.8 | 28.4 1.5 |
| ViT-Tiny: Normalized SGD | 42.4 1.4 | 34.2 1.2 | 42.5 1.0 | 37.3 1.0 | 39.4 1.1 | 32.9 1.5 |
| Model and method | Benign | Dir. | Flip |
| ResNet-18: AdamW | 66.7 2.0 | 17.2 4.7 | 21.1 5.9 |
| ResNet-18: Muon-NS | 88.1 0.8 | 30.4 6.9 | 44.4 5.6 |
| ViT-Tiny: AdamW | 64.7 1.1 | 18.0 3.2 | 21.5 1.9 |
| ViT-Tiny: Muon-NS | 66.5 1.1 | 25.3 3.4 | 31.7 4.3 |
| Aggregator | Benign | RFA-query attack | |
| Mean | 88.7 1.0 | 10.0 0.0 | -78.7 1.0 |
| RFA | 88.1 0.7 | 36.5 6.6 | -51.7 6.2 |
| Geometry | Benign | Dir. | Flip | Dir. | Flip |
| Tensorwise | 90.8 0.4 | 82.3 3.4 | 82.4 3.9 | -8.5 3.4 | -8.3 3.7 |
| Muon-NS | 91.4 0.3 | 83.7 2.2 | 85.0 2.8 | -7.7 2.2 | -6.4 2.7 |
| Method | Benign | Dir. | Dir. | Flip |
| SGD | 5.038 0.080 | 6.676 0.304 | 7.034 0.128 | 8.035 0.121 |
| Normalized SGD | 3.620 0.064 | 3.695 0.042 | 3.789 0.043 | 3.599 0.009 |
| AdamW | 2.268 0.053 | 2.345 0.075 | 2.358 0.061 | 2.315 0.047 |
| Muon-NS | 1.875 0.003 | 1.920 0.006 | 1.938 0.004 | 1.876 0.004 |
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| Geometry and aggregator | Benign | Dir. | Dir. | Dir. | Diverse | Flip |
| Muon-NS: Mean | 89.1 0.5 | 79.4 2.3 | 19.4 1.4 | 10.0 0.0 | 10.0 0.0 | 10.0 0.0 |
| Muon-NS: RFA | 88.6 1.1 | 74.0 3.3 | 34.8 5.9 | 32.9 4.7 | 35.4 6.6 | 45.1 5.2 |
| Tensorwise : Mean | 49.1 0.7 | 37.7 2.1 | 11.5 1.6 | 10.0 0.0 | 10.0 0.0 | 10.0 0.0 |
| Tensorwise : RFA | 50.8 1.0 | 32.7 1.9 | 16.7 2.7 | 16.3 2.8 | 14.5 2.5 | 20.5 3.4 |
| Geometry | Clean | Sign-flip | ALIE | IPM | Adaptive |
| SGD | 11.62 0.04 | 11.96 0.05 | 11.63 0.04 | 11.96 0.05 | 11.69 0.06 |
| Normalized SGD | 9.56 0.02 | 9.60 0.04 | 9.61 0.05 | 9.59 0.04 | 9.63 0.02 |
| Muon-NS | 2.55 0.01 | 2.71 0.01 | 2.71 0.01 | 2.70 0.01 | 2.99 0.02 |
| Geometry | Clean | Sign-flip | ALIE | IPM | Mimic | Adaptive |
| ResNet-18: SGD | 3.9 5.3 | 0.0 0.0 | 0.0 0.0 | 0.0 0.0 | 0.0 0.0 | 0.0 0.0 |
| ResNet-18: Normalized SGD | 14.6 10.3 | 0.0 0.1 | 0.0 0.0 | 1.5 2.9 | 1.9 2.2 | 0.0 0.0 |
| ResNet-18: Sign | 19.9 9.6 | 2.7 5.6 | 0.5 0.9 | 1.4 2.3 | 6.5 10.3 | 0.1 0.1 |
| ResNet-18: Muon-NS | 72.4 4.8 | 26.1 23.7 | 69.5 7.4 | 57.3 14.2 | 59.2 10.8 | 25.1 17.0 |
| ViT-Tiny: SGD | 4.8 4.5 | 0.1 0.3 | 2.4 3.9 | 0.8 1.8 | 0.2 0.4 | 0.1 0.2 |
| ViT-Tiny: Normalized SGD | 13.1 8.3 | 0.4 0.7 | 5.4 9.7 | 3.0 5.6 | 2.3 4.7 | 0.2 0.4 |
| Geometry | Clean | Sign-flip | IPM | Adaptive |
| MNIST/CNN: SGD | 86.4 5.3 | 65.6 10.0 | 80.5 3.9 | 72.0 5.5 |
| MNIST/CNN: Normalized SGD | 95.3 1.0 | 87.5 2.3 | 92.2 1.4 | 87.5 0.7 |
| MNIST/CNN: Muon-NS | 99.0 0.0 | 97.4 0.4 | 98.9 0.1 | 98.5 0.6 |
| Fashion-MNIST/CNN: SGD | 73.9 1.3 | 61.1 4.3 | 65.9 3.8 | 62.5 2.4 |
| Fashion-MNIST/CNN: Normalized SGD | 79.4 1.2 | 72.5 2.1 | 77.1 0.9 | 71.1 1.6 |
| Fashion-MNIST/CNN: Muon-NS | 90.9 0.3 | 88.7 0.9 | 89.9 0.1 | 89.8 0.2 |
| Geometry and aggregator | Clean | Sign-flip | IPM | Mimic |
| SGD: Mean | 40.6 2.5 | 39.3 2.8 | 39.7 3.2 | 33.1 2.4 |
| SGD: RFA | 39.8 2.0 | 29.2 2.3 | 32.9 4.2 | 29.7 5.5 |
| SGD: Krum | 16.8 1.1 | 14.1 1.8 | 15.3 1.3 | 15.9 2.4 |
| SGD: CM | 19.9 1.3 | 11.3 1.1 | 16.9 2.7 | 17.0 3.4 |
| SGD: CClip | 18.2 1.8 | 16.8 2.4 | 18.4 2.6 | 14.6 1.8 |
| Normalized SGD: Mean | 49.4 1.9 | 46.3 1.6 | 48.7 2.1 | 46.7 3.0 |
| Geometry | Attack | ||||
| SGD | Clean | 17.8 1.8 | 39.8 2.0 | 50.6 1.0 | 47.1 0.9 |
| SGD | IPM | 16.4 1.9 | 31.8 3.1 | 42.5 1.6 | 43.7 1.1 |
| SGD | Adaptive | 15.1 1.6 | 24.8 2.8 | 33.9 2.4 | 40.9 1.6 |
| Normalized SGD | Clean | 28.6 1.9 | 49.0 2.3 | 52.4 1.5 | 42.3 1.1 |
| Normalized SGD | IPM | 20.3 1.7 | 42.3 2.1 | 46.2 1.8 | 41.5 1.5 |
| Normalized SGD | Adaptive | 17.3 1.7 | 30.4 1.7 | 37.2 0.9 | 36.7 2.5 |
| Byzantine fraction | Ordinary | Extrapolated |
| 0% | 18.15 0.04 | 9.06 0.02 |
| 10% | 18.28 0.03 | 9.43 0.02 |
| 20% | 19.18 0.03 | 13.80 0.01 |
| Messages | Final | Max. | Max. | Iterations |
| Benign | 8 | |||
| Directional | 8 |
Muon Optimizer
Muon optimizer uses momentum and matrix orthogonalization to shape neural-network updates, especially in large language-model training.
See all 159 papers